# A note on the sample complexity of the Er-SpUD algorithm by Spielman, Wang and Wright for exact recovery of sparsely used dictionaries

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

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Jan 2016.

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

- [White-Box Transformers via Sparse Rate Reduction](https://mlsanity.com/paper/2306.01129/) (2023)
- [Archetypal SAE: Adaptive and Stable Dictionary Learning for Concept Extraction in Large Vision Models](https://mlsanity.com/paper/2502.12892/) (2025)
- [Interpreting the linear structure of vision-language model embedding spaces](https://mlsanity.com/paper/2504.11695/) (2025)
- [Optimal Spectral Recovery of a Planted Vector in a Subspace](https://mlsanity.com/paper/2105.15081/) (2021)
- [Stable and Interpretable Unrolled Dictionary Learning](https://mlsanity.com/paper/2106.00058/) (2021)
- [Sparse but Wrong: Incorrect L0 Leads to Incorrect Features in Sparse Autoencoders](https://mlsanity.com/paper/2508.16560/) (2025)
- [AbsTopK: Rethinking Sparse Autoencoders For Bidirectional Features](https://mlsanity.com/paper/2510.00404/) (2025)
- [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)
- [Towards scientific discovery with dictionary learning: Extracting biological concepts from microscopy foundation models](https://mlsanity.com/paper/2412.16247/) (2024)
- [Tensor learning with orthogonal, Lorentz, and symplectic symmetries](https://mlsanity.com/paper/2406.01552/) (2024)
- [The Star Geometry of Critic-Based Regularizer Learning](https://mlsanity.com/paper/2408.16852/) (2024)
- [SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and More](https://mlsanity.com/paper/2412.21203/) (2024)
- [SPEAR++: Scaling Gradient Inversion via Sparsely-Used Dictionary Learning](https://mlsanity.com/paper/2510.24200/) (2025)
- [A Unified Theory of Sparse Dictionary Learning in Mechanistic Interpretability: Piecewise Biconvexity and Spurious Minima](https://mlsanity.com/paper/2512.05534/) (2025)
- [Convex Sparse Blind Deconvolution](https://mlsanity.com/paper/2106.07053/) (2021)
- [Unsupervised Representation Learning from Sparse Transformation Analysis](https://mlsanity.com/paper/2410.05564/) (2024)
- [DB-KSVD: Scalable Alternating Optimization for Disentangling High-Dimensional Embedding Spaces](https://mlsanity.com/paper/2505.18441/) (2025)
- [Toward Identifiable Sparse Autoencoders](https://mlsanity.com/paper/2605.31245/) (2026)
- [A Riemannian smoothing steepest descent method for non-Lipschitz optimization on submanifolds](https://mlsanity.com/paper/2104.04199/) (2021)
- [Unsupervised Congestion Status Identification Using LMP Data](https://mlsanity.com/paper/2411.10058/) (2024)
- [Imaging with super-resolution in changing random media](https://mlsanity.com/paper/2511.14147/) (2025)
- [Recovering Imbalanced Clusters via Gradient-Based Projection Pursuit](https://mlsanity.com/paper/2502.02668/) (2025)
- [Concept Component Analysis: A Principled Approach for Concept Extraction in LLMs](https://mlsanity.com/paper/2601.20420/) (2026)
- [Iterative Atom Refinement: A Monotonicity Principle for Dictionary Learning](https://mlsanity.com/paper/2609.23812/) (2026)
- [Emergent phases of superposition: from partial to full representation](https://mlsanity.com/paper/2609.36455/) (2026)

## Abstract (arXiv)

We consider the problem of recovering an invertible n × n matrix A and a sparse n × p random matrix X based on the observation of Y = AX (up to a scaling and permutation of columns of A and rows of X). Using only elementary tools from the theory of empirical processes we show that a version of the Er-SpUD algorithm by Spielman, Wang and Wright with high probability recovers A and X exactly, provided that p ≥ Cnlog n, which is optimal up to the constant C.