Complete Dictionary Recovery over the Sphere

Abstract

We consider the problem of recovering a complete (i.e., square and invertible) matrix ${\mathbf{A}}_0$, from $\mathbf{Y}\in {\mathbb{R}}^{n\times p}$ with $\mathbf{Y}={\mathbf{A}}_0{\mathbf{X}}_0$, provided ${\mathbf{X}}_0$ is sufficiently sparse. This recovery problem is central to the 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 ${\mathbf{A}}_0$ when ${\mathbf{X}}_0$ has $O(n)$ nonzeros per column, under suitable probability model for ${\mathbf{X}}_0$. In contrast, prior results based on efficient algorithms provide recovery guarantees when ${\mathbf{X}}_0$ has only $O(n^{1-\delta })$ nonzeros per column for any constant $\delta \in (0,1)$. 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. To show this apparently hard problem is tractable, we first provide a geometric characterization of the high-dimensional objective landscape, which shows that with high probability there are no "spurious" local minima. This particular geometric structure allows us to design a Riemannian trust region algorithm over the sphere that provably converges to one local minimizer with an arbitrary initialization, despite the presence of saddle points. The geometric approach we develop here may also shed light on other problems arising from nonconvex recovery of structured signals.

104 pages, 5 figures. Due to length constraint of publication, this long paper are subsequently divided into two papers (arXiv:1511.03607 and arXiv:1511.04777). Further updates will be made only to the two papers

References in corpus (2)

• High Dimensional Expectation-Maximization Algorithm: Statistical Optimization and Asymptotic Normality
• Provable Sparse Tensor Decomposition

Cited by in corpus (24)

• Global rates of convergence for nonconvex optimization on manifolds
• Nonconvex phase synchronization
• When Are Nonconvex Problems Not Scary?
• The Power of Normalization: Faster Evasion of Saddle Points
• A Riemannian low-rank method for optimization over semidefinite matrices with block-diagonal constraints
• The local convexity of solving systems of quadratic equations
• Convolutional Phase Retrieval via Gradient Descent
• On Noisy Negative Curvature Descent: Competing with Gradient Descent for Faster Non-convex Optimization
• Homotopy Analysis for Tensor PCA
• Dictionary Learning from Incomplete Data
• Finding the Sparsest Vectors in a Subspace: Theory, Algorithms, and Applications
• Structured Local Optima in Sparse Blind Deconvolution
• Complete Dictionary Learning via ${\ell }^4$-Norm Maximization over the Orthogonal Group
• An improved analysis of the ER-SpUD dictionary learning algorithm
• Dimensionality Reduction for Stationary Time Series via Stochastic Nonconvex Optimization
• Analysis of the Optimization Landscapes for Overcomplete Representation Learning
• Tensor Graphical Model: Non-convex Optimization and Statistical Inference
• The Landscape of Matrix Factorization Revisited
• On the Reconstruction Risk of Convolutional Sparse Dictionary Learning
• Multichannel Sparse Blind Deconvolution on the Sphere
• An information theoretic formulation of the Dictionary Learning and Sparse Coding Problems on Statistical Manifolds
• On the Global Geometry of Sphere-Constrained Sparse Blind Deconvolution
• Using Negative Curvature in Solving Nonlinear Programs
• Greedy Approaches to Symmetric Orthogonal Tensor Decomposition