# Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture

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

## Key facts

- Cited by 49 papers in the map (data through 7 Oct 2026).
- First posted on arXiv 11 Nov 2015.

## Built on by (most cited first, 30 of 49)

- [A Geometric Analysis of Neural Collapse with Unconstrained Features](https://mlsanity.com/paper/2105.02375/) (2021)
- [Edge Artificial Intelligence for 6G: Vision, Enabling Technologies, and Applications](https://mlsanity.com/paper/2111.12444/) (2021)
- [An Unconstrained Layer-Peeled Perspective on Neural Collapse](https://mlsanity.com/paper/2110.02796/) (2021)
- [Neural Collapse with Normalized Features: A Geometric Analysis over the Riemannian Manifold](https://mlsanity.com/paper/2209.09211/) (2022)
- [Provable Representation Learning for Imitation Learning via Bi-level Optimization](https://mlsanity.com/paper/2002.10544/) (2020)
- [SPEAR:Exact Gradient Inversion of Batches in Federated Learning](https://mlsanity.com/paper/2403.03945/) (2024)
- [Revisiting Sparse Convolutional Model for Visual Recognition](https://mlsanity.com/paper/2210.12945/) (2022)
- [A Global Geometric Analysis of Maximal Coding Rate Reduction](https://mlsanity.com/paper/2406.01909/) (2024)
- [Finding Second-Order Stationary Points in Nonconvex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2110.04814/) (2021)
- [Preconditioned Gradient Descent for Over-Parameterized Nonconvex Matrix Factorization](https://mlsanity.com/paper/2504.09708/) (2025)
- [Understanding approximate and unrolled dictionary learning for pattern recovery](https://mlsanity.com/paper/2106.06338/) (2021)
- [First-Order Algorithms for Min-Max Optimization in Geodesic Metric Spaces](https://mlsanity.com/paper/2206.02041/) (2022)
- [Decentralized Nonconvex Optimization with Guaranteed Privacy and Accuracy](https://mlsanity.com/paper/2212.07534/) (2022)
- [Time Series Forecasting via Learning Convolutionally Low-Rank Models](https://mlsanity.com/paper/2104.11510/) (2021)
- [Simple Alternating Minimization Provably Solves Complete Dictionary Learning](https://mlsanity.com/paper/2210.12816/) (2022)
- [Optimal Regularization for a Data Source](https://mlsanity.com/paper/2212.13597/) (2022)
- [Gradient descent provably escapes saddle points in the training of shallow ReLU networks](https://mlsanity.com/paper/2208.02083/) (2022)
- [Personalized Dictionary Learning for Heterogeneous Datasets](https://mlsanity.com/paper/2305.15311/) (2023)
- [Sparse Personalized Federated Learning](https://mlsanity.com/paper/2107.05330/) (2021)
- [Sparse Federated Learning with Hierarchical Personalized Models](https://mlsanity.com/paper/2203.13517/) (2022)
- [Riemannian Perspective on Matrix Factorization](https://mlsanity.com/paper/2102.00937/) (2021)
- [Nonconvex Matrix Factorization is Geodesically Convex: Global Landscape Analysis for Fixed-rank Matrix Optimization From a Riemannian Perspective](https://mlsanity.com/paper/2209.15130/) (2022)
- [Multilinear Kernel Regression and Imputation via Manifold Learning](https://mlsanity.com/paper/2402.03648/) (2024)
- [Identifiable Shared Component Analysis of Unpaired Multimodal Mixtures](https://mlsanity.com/paper/2409.19422/) (2024)
- [SPEAR++: Scaling Gradient Inversion via Sparsely-Used Dictionary Learning](https://mlsanity.com/paper/2510.24200/) (2025)
- [A Geometric Approach to k-means](https://mlsanity.com/paper/2201.04822/) (2022)
- [A Riemannian ADMM](https://mlsanity.com/paper/2211.02163/) (2022)
- [Gradient descent in matrix factorization: Understanding large initialization](https://mlsanity.com/paper/2305.19206/) (2023)
- [Last-Iterate Convergence of Adaptive Riemannian Gradient Descent for Equilibrium Computation](https://mlsanity.com/paper/2306.16617/) (2023)
- [Optimal vintage factor analysis with deflation varimax](https://mlsanity.com/paper/2310.10545/) (2023)

## Abstract (arXiv)

We consider the problem of recovering a complete (i.e., square and invertible) matrix mathbf A0, from mathbf Y ∈ ℝn × p with mathbf Y = mathbf A0 mathbf X0, provided mathbf 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 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 either only guarantee recovery when mathbf X0 has O(√n) zeros per column, or require multiple rounds of SDP relaxation to work when mathbf X0 has 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. In this paper, we provide a geometric characterization of the objective landscape. In particular, we show that the problem is highly structured: with high probability, (1) there are no "spurious" local minimizers; and (2) around all saddle points the objective has a negative directional curvature. This distinctive structure makes the problem amenable to efficient optimization algorithms. In a companion paper (arXiv:1511.04777), we design a second-order trust-region algorithm over the sphere that provably converges to a local minimizer from arbitrary initializations, despite the presence of saddle points.