An augmented Lagrangian multi-scale dictionary learning algorithm
- PDF / 1,245,160 Bytes
- 16 Pages / 595.28 x 793.7 pts Page_size
- 83 Downloads / 183 Views
RESEARCH
Open Access
An augmented Lagrangian multi-scale dictionary learning algorithm Qiegen Liu1, Jianhua Luo1*, Shanshan Wang1, Moyan Xiao1 and Meng Ye2
Abstract Learning overcomplete dictionaries for sparse signal representation has become a hot topic fascinated by many researchers in the recent years, while most of the existing approaches have a serious problem that they always lead to local minima. In this article, we present a novel augmented Lagrangian multi-scale dictionary learning algorithm (ALM-DL), which is achieved by first recasting the constrained dictionary learning problem into an AL scheme, and then updating the dictionary after each inner iteration of the scheme during which majorizationminimization technique is employed for solving the inner subproblem. Refining the dictionary from low scale to high makes the proposed method less dependent on the initial dictionary hence avoiding local optima. Numerical tests for synthetic data and denoising applications on real images demonstrate the superior performance of the proposed approach. Keywords: dictionary learning, augmented Lagrangian, multi-scale, refinement, image denoising.
1. Introduction In the last two decades, more and more studies have focused on dictionary learning, the goal of which is to model signals as a sparse linear combination of atoms that form a dictionary below a certain error toleration. Sparse representation of signals under the learned dictionary possesses significant advantages over the prespecified dictionary such as wavelet and discrete cosine transform (DCT) as demonstrated in many literatures [1-3] and it has been widely used in denoising, inpainting, and classification areas with state-of-the-art results obtained [1-5]. Considering there is a signal bl ÎRM, it can be represented by a linear combination of a few atoms either exactly as bl = Axl or proximately as bl ≈ Axl, where A represents the dictionary and xl denotes the representation coefficients. Given an input matrix B = [b1, ..., bL] in RM×L of L signals, the problem then can be formulated as an optimization problem jointly over a dictionary A = [a1, ..., aJ] in RM×J and the sparse representation matrix X = [x1, ..., xJ] in RJ×L, namely
* Correspondence: [email protected] 1 College of Life Science and Technology, Shanghai Jiaotong University, 200240, Shanghai, P.R. China Full list of author information is available at the end of the article
⎧ L ⎨ min xl 0 ⎩
A,X
l=1
s.t.bl − Axl 2 ≤ τ ,
l = 1, · · · , L;
2 aj = 1, 2
j = 1, · · · , J
(1)
where ||·|| 0 denotes the l 0 norm which counts the number of nonzero coefficients of the vector, ||·|| 2 stands for the Euclidean norm on RM, and τ is the tolerable limit of error in reconstruction. Most of the existing methods for solving Equation 1 can be essentially interpreted as different generalizations of the K-means clustering algorithm because they usually have two-step iterative approaches consisting of a sparse coding step where sparse approximations X is found with A fixed and a dictionary upda
Data Loading...
