# On the Computational Intractability of Exact and Approximate Dictionary Learning

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

## Key facts

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

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

- [Projecting Assumptions: The Duality Between Sparse Autoencoders and Concept Geometry](https://mlsanity.com/paper/2503.01822/) (2025)
- [Measuring Progress in Dictionary Learning for Language Model Interpretability with Board Game Models](https://mlsanity.com/paper/2408.00113/) (2024)
- [Mathematical Models of Computation in Superposition](https://mlsanity.com/paper/2408.05451/) (2024)
- [GaussianSpa: An "Optimizing-Sparsifying" Simplification Framework for Compact and High-Quality 3D Gaussian Splatting](https://mlsanity.com/paper/2411.06019/) (2024)
- [SPEAR:Exact Gradient Inversion of Batches in Federated Learning](https://mlsanity.com/paper/2403.03945/) (2024)
- [Function Encoders: A Principled Approach to Transfer Learning in Hilbert Spaces](https://mlsanity.com/paper/2501.18373/) (2025)
- [Unboxing the Black Box: Mechanistic Interpretability for Algorithmic Understanding of Neural Networks](https://mlsanity.com/paper/2511.19265/) (2025)
- [Unsupervised Opinion Summarization Using Approximate Geodesics](https://mlsanity.com/paper/2209.07496/) (2022)
- [Towards Worst-Case Guarantees with Scale-Aware Interpretability](https://mlsanity.com/paper/2602.05184/) (2026)
- [Deep learning based dictionary learning and tomographic image reconstruction](https://mlsanity.com/paper/2108.11730/) (2021)
- [Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment](https://mlsanity.com/paper/2110.11420/) (2021)
- [Convergence of alternating minimisation algorithms for dictionary learning](https://mlsanity.com/paper/2304.01768/) (2023)
- [An iterative coordinate descent algorithm to compute sparse low-rank approximations](https://mlsanity.com/paper/2107.14608/) (2021)
- [Inversion of Magnetic Data using Learned Dictionaries and Scale Space](https://mlsanity.com/paper/2502.05451/) (2025)

## Abstract (arXiv)

The efficient sparse coding and reconstruction of signal vectors via linear observations has received a tremendous amount of attention over the last decade. In this context, the automated learning of a suitable basis or overcomplete dictionary from training data sets of certain signal classes for use in sparse representations has turned out to be of particular importance regarding practical signal processing applications. Most popular dictionary learning algorithms involve NP-hard sparse recovery problems in each iteration, which may give some indication about the complexity of dictionary learning but does not constitute an actual proof of computational intractability. In this technical note, we show that learning a dictionary with which a given set of training signals can be represented as sparsely as possible is indeed NP-hard. Moreover, we also establish hardness of approximating the solution to within large factors of the optimal sparsity level. Furthermore, we give NP-hardness and non-approximability results for a recent dictionary learning variation called the sensor permutation problem. Along the way, we also obtain a new non-approximability result for the classical sparse recovery problem from compressed sensing.