mlsanityData to 7 Oct 2026

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

arXiv 1601.02049 ↗First posted 8 Jan 2016math.PR cs.LG math.STcited by 26

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 4; 2022: 2; 2023: 1; 2024: 6; 2025: 9; 2026: 4.

26 papers.

Sort:

By area:

  1. 2023White-Box Transformers via Sparse Rate Reductioncited by 77
  2. 2025Archetypal SAE: Adaptive and Stable Dictionary Learning for Concept Extraction in Large Vision Modelscited by 67
  3. 2025Interpreting the linear structure of vision-language model embedding spacescited by 32
  4. 2021Optimal Spectral Recovery of a Planted Vector in a Subspacecited by 21
  5. 2021Stable and Interpretable Unrolled Dictionary Learningcited by 15
  6. 2025Sparse but Wrong: Incorrect L0 Leads to Incorrect Features in Sparse Autoencoderscited by 11
  7. 2025AbsTopK: Rethinking Sparse Autoencoders For Bidirectional Featurescited by 8
  8. 2022Simple Alternating Minimization Provably Solves Complete Dictionary Learningcited by 6
  9. 2022Optimal Regularization for a Data Sourcecited by 6
  10. 2024Towards scientific discovery with dictionary learning: Extracting biological concepts from microscopy foundation modelscited by 4
  11. 2024Tensor learning with orthogonal, Lorentz, and symplectic symmetriescited by 3
  12. 2024The Star Geometry of Critic-Based Regularizer Learningcited by 3
14 more
  1. 2024SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and Morecited by 3
  2. 2025SPEAR++: Scaling Gradient Inversion via Sparsely-Used Dictionary Learningcited by 3
  3. 2021Convex Sparse Blind Deconvolutioncited by 2
  4. 2024Unsupervised Representation Learning from Sparse Transformation Analysiscited by 2
  5. 2025DB-KSVD: Scalable Alternating Optimization for Disentangling High-Dimensional Embedding Spacescited by 2
  6. 2025A Unified Theory of Sparse Dictionary Learning in Mechanistic Interpretability: Piecewise Biconvexity and Spurious Minimacited by 2
  7. 2026Toward Identifiable Sparse Autoencoderscited by 2
  8. 2021A Riemannian smoothing steepest descent method for non-Lipschitz optimization on submanifoldscited by 1
  9. 2024Unsupervised Congestion Status Identification Using LMP Datacited by 1
  10. 2025Imaging with super-resolution in changing random mediacited by 1
  11. 2025Recovering Imbalanced Clusters via Gradient-Based Projection Pursuitcited by 0
  12. 2026Concept Component Analysis: A Principled Approach for Concept Extraction in LLMscited by 0
  13. 2026Iterative Atom Refinement: A Monotonicity Principle for Dictionary Learningcited by 0
  14. 2026Emergent phases of superposition: from partial to full representationcited by 0