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 language | English (US) |
---|---|
Title of host publication | 2015 International Conference on Sampling Theory and Applications, SampTA 2015 |
Publisher | Institute of Electrical and Electronics Engineers Inc. |
Pages | 407-410 |
Number of pages | 4 |
ISBN (Electronic) | 9781467373531 |
DOIs | |
State | Published - Jul 2 2015 |
Externally published | Yes |
Event | 11th International Conference on Sampling Theory and Applications, SampTA 2015 - Washington, United States Duration: May 25 2015 → May 29 2015 |
Publication series
Name | 2015 International Conference on Sampling Theory and Applications, SampTA 2015 |
---|
Conference
Conference | 11th International Conference on Sampling Theory and Applications, SampTA 2015 |
---|---|
Country/Territory | United States |
City | Washington |
Period | 5/25/15 → 5/29/15 |
Bibliographical note
Publisher Copyright:© 2015 IEEE.
Keywords
- Dictionary learning
- Geometric analysis
- Nonconvex optimization
- Recovery guarantee
- Riemannian trustregion method