Alternating Direction Method of Multipliers for Solving Dictionary Learning Models

Abstract

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.

Keywords

Dictionary learning / K-SVD / Alternating direction method of multipliers / Orthogonal matching pursuit

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. 2011, 3 1 1-122

[2] Aharon M, Elad M, Bruckstein A. K-svd: An algorithm for designing overcomplete dictionaries for sparse representation. Signal Process. IEEE Trans.. 2006, 54 11 4311-4322

[3] Davis G, Mallat S, Avellaneda M. Adaptive greedy approximations. Constr. Approx.. 1997, 13 1 57-98

[4] Mallat SG, Zhang Z. Matching pursuits with time-frequency dictionaries. Signal Process. IEEE Trans.. 1993, 41 12 3397-3415

[5] Chen S, Billings SA, Luo W. Orthogonal least squares methods and their application to non-linear system identification. Int. J. Control. 1989, 50 5 1873-1896

[6] Davis GM, Mallat SG, Zhang Z. Adaptive time-frequency decompositions. Opt. Eng.. 1994, 33 7 2183-2191

[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

[8] Tropp JA. Greed is good: Algorithmic results for sparse approximation. Inf. Theory IEEE Trans.. 2004, 50 10 2231-2242

[9] Tropp JA, Gilbert AC. Signal recovery from random measurements via orthogonal matching pursuit. Inf. Theory IEEE Trans.. 2007, 53 12 4655-4666

[10] Davenport MA, Wakin MB. Analysis of orthogonal matching pursuit using the restricted isometry property. Inf. Theory IEEE Trans.. 2010, 56 9 4395-4401

[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.. 2012, 58 2 1094-1121

[13] Needell D, Vershynin R. Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit. Found. Comput. Math.. 2009, 9 3 317-334

[14] Needell D, Vershynin R. Signal recovery from incomplete and inaccurate measurements via regularized orthogonal matching pursuit. Sel. Top. Signal Process. IEEE J.. 2010, 4 2 310-316

[15] Needell D, Tropp JA. Cosamp: Iterative signal recovery from incomplete and inaccurate samples. Appl. Comput. Harmon. Anal. 2009, 26 3 301-321

[16] Rubinstein R, Zibulevsky M, Elad M. Efficient implementation of the k-svd algorithm using batch orthogonal matching pursuit. CS Tech.. 2008, 40 1-15

[17] Chen SS, Donoho DL, Saunders MA. Atomic decomposition by basis pursuit. SIAM J. Sci. Comput.. 1998, 20 1 33-61

[18] Beck A, Teboulle M. A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imaging Sci.. 2009, 2 1 183-202

[19] Van Den Berg E, Friedlander MP. Probing the pareto frontier for basis pursuit solutions. SIAM J. Sci. Comput.. 2008, 31 2 890-912

[20] Becker S, Bobin J, Candès EJ. Nesta: A fast and accurate first-order method for sparse recovery. SIAM J. Imaging Sci.. 2011, 4 1 1-39

[21] Donoho DL, Huo X. Uncertainty principles and ideal atomic decomposition. Inf. Theory IEEE Trans.. 2001, 47 7 2845-2862

[22] Elad M, Bruckstein AM. A generalized uncertainty principle and sparse representation in pairs of bases. Inf. Theory IEEE Trans.. 2002, 48 9 2558-2567

[23] Donoho DL, Elad M. Optimally sparse representation in general (nonorthogonal) dictionaries via l1 minimization. Proc. Natl. Acad. Sci.. 2003, 100 5 2197-2202

[24] Donoho DL, Elad M, Temlyakov VN. Stable recovery of sparse overcomplete representations in the presence of noise. Inf. Theory IEEE Trans.. 2006, 52 1 6-18

[25] Tropp JA. Just relax: Convex programming methods for identifying sparse signals in noise. Inf. Theory IEEE Trans.. 2006, 52 3 1030-1051

[26] Engan K, Aase SO, Husøy JH. Multi-frame compression: Theory and design. Signal Process.. 2000, 80 10 2121-2140

[27] Bruckstein AM, Donoho DL, Elad M. From sparse solutions of systems of equations to sparse modeling of signals and images. SIAM Rev.. 2009, 51 1 34-81

[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. 2010, 98 6 972-982

[30] Elad M. Sparse and Redundant Representations: From Theory to Applications in Signal and Image Processing. 2010 New York: Springer

[31] Rakotomamonjy A. Applying alternating direction method of multipliers for constrained dictionary learning. Neurocomputing. 2013, 106 126-136

[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

[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

[34] Shen Y, Wen Z, Zhang Y. Augmented lagrangian alternating direction method for matrix separation based on low-rank factorization. Optim. Methods Softw.. 2014, 29 2 239-263

[35] Xu Y, Yin W, Wen Z, Zhang Y. An alternating direction algorithm for matrix completion with nonnegative factors. Front. Math. China. 2012, 7 2 365-384

[36] Wen, Z., Peng, X., Liu, X., Bai, X., Sun, X.: Asset allocation under the basel accord risk measures, Available at SSRN 2202845

[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

[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

[39] Lu Z, Zhang Y. Sparse approximation via penalty decomposition methods. SIAM J. Optim.. 2013, 23 4 2448-2478

[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.. 2013, 6 3 1758-1789

[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. 2011, 5 4 815-841

[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

[43] Dahl J, Hansen PC, Jensen SH, Jensen TL. Algorithms and software for total variation image reconstruction via first-order methods. Numer. Algorithms. 2010, 53 1 67-92