# Complete Dictionary Recovery over the Sphere

arXiv: https://arxiv.org/abs/1504.06785 · HTML: https://mlsanity.com/paper/1504.06785/

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Apr 2015.

## Built on by (most cited first, 19 of 19)

- [On the Optimization Landscape of Neural Collapse under MSE Loss: Global Optimality with Unconstrained Features](https://mlsanity.com/paper/2203.01238/) (2022)
- [Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurements](https://mlsanity.com/paper/2104.14526/) (2021)
- [The loss landscape of deep linear neural networks: a second-order analysis](https://mlsanity.com/paper/2107.13289/) (2021)
- [Optimal Spectral Recovery of a Planted Vector in a Subspace](https://mlsanity.com/paper/2105.15081/) (2021)
- [Preconditioned Gradient Descent for Overparameterized Nonconvex Burer--Monteiro Factorization with Global Optimality Certification](https://mlsanity.com/paper/2206.03345/) (2022)
- [Simple Alternating Minimization Provably Solves Complete Dictionary Learning](https://mlsanity.com/paper/2210.12816/) (2022)
- [Escaping Saddle Points for Nonsmooth Weakly Convex Functions via Perturbed Proximal Algorithms](https://mlsanity.com/paper/2102.02837/) (2021)
- [Unique sparse decomposition of low rank matrices](https://mlsanity.com/paper/2106.07736/) (2021)
- [Behind the Scenes of Gradient Descent: A Trajectory Analysis via Basis Function Decomposition](https://mlsanity.com/paper/2210.00346/) (2022)
- [Closed-Loop Transcription via Convolutional Sparse Coding](https://mlsanity.com/paper/2302.09347/) (2023)
- [Escaping Saddle Points in Distributed Newton's Method with Communication Efficiency and Byzantine Resilience](https://mlsanity.com/paper/2103.09424/) (2021)
- [Dictionary Learning for the Almost-Linear Sparsity Regime](https://mlsanity.com/paper/2210.10855/) (2022)
- [Efficient Sparse Coding using Hierarchical Riemannian Pursuit](https://mlsanity.com/paper/2104.10314/) (2021)
- [Convex Sparse Blind Deconvolution](https://mlsanity.com/paper/2106.07053/) (2021)
- [A Comprehensive Study on Optimization Strategies for Gradient Descent In Deep Learning](https://mlsanity.com/paper/2101.02397/) (2021)
- [Convergence of alternating minimisation algorithms for dictionary learning](https://mlsanity.com/paper/2304.01768/) (2023)
- [Decentralized Complete Dictionary Learning via ℓ4-Norm Maximization](https://mlsanity.com/paper/2211.03628/) (2022)
- [Efficient Matrix Factorization Via Householder Reflections](https://mlsanity.com/paper/2405.07649/) (2024)
- [Fast Structured Orthogonal Dictionary Learning using Householder Reflections](https://mlsanity.com/paper/2409.09138/) (2024)

## Abstract (arXiv)

We consider the problem of recovering a complete (i.e., square and invertible) matrix mathbf A0, from mathbf Y ∈ mathbb Rn × p with mathbf Y = mathbf A0 mathbf X0, provided mathbf X0 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 A0 when mathbf X0 has O(n) nonzeros per column, under suitable probability model for mathbf X0. In contrast, prior results based on efficient algorithms provide recovery guarantees when mathbf X0 has only O(n1-δ) nonzeros per column for any constant δ ∈ (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.