# Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Method

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

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Nov 2015.

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

- [A Geometric Analysis of Neural Collapse with Unconstrained Features](https://mlsanity.com/paper/2105.02375/) (2021)
- [Neural Collapse with Normalized Features: A Geometric Analysis over the Riemannian Manifold](https://mlsanity.com/paper/2209.09211/) (2022)
- [Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurements](https://mlsanity.com/paper/2104.14526/) (2021)
- [Neural Collapse in Multi-label Learning with Pick-all-label Loss](https://mlsanity.com/paper/2310.15903/) (2023)
- [On Riemannian Stochastic Approximation Schemes with Fixed Step-Size](https://mlsanity.com/paper/2102.07586/) (2021)
- [First-Order Algorithms for Min-Max Optimization in Geodesic Metric Spaces](https://mlsanity.com/paper/2206.02041/) (2022)
- [Riemannian stochastic optimization methods avoid strict saddle points](https://mlsanity.com/paper/2311.02374/) (2023)
- [Optimal Regularization for a Data Source](https://mlsanity.com/paper/2212.13597/) (2022)
- [No-go Theorem for Acceleration in the Hyperbolic Plane](https://mlsanity.com/paper/2101.05657/) (2021)
- [Accelerated Riemannian Optimization: Handling Constraints with a Prox to Bound Geometric Penalties](https://mlsanity.com/paper/2211.14645/) (2022)
- [Dictionary Learning for the Almost-Linear Sparsity Regime](https://mlsanity.com/paper/2210.10855/) (2022)
- [A Riemannian ADMM](https://mlsanity.com/paper/2211.02163/) (2022)
- [Multilinear Kernel Regression and Imputation via Manifold Learning](https://mlsanity.com/paper/2402.03648/) (2024)
- [SPEAR++: Scaling Gradient Inversion via Sparsely-Used Dictionary Learning](https://mlsanity.com/paper/2510.24200/) (2025)
- [Efficient Sparse Coding using Hierarchical Riemannian Pursuit](https://mlsanity.com/paper/2104.10314/) (2021)
- [Last-Iterate Convergence of Adaptive Riemannian Gradient Descent for Equilibrium Computation](https://mlsanity.com/paper/2306.16617/) (2023)
- [Streamlining in the Riemannian Realm: Efficient Riemannian Optimization with Loopless Variance Reduction](https://mlsanity.com/paper/2403.06677/) (2024)
- [Finite-Time Analysis of Stochastic Nonconvex Nonsmooth Optimization on the Riemannian Manifolds](https://mlsanity.com/paper/2510.21468/) (2025)
- [Non-Convex Compressed Sensing with Training Data](https://mlsanity.com/paper/2101.08310/) (2021)
- [Convergence of alternating minimisation algorithms for dictionary learning](https://mlsanity.com/paper/2304.01768/) (2023)
- [Learning-Rate-Free Stochastic Optimization over Riemannian Manifolds](https://mlsanity.com/paper/2406.02296/) (2024)
- [Online Orthogonal Dictionary Learning Based on Frank-Wolfe Method](https://mlsanity.com/paper/2103.01484/) (2021)
- [Learning Trees of ℓ0-Minimization Problems](https://mlsanity.com/paper/2302.02548/) (2023)
- [Sharper Convergence Rates for Nonconvex Optimisation via Reduction Mappings](https://mlsanity.com/paper/2506.08428/) (2025)

## 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. 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 (arXiv:1511.03607), 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 rows of mathbf X0. The rows are then recovered by linear programming rounding and deflation.