Local stability and robustness of sparse dictionary learning in the presence of noise
Rodolphe Jenatton∗,⋆ Rémi Gribonval† Francis Bach∘
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.
中文速览
稀疏字典学习（sparse dictionary learning）是一种把信号表示为字典原子稀疏线性组合的主流方法，但其核心优化问题是非凸的，人们一直不清楚算法找到的局部最小值是否真的接近生成信号的"真实字典"。这篇论文在一个概率生成模型下严格证明了：当信号由真实字典加噪声生成时，稀疏编码的目标函数以高概率在真实字典的邻域内存在一个局部最小值，从而为算法的可识别性提供了理论保障。与前人工作相比，该分析同时处理了过完备字典（原子数多于信号维度）和含噪信号这两种更贴近实际的情形，并给出非渐近的定量刻画，说明噪声水平、字典相干性、稀疏度、信号数量等关键参数如何共同影响识别成功的概率。这一结果填补了稀疏编码理论分析的重要空白，为理解非凸字典学习算法何时能够收敛到有意义的解提供了坚实的数学基础。
原文 arXiv:1210.0685;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1210.0685v1