Complete dictionary recovery over the sphere

Ju Sun, Qing Qu, John Wright

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

26 Scopus citations

Abstract

We consider the problem of recovering a complete (i.e., square and invertible) dictionary A0, from Y = A0X0 with Y Rn×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 nonconvex 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. This invited talk summarizes these results, presented in [1]. It also presents numerical experiments demonstrating their implications for practical problems in representation learning and the more general algorithmic problem of recovering matrix decompositions with structured factors.

Original languageEnglish (US)
Title of host publication2015 International Conference on Sampling Theory and Applications, SampTA 2015
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages407-410
Number of pages4
ISBN (Electronic)9781467373531
DOIs
StatePublished - Jul 2 2015
Externally publishedYes
Event11th International Conference on Sampling Theory and Applications, SampTA 2015 - Washington, United States
Duration: May 25 2015May 29 2015

Publication series

Name2015 International Conference on Sampling Theory and Applications, SampTA 2015

Conference

Conference11th International Conference on Sampling Theory and Applications, SampTA 2015
CountryUnited States
CityWashington
Period5/25/155/29/15

Keywords

  • Dictionary learning
  • Geometric analysis
  • Nonconvex optimization
  • Recovery guarantee
  • Riemannian trustregion method

Fingerprint Dive into the research topics of 'Complete dictionary recovery over the sphere'. Together they form a unique fingerprint.

Cite this