# Simple, Efficient, and Neural Algorithms for Sparse Coding

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

## Key facts

- Cited by 37 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Mar 2015.

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

- [Cross-Node Federated Graph Neural Network for Spatio-Temporal Data Modeling](https://mlsanity.com/paper/2106.05223/) (2021)
- [Learning threshold neurons via the "edge of stability"](https://mlsanity.com/paper/2212.07469/) (2022)
- [Measuring Progress in Dictionary Learning for Language Model Interpretability with Board Game Models](https://mlsanity.com/paper/2408.00113/) (2024)
- [From Flat to Hierarchical: Extracting Sparse Representations with Matching Pursuit](https://mlsanity.com/paper/2506.03093/) (2025)
- [Hessian Eigenspectra of More Realistic Nonlinear Models](https://mlsanity.com/paper/2103.01519/) (2021)
- [Contrasting the landscape of contrastive and non-contrastive learning](https://mlsanity.com/paper/2203.15702/) (2022)
- [Convergence of gradient descent for deep neural networks](https://mlsanity.com/paper/2203.16462/) (2022)
- [Stable and Interpretable Unrolled Dictionary Learning](https://mlsanity.com/paper/2106.00058/) (2021)
- [I Predict Therefore I Am: Is Next Token Prediction Enough to Learn Human-Interpretable Concepts from Data?](https://mlsanity.com/paper/2503.08980/) (2025)
- [Continual Task Allocation in Meta-Policy Network via Sparse Prompting](https://mlsanity.com/paper/2305.18444/) (2023)
- [Learning from Censored and Dependent Data: The case of Linear Dynamics](https://mlsanity.com/paper/2104.05087/) (2021)
- [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)
- [From Gradient Flow on Population Loss to Learning with Stochastic Gradient Descent](https://mlsanity.com/paper/2210.06705/) (2022)
- [Do Not Train It: A Linear Neural Architecture Search of Graph Neural Networks](https://mlsanity.com/paper/2305.14065/) (2023)
- [Personalized Dictionary Learning for Heterogeneous Datasets](https://mlsanity.com/paper/2305.15311/) (2023)
- [On the Stability of Nonlinear Receding Horizon Control: A Geometric Perspective](https://mlsanity.com/paper/2103.15010/) (2021)
- [Towards scientific discovery with dictionary learning: Extracting biological concepts from microscopy foundation models](https://mlsanity.com/paper/2412.16247/) (2024)
- [On the convergence of group-sparse autoencoders](https://mlsanity.com/paper/2102.07003/) (2021)
- [The Star Geometry of Critic-Based Regularizer Learning](https://mlsanity.com/paper/2408.16852/) (2024)
- [Mechanistic Interpretability with Sparse Autoencoder Neural Operators](https://mlsanity.com/paper/2509.03738/) (2025)
- [PolySAE: Modeling Feature Interactions in Sparse Autoencoders via Polynomial Decoding](https://mlsanity.com/paper/2602.01322/) (2026)
- [The Effect of SGD Batch Size on Autoencoder Learning: Sparsity, Sharpness, and Feature Learning](https://mlsanity.com/paper/2308.03215/) (2023)
- [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)
- [Evaluating Sparse Autoencoders: From Shallow Design to Matching Pursuit](https://mlsanity.com/paper/2506.05239/) (2025)
- [Structural Extensions of Basis Pursuit: Guarantees on Adversarial Robustness](https://mlsanity.com/paper/2205.08955/) (2022)
- [Learning unfolded networks with a cyclic group structure](https://mlsanity.com/paper/2211.09238/) (2022)
- [Learning Trees of ℓ0-Minimization Problems](https://mlsanity.com/paper/2302.02548/) (2023)

## Abstract (arXiv)

Sparse coding is a basic task in many fields including signal processing, neuroscience and machine learning where the goal is to learn a basis that enables a sparse representation of a given set of data, if one exists. Its standard formulation is as a non-convex optimization problem which is solved in practice by heuristics based on alternating minimization. Re- cent work has resulted in several algorithms for sparse coding with provable guarantees, but somewhat surprisingly these are outperformed by the simple alternating minimization heuristics. Here we give a general framework for understanding alternating minimization which we leverage to analyze existing heuristics and to design new ones also with provable guarantees. Some of these algorithms seem implementable on simple neural architectures, which was the original motivation of Olshausen and Field (1997a) in introducing sparse coding. We also give the first efficient algorithm for sparse coding that works almost up to the information theoretic limit for sparse recovery on incoherent dictionaries. All previous algorithms that approached or surpassed this limit run in time exponential in some natural parameter. Finally, our algorithms improve upon the sample complexity of existing approaches. We believe that our analysis framework will have applications in other settings where simple iterative algorithms are used.