Complete dictionary recovery using nonconvex optimization

Ju Sun, Qing Qu, John Wright

Research output: Chapter in Book/Report/Conference proceedingConference contribution

24 Scopus citations


We consider the problem of recovering a complete (i.e., square and invertible) dictionary A0, from Y = A0X0 with Y ∈ ℝn×p. This recovery setting is central to the theoretical understanding of dictionary learning. We give the first efficient algorithm that provably recovers A0 when X0 has O (n) nonzeros per column, under suitable probability model for X0. Prior results provide recovery guarantees when X0 has only O (√n) nonzeros per column. Our algorithm is based on non-convex optimization with a spherical constraint, and hence is naturally phrased in the language of manifold optimization. Our proofs give a geometric characterization of the high-dimensional objective landscape, which shows that with high probability there are no spurious local minima. Experiments with synthetic data corroborate our theory.

Original languageEnglish (US)
Title of host publication32nd International Conference on Machine Learning, ICML 2015
EditorsFrancis Bach, David Blei
PublisherInternational Machine Learning Society (IMLS)
Number of pages10
ISBN (Electronic)9781510810587
StatePublished - Jan 1 2015
Externally publishedYes
Event32nd International Conference on Machine Learning, ICML 2015 - Lile, France
Duration: Jul 6 2015Jul 11 2015

Publication series

Name32nd International Conference on Machine Learning, ICML 2015


Other32nd International Conference on Machine Learning, ICML 2015

Fingerprint Dive into the research topics of 'Complete dictionary recovery using nonconvex optimization'. Together they form a unique fingerprint.

Cite this