Exact Recovery of Sparsely-Used Dictionaries

2012/06/26 by Daniel A. Spielman, Huan Wang, Spielman, Daniel A. +3 · 2 citations
Computer Science · Engineering · #Blind Source Separation Techniques #FOS: Computer and information sciences #Geophysical Methods and Applications #Information Theory (cs.IT) #Machine Learning (cs.LG) #Sparse and Compressive Sensing Techniques

paper · pdf · doi:10.48550/arxiv.1206.5882

openalex publication_date 2012/06/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider the problem of learning sparsely used dictionaries with an arbitrary square dictionary and a random, sparse coefficient matrix. We prove that O (n log n) samples are sufficient to uniquely determine the coefficient matrix. Based on this proof, we design a polynomial-time algorithm, called Exact Recovery of Sparsely-Used Dictionaries (ER-SpUD), and prove that it probably recovers the dictionary and coefficient matrix when the coefficient matrix is sufficiently sparse. Simulation results show that ER-SpUD reveals the true dictionary as well as the coefficients with probability higher than many state-of-the-art algorithms.

Citations

• From Sparse Solutions of Systems of Equations to Sparse Modeling of Signals and Images
• rm K-SVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation
• Matrix sparsification and the sparse null space problem

Cited by

• Noisy Inductive Matrix Completion Under Sparse Factor Models
• Approximate Guarantees for Dictionary Learning

Related

• Towards Learning Sparsely Used Dictionaries with Arbitrary Supports
• New Algorithms for Learning Incoherent and Overcomplete Dictionaries
• A note on the sample complexity of the Er-SpUD algorithm by Spielman, Wang and Wright for exact recovery of sparsely used dictionaries
• Dictionary Learning for the Almost-Linear Sparsity Regime
• A Clustering Approach to Learn Sparsely-Used Overcomplete Dictionaries