Exact Recovery of Sparsely-Used Dictionaries

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.

References in corpus (3)

• Convex Sparse Matrix Factorizations
• On the Local Correctness of L^1 Minimization for Dictionary Learning
• Matrix sparsification and the sparse null space problem

Cited by in corpus (33)

• Non-convex Optimization for Machine Learning
• Bilinear Generalized Approximate Message Passing
• Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
• Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Method
• Phase transitions and sample complexity in Bayes-optimal matrix factorization
• On the Identifiability of Overcomplete Dictionaries via the Minimisation Principle Underlying K-SVD
• Innovation Pursuit: A New Approach to Subspace Clustering
• Efficient Sum of Outer Products Dictionary Learning (SOUP-DIL) and Its Application to Inverse Problems
• Noisy Matrix Completion under Sparse Factor Models
• Bilinear Recovery using Adaptive Vector-AMP
• From Symmetry to Geometry: Tractable Nonconvex Problems
• Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent
• Unsupervised Congestion Status Identification Using LMP Data
• Greedy Deep Dictionary Learning
• When are Overcomplete Topic Models Identifiable? Uniqueness of Tensor Tucker Decompositions with Structured Sparsity
• Fast Orthonormal Sparsifying Transforms Based on Householder Reflectors
• Dictionary Learning from Incomplete Data
• Dictionary Learning with BLOTLESS Update
• Complete Dictionary Learning via ${\ell }^4$-Norm Maximization over the Orthogonal Group
• Dual Principal Component Pursuit
• Efficient Sparse Coding using Hierarchical Riemannian Pursuit
• Conditions for Existence of Dual Certificates in Rank-One Semidefinite Problems
• Forward Super-Resolution: How Can GANs Learn Hierarchical Generative Models for Real-World Distributions
• Alternating minimization for dictionary learning: Local Convergence Guarantees
• Noisy Inductive Matrix Completion Under Sparse Factor Models
• An Incidence Geometry approach to Dictionary Learning
• Spectral Sparse Representation for Clustering: Evolved from PCA, K-means, Laplacian Eigenmap, and Ratio Cut
• Finding a low-rank basis in a matrix subspace
• Combinatorial rigidity of Incidence systems and Application to Dictionary learning
• Approximate Guarantees for Dictionary Learning
• Compressed Factorization: Fast and Accurate Low-Rank Factorization of Compressively-Sensed Data
• Sparse Illumination Learning and Transfer for Single-Sample Face Recognition with Image Corruption and Misalignment
• Learning Semidefinite Regularizers