Abstract
In dictionary learning, a matrix comprised of signals Y is factorized into the product of two matrices: a matrix of prototypical atoms D, and a sparse matrix containing coefficients for atoms in D, called X. This process has applications in signal processing, image recognition, and a number of other fields. Many procedures for solving the dictionary learning problem follow the alternating minimization paradigm; that is, by alternating between solving for D and X, until the procedure converges to a solution. Our findings indicate that the costly step of alternating minimization can be avoided in some cases, by modifying an initialization procedure that was proposed in 2014. We provide theoretical justification and empirical evidence showing that atom recovery and reasonable data reconstruction is possible under these new assumptions.
Similar content being viewed by others
References
Agarwal, A., Anandkumar, A., Jain, P., Netrapalli, P., Tandon, R.: Learning sparsely used overcomplete dictionaries. Proc. Mach. Learn. Res. (COLT) 35, 123–137 (2014)
Agarwal, A., Anandkumar, A., Jain, P., Netrapalli, P.: Learning sparsely used overcomplete dictionaries via alternating minimization. SIAM J. Optim. 26(4), 2775–2799 (2016)
Aharon, M., Elad, M., Bruckstein, A.: K-SVD: an algorithm for designing overcomplete dictionaries for sparse representation. IEEE Trans. Signal Process. 54, 4311–4322 (2006)
Arora, S., Ge, R., Moitra, A.: New algorithms for learning incoherent and overcomplete dictionaries. Proc. Mach. Learn. Res. (COLT) 35, 779–806 (2014)
Bandeira, A.S., Mixon, D.G., Moreira, J.: A conditional construction of restricted isometries. Int. Math. Res. Not. IMRN 2, 372–381 (2017)
Barak, B., Kelner, J.A., Steurer, D.: Dictionary learning and tensor decomposition via the sum-of-squares method. STOC (2015)
Blumensath, T., Davies, M.: Iterative hard thresholding for compressed sensing. Appl. Comput. Harmon. Anal. 27(3), 265–74 (2009)
Bouton, C.E., Shaikhouni, A., Annetta, N.V., Bockbrader, M.A., Friedenberg, D.A., Nielson, D.M.: e.a.: Restoring cortical control of functional movement in a human with quadriplegia. Nature 533, 247–250 (2016)
Cai, T.T., Wang, L.: Orthogonal matching pursuit for sparse signal recovery with noise. IEEE Trans. Inf. Theory 57(7), 4680–4688 (2011)
Candes, E., Romberg, J., Tao, T.: Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Trans. Inf. Theory 52(2), 489–509 (2006a)
Candes, E., Romberg, J., Tao, T.: Stable signal recovery from incomplete and inaccurate measurements. Commun. Pure Appl. Math. 59(8), 1207–1223 (2006b)
Cohen, A., Dahmen, W., DeVore, R.: Orthogonal matching pursuit under the restricted isometry property. Constr. Approx. 45(1), 113–127 (2017)
Daubechies, I., DeVore, R., Fornasier, M., Gunturk, S.: Iteratively reweighted least squares minimization for sparse recovery. Commun. Pure Appl. Math. 63(1), 1–38 (2010)
Davenport, M.A., Wakin, M.B.: Analysis of orthogonal matching pursuit using the restricted isometry property. IEEE Trans. Inf. Theory 56(9), 4395–4401 (2010)
Donoho, D.L.: Compressed sensing. IEEE Trans. Inf. Theory 52(4), 1289–1306 (2006)
Donoho, D.L., Elad, M.: Optimally sparse representation in general (nonorthogonal) dictionaries via \(l^{1}\) minimization. Proc. Natl. Acad. Sci. 100(1), 2197–2202 (2003)
Engan, K., Aase, S., Husoy, J.: Method of optimal directions for frame design. In: Proceedings of 1999 IEEE International Conference on Acoustics, Speech, and Signal Processing (1999)
Field, D., Olshausen, B.: Emergence of simple-cell receptive field properties by learning a sparse code for natural images. Nature 381, 607–609 (1996)
Foucart, S.: Sparse recovery algorithms: sufficient conditions in terms of restricted isometry constants. Approximation Theory XIII: San Antonio 2010. Springer Proceedings in Mathematics, vol. 13, pp. 65–77. Springer, New York (2012)
Gribonval, R., Schnass, K.: Dictionary identification-sparse matrix-factorization via \(l1\)-minimization. IEEE Trans. Inf. Theory 56(7), 3523–3539 (2010)
Gribonval, R., Jenatton, R., Bach, F.: Sparse and spurious: dictionary learning with noise and outliers. IEEE Trans. Inf. Theory 61(11), 6298–6319 (2015)
Hansen, F., Pedersen, G.: Jensen’s operator inequality. Bull. Lond. Math. Soc. 35(4), 553–564 (2003)
Jenatton, R., Mairal, J., Obozinski, G., Bach, F.R.: Proximal methods for sparse hierarchical dictionary learning. In: 27th International Conference on Machine Learning
Mairal, J., Sapiro, G., Elad, M.: Learning multiscale sparse representations for image and video restoration. Multiscale Model. Simul. 7(1), 214–241 (2008)
Naumova, V., Schnass, K.: Dictionary learning from incomplete data for efficient image restoration. In: 2017 25th European Signal Processing Conference (EUSIPCO), pp. 1425–1429 (2017)
Newman, D., Shepp, L.: The double dixie cup problem. Am. Math. Mon. 67(1), 58–61 (1960)
Schnass, K.: On the identifiability of overcomplete dictionaries via the minimisation principle underlying K-SVD. Appl. Comput. Harmon. Anal. 37(3), 464–491 (2014)
Spielman, D.A., Wang, H., Wright, J.: Exact recovery of sparsely-used dictionaries. Proc. Mach. Learn. Res. (COLT) 23, 1–18 (2012)
Tosic, I., Frossard, P.: Dictionary learning. IEEE Signal Process. Mag. 28(2), 27–38 (2011)
Tropp, J.A.: Greed is good: algorithmic results for sparse approximation. IEEE Trans. Inf. Theory 50(10), 2231–2242 (2004)
Vershynin, R.: Introduction to the non-asymptotic analysis of random matrices. In: Compressed Sensing, pp. 210–268. Cambridge University Press, Cambridge (2012)
Zhang, Q., Li, B.: Discriminative K-SVD for dictionary learning in face recognition. In: 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pp. 2691–2698 (2010)
Acknowledgements
Enrico Au-Yeung is grateful for the financial support of an Undergraduate Research Assistant Program (URAP) Grant from DePaul University. Greg Zanotti is grateful that the Undergraduate Research Assistant Program (URAP) Grant from DePaul University makes this research project possible.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
About this article
Cite this article
Au-Yeung, E., Zanotti, G. Fast Overcomplete Dictionary Construction with Probabilistic Guarantees. Bull Braz Math Soc, New Series 51, 719–743 (2020). https://doi.org/10.1007/s00574-019-00171-y
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00574-019-00171-y