Local stability and robustness of sparse dictionary learning in the presence of noise

Abstract

A popular approach within the signal processing and machine learning communities consists in modelling signals as sparse linear combinations of atoms selected from a learned dictionary. While this paradigm has led to numerous empirical successes in various fields ranging from image to audio processing, there have only been a few theoretical arguments supporting these evidences. In particular, sparse coding, or sparse dictionary learning, relies on a non-convex procedure whose local minima have not been fully analyzed yet. In this paper, we consider a probabilistic model of sparse signals, and show that, with high probability, sparse coding admits a local minimum around the reference dictionary generating the signals. Our study takes into account the case of over-complete dictionaries and noisy signals, thus extending previous work limited to noiseless settings and/or under-complete dictionaries. The analysis we conduct is non-asymptotic and makes it possible to understand how the key quantities of the problem, such as the coherence or the level of noise, can scale with respect to the dimension of the signals, the number of atoms, the sparsity and the number of observations.

References in corpus (8)

• Spike and slab variable selection: Frequentist and Bayesian strategies
• On the conditions used to prove oracle results for the Lasso
• Proximal Methods for Hierarchical Sparse Coding
• Convex Sparse Matrix Factorizations
• The Sample Complexity of Dictionary Learning
• On the Local Correctness of L^1 Minimization for Dictionary Learning
• On the Sample Complexity of Predictive Sparse Coding
• A tail inequality for quadratic forms of subgaussian random vectors

Cited by in corpus (12)

• Phase transitions and sample complexity in Bayes-optimal matrix factorization
• On the Identifiability of Overcomplete Dictionaries via the Minimisation Principle Underlying K-SVD
• Noisy Matrix Completion under Sparse Factor Models
• Phase Diagram and Approximate Message Passing for Blind Calibration and Dictionary Learning
• A Clustering Approach to Learn Sparsely-Used Overcomplete Dictionaries
• Structured Dictionary Learning for Classification
• Local Identification of Overcomplete Dictionaries
• Fault Handling in Large Water Networks with Online Dictionary Learning
• Sample Complexity of Dictionary Learning and other Matrix Factorizations
• Sparse and spurious: dictionary learning with noise and outliers
• Metrics for Multivariate Dictionaries
• On the Reconstruction Risk of Convolutional Sparse Dictionary Learning