×

zbMATH — the first resource for mathematics

Alternating direction method of multipliers for solving dictionary learning models. (English) Zbl 1321.49049
Summary: In recent years, there has been a growing usage of sparse representations in signal processing. This paper revisits the K-SVD, an algorithm for designing overcomplete dictionaries for sparse and redundant representations. We present a new approach to solve dictionary learning models by combining the alternating direction method of multipliers and the orthogonal matching pursuit. The experimental results show that our approach can reliably obtain better learned dictionary elements and outperform other algorithms.
Reviewer: Reviewer (Berlin)
MSC:
49M37 Numerical methods based on nonlinear programming
49N45 Inverse problems in optimal control
65K05 Numerical mathematical programming methods
90C30 Nonlinear programming
68U10 Computing methodologies for image processing
94A08 Image processing (compression, reconstruction, etc.) in information and communication theory
94A12 Signal theory (characterization, reconstruction, filtering, etc.)
Software:
CoSaMP; LMaFit; na28; NESTA; PDCO; SPGL1
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Boyd, S; Parikh, N; Chu, E; Peleato, B; Eckstein, J, Distributed optimization and statistical learning via the alternating direction method of multipliers, Found. Trends Mach. Learning, 3, 1-122, (2011) · Zbl 1229.90122
[2] Aharon, M; Elad, M; Bruckstein, A, K-svd: an algorithm for designing overcomplete dictionaries for sparse representation, Signal Process. IEEE Trans., 54, 4311-4322, (2006) · Zbl 1375.94040
[3] Davis, G; Mallat, S; Avellaneda, M, Adaptive greedy approximations, Constr. Approx., 13, 57-98, (1997) · Zbl 0885.41006
[4] Mallat, SG; Zhang, Z, Matching pursuits with time-frequency dictionaries, Signal Process. IEEE Trans., 41, 3397-3415, (1993) · Zbl 0842.94004
[5] Chen, S; Billings, SA; Luo, W, Orthogonal least squares methods and their application to non-linear system identification, Int. J. Control, 50, 1873-1896, (1989) · Zbl 0686.93093
[6] Davis, GM; Mallat, SG; Zhang, Z, Adaptive time-frequency decompositions, Opt. Eng., 33, 2183-2191, (1994)
[7] Pati, Y.C., Rezaiifar, R., Krishnaprasad, P.: Orthogonal matching pursuit: Recursive function approximation with applications to wavelet decomposition. In: Signals, Systems and Computers, 1993. 1993 Conference Record of The Twenty-Seventh Asilomar Conference on IEEE, 1993, pp. 40-44 · Zbl 0686.93093
[8] Tropp, JA, Greed is good: algorithmic results for sparse approximation, Inf. Theory IEEE Trans., 50, 2231-2242, (2004) · Zbl 1288.94019
[9] Tropp, JA; Gilbert, AC, Signal recovery from random measurements via orthogonal matching pursuit, Inf. Theory IEEE Trans., 53, 4655-4666, (2007) · Zbl 1288.94022
[10] Davenport, MA; Wakin, MB, Analysis of orthogonal matching pursuit using the restricted isometry property, Inf. Theory IEEE Trans., 56, 4395-4401, (2010) · Zbl 1366.94093
[11] Needell, D., Tropp, J., Vershynin, R.: Greedy signal recovery review. In: Signals, Systems and Computers, 2008 42nd Asilomar Conference on IEEE, 2008, pp. 1048-1050
[12] Donoho, DL; Tsaig, Y; Drori, I; Starck, J-L, Sparse solution of underdetermined systems of linear equations by stagewise orthogonal matching pursuit, Inf. Theory IEEE Trans., 58, 1094-1121, (2012) · Zbl 1365.94069
[13] Needell, D; Vershynin, R, Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit, Found. Comput. Math., 9, 317-334, (2009) · Zbl 1183.68739
[14] Needell, D; Vershynin, R, Signal recovery from incomplete and inaccurate measurements via regularized orthogonal matching pursuit, Sel. Top. Signal Process. IEEE J., 4, 310-316, (2010)
[15] Needell, D; Tropp, JA, Cosamp: iterative signal recovery from incomplete and inaccurate samples, Appl. Comput. Harmon. Anal, 26, 301-321, (2009) · Zbl 1163.94003
[16] Rubinstein, R; Zibulevsky, M; Elad, M, Efficient implementation of the k-svd algorithm using batch orthogonal matching pursuit, CS Tech., 40, 1-15, (2008)
[17] Chen, SS; Donoho, DL; Saunders, MA, Atomic decomposition by basis pursuit, SIAM J. Sci. Comput., 20, 33-61, (1998) · Zbl 0919.94002
[18] Beck, A; Teboulle, M, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci., 2, 183-202, (2009) · Zbl 1175.94009
[19] Berg, E; Friedlander, MP, Probing the Pareto frontier for basis pursuit solutions, SIAM J. Sci. Comput., 31, 890-912, (2008) · Zbl 1193.49033
[20] Becker, S; Bobin, J; Candès, EJ, Nesta: A fast and accurate first-order method for sparse recovery, SIAM J. Imaging Sci., 4, 1-39, (2011) · Zbl 1209.90265
[21] Donoho, DL; Huo, X, Uncertainty principles and ideal atomic decomposition, Inf. Theory IEEE Trans., 47, 2845-2862, (2001) · Zbl 1019.94503
[22] Elad, M; Bruckstein, AM, A generalized uncertainty principle and sparse representation in pairs of bases, Inf. Theory IEEE Trans., 48, 2558-2567, (2002) · Zbl 1062.15001
[23] Donoho, DL; Elad, M, Optimally sparse representation in general (nonorthogonal) dictionaries via l1 minimization, Proc. Natl. Acad. Sci., 100, 2197-2202, (2003) · Zbl 1064.94011
[24] Donoho, DL; Elad, M; Temlyakov, VN, Stable recovery of sparse overcomplete representations in the presence of noise, Inf. Theory IEEE Trans., 52, 6-18, (2006) · Zbl 1288.94017
[25] Tropp, JA, Just relax: convex programming methods for identifying sparse signals in noise, Inf. Theory IEEE Trans., 52, 1030-1051, (2006) · Zbl 1288.94025
[26] Engan, K; Aase, SO; Husøy, JH, Multi-frame compression: theory and design, Signal Process., 80, 2121-2140, (2000) · Zbl 1098.94538
[27] Bruckstein, AM; Donoho, DL; Elad, M, From sparse solutions of systems of equations to sparse modeling of signals and images, SIAM Rev., 51, 34-81, (2009) · Zbl 1178.68619
[28] Elad, M., Aharon, M.: Image denoising via learned dictionaries and sparse representation. In: Computer Vision and Pattern Recognition, 2006 IEEE Computer Society Conference on, vol. 1, IEEE, 2006, pp. 895-900
[29] Elad, M; Figueiredo, MA; Ma, Y, On the role of sparse and redundant representations in image processing, Proc. IEEE, 98, 972-982, (2010)
[30] Elad, M.: Sparse and Redundant Representations: From Theory to Applications in Signal and Image Processing. Springer, New York (2010) · Zbl 1211.94001
[31] Rakotomamonjy, A, Applying alternating direction method of multipliers for constrained dictionary learning, Neurocomputing, 106, 126-136, (2013)
[32] Sun, D.L., Fevotte, C.: Alternating direction method of multipliers for non-negative matrix factorization with the beta-divergence. In: Acoustics, Speech and Signal Processing (ICASSP), 2014 IEEE International Conference on IEEE, 2014, pp. 6201-6205 · Zbl 1193.49033
[33] Ling, Q., Xu, Y., Yin, W., Wen, Z.: Decentralized low-rank matrix completion. In: Acoustics, Speech and Signal Processing (ICASSP), 2012 IEEE International Conference on, IEEE, 2012, pp. 2925-2928 · Zbl 1288.94022
[34] Shen, Y; Wen, Z; Zhang, Y, Augmented Lagrangian alternating direction method for matrix separation based on low-rank factorization, Optim. Methods Softw., 29, 239-263, (2014) · Zbl 1285.90068
[35] Xu, Y; Yin, W; Wen, Z; Zhang, Y, An alternating direction algorithm for matrix completion with nonnegative factors, Front. Math. China, 7, 365-384, (2012) · Zbl 1323.65044
[36] Wen, Z., Peng, X., Liu, X., Bai, X., Sun, X.: Asset allocation under the basel accord risk measures, Available at SSRN 2202845 · Zbl 1366.94093
[37] Hong, M., Luo, Z.-Q., Razaviyayn, M.: Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems, arXiv preprint arXiv:1410.1390 · Zbl 1356.49061
[38] Magnússon, S., Weeraddana, P.C., Rabbat, M. G., Fischione, C.: On the convergence of alternating direction lagrangian methods for nonconvex structured optimization problems, arXiv preprint arXiv:1409.8033 · Zbl 1370.90196
[39] Lu, Z; Zhang, Y, Sparse approximation via penalty decomposition methods, SIAM J. Optim., 23, 2448-2478, (2013) · Zbl 1295.90056
[40] Xu, Y; Yin, W, A block coordinate descent method for regularized multiconvex optimization with applications to nonnegative tensor factorization and completion, SIAM J. Imaging Sci., 6, 1758-1789, (2013) · Zbl 1280.49042
[41] Filipovi, M; Kopriva, I, A comparison of dictionary based approaches to inpainting and denoising with an emphasis to independent component analysis learned dictionaries, Inverse Probl. Imaging, 5, 815-841, (2011) · Zbl 1234.68450
[42] Mohimani, G.H., Babaie-Zadeh, M., Jutten, C.: Fast sparse representation based on smoothed l0 norm. In: Independent Component Analysis and Signal Separation, Springer, 2007, pp. 389-396 · Zbl 1173.94376
[43] Dahl, J; Hansen, PC; Jensen, SH; Jensen, TL, Algorithms and software for total variation image reconstruction via first-order methods, Numer. Algorithms, 53, 67-92, (2010) · Zbl 1181.94009
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.