Abstract
We consider the problem of recovering a complete (i.e., square and invertible) matrix A0, from Y ∈ ℝn × p with Y = A0 X0, provided X0 is sufficiently sparse. This recovery problem is central to theoretical understanding of dictionary learning, which seeks a sparse representation for a collection of input signals and finds numerous applications in modern signal processing and machine 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. Our algorithmic pipeline centers around solving a certain nonconvex optimization problem with a spherical constraint, and hence is naturally phrased in the language of manifold optimization. In a companion paper, we have showed that with high probability, our nonconvex formulation has no "spurious" local minimizers and around any saddle point, the objective function has a negative directional curvature. In this paper, we take advantage of the particular geometric structure and describe a Riemannian trust region algorithm that provably converges to a local minimizer with from arbitrary initializations. Such minimizers give excellent approximations to the rows of X0. The rows are then recovered by a linear programming rounding and deflation.
Original language | English (US) |
---|---|
Article number | 7755786 |
Pages (from-to) | 885-914 |
Number of pages | 30 |
Journal | IEEE Transactions on Information Theory |
Volume | 63 |
Issue number | 2 |
DOIs | |
State | Published - Feb 2017 |
Externally published | Yes |
Bibliographical note
Funding Information:This work was supported in part by ONR under Grant N00014-13-1-0492, in part by NSF under Grant 1343282, Grant CCF 1527809, and Grant IIS 1546411, and in part by the Moore and Sloan Foundations.
Publisher Copyright:
© 2016 IEEE.
Keywords
- Dictionary learning
- escaping saddle points
- function landscape
- inverse problems
- manifold optimization
- nonconvex optimization
- nonlinear approximation
- second-order geometry
- spherical constraint
- structured signals
- trust-region method