Sparse and spurious: dictionary learning with noise and outliers
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, noisy signals, and possible outliers, 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.
Code (0)
등록된 구현이 없습니다.
Tasks
Dictionary LearningSimilar Papers 제목 키워드 기반
Robust Non-Linear Matrix Factorization for Dictionary Learning, Denoising, and Clustering
Low dimensional nonlinear structure abounds in datasets across computer vision and machine learning. Kernelized matrix factorization techniques have recently been proposed to learn these nonlinear structures for denoisin…
ClusteringDenoisingDictionary LearningImputationLearning Hybrid Representation by Robust Dictionary Learning in Factorized Compressed Space
In this paper, we investigate the robust dictionary learning (DL) to discover the hybrid salient low-rank and sparse representation in a factorized compressed space. A Joint Robust Factorization and Projective Dictionary…
Dictionary LearningRobust Dictionary based Data Representation
The robustness to noise and outliers is an important issue in linear representation in real applications. We focus on the problem that samples are grossly corrupted, which is also the 'sample specific' corruptions proble…
Learning a collaborative multiscale dictionary based on robust empirical mode decomposition
Dictionary learning is a challenge topic in many image processing areas. The basic goal is to learn a sparse representation from an overcomplete basis set. Due to combining the advantages of generic multiscale representa…
ClusteringDenoisingDictionary LearningImage DenoisingUnderstanding l4-based Dictionary Learning: Interpretation, Stability, and Robustness
Recently, the $\ell^4$-norm maximization has been proposed to solve the sparse dictionary learning (SDL) problem. The simple MSP (matching, stretching, and projection) algorithm proposed by \cite{zhai2019a} has proved su…
Dictionary Learning