A Clustering Approach to Learn Sparsely-Used Overcomplete Dictionaries

Abstract

We consider the problem of learning overcomplete dictionaries in the context of sparse coding, where each sample selects a sparse subset of dictionary elements. Our main result is a strategy to approximately recover the unknown dictionary using an efficient algorithm. Our algorithm is a clustering-style procedure, where each cluster is used to estimate a dictionary element. The resulting solution can often be further cleaned up to obtain a high accuracy estimate, and we provide one simple scenario where ${\ell }_1$-regularized regression can be used for such a second stage.

Part of this work appears in COLT 2014

References in corpus (4)

• A Spectral Algorithm for Latent Dirichlet Allocation
• A Practical Algorithm for Topic Modeling with Provable Guarantees
• Local stability and robustness of sparse dictionary learning in the presence of noise
• When are Overcomplete Topic Models Identifiable? Uniqueness of Tensor Tucker Decompositions with Structured Sparsity

Cited by in corpus (14)

• Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
• Phase transitions and sample complexity in Bayes-optimal matrix factorization
• When Are Nonconvex Problems Not Scary?
• Simple, Efficient, and Neural Algorithms for Sparse Coding
• New Algorithms for Learning Incoherent and Overcomplete Dictionaries
• A Unified Framework for Identifiability Analysis in Bilinear Inverse Problems with Applications to Subspace and Sparsity Models
• A General Framework for Bayes Structured Linear Models
• Minimax Lower Bounds on Dictionary Learning for Tensor Data
• Local Identification of Overcomplete Dictionaries
• Convolutional Phase Retrieval via Gradient Descent
• Performance Limits of Dictionary Learning for Sparse Coding
• Unique Sharp Local Minimum in ${\ell }_1$-minimization Complete Dictionary Learning
• Alternating minimization for dictionary learning: Local Convergence Guarantees
• Combinatorial rigidity of Incidence systems and Application to Dictionary learning