K-SVD : An Algorithm for Designing of Overcomplete Dictionaries for Sparse Representation
K-SVD : An Algorithm for Designing of Overcomplete Dictionaries for Sparse Representation
复制标题
DOI：
--
复制
发表时间：
2005
影响因子：
6.8
通讯作者：
M. Aharon;Michael Elad;A. Bruckstein;Y. Katz
中科院分区：
文献类型：
--
作者：
M. Aharon;Michael Elad;A. Bruckstein;Y. Katz
近年来，人们对信号稀疏表示的研究越来越感兴趣。使用包含原型信号原子的过完备字典，通过这些原子的稀疏线性组合来描述信号。使用稀疏表示的应用有很多，包括压缩、逆问题中的正则化、特征提取等等。最近在这一领域的活动主要集中在研究的追求算法，分解信号相对于一个给定的字典。设计字典以更好地拟合上述模型可以通过从预先指定的线性变换集合中选择一个来完成，或者通过使字典适应一组训练信号来完成。这两种技术都被考虑过，但这个话题在很大程度上仍然是开放的。在本文中，我们提出了一种新的算法，以适应字典，以实现稀疏信号表示。给定一组训练信号，我们在严格的稀疏性约束下，寻找导致该集合中每个成员的最佳表示的字典。我们提出了一种新的方法-K-SVD算法-推广的K-Means聚类过程。K-SVD是一种迭代方法，它在基于当前字典的示例稀疏编码和更新字典原子以更好地适应数据的过程之间交替。字典列的更新与稀疏表示的更新相结合，从而加速收敛。K-SVD算法是灵活的，并且可以与任何追踪方法（例如，基本追踪、FOOLS或匹配追踪）。我们分析了该算法，并证明了它的合成测试和应用在真实的图像数据的结果。
In recent years there has been a growing interest in the study of sparse representation of signals. Using an overcomplete dictionary that contains prototype signal-atoms, signals are described by sparse linear combinations of these atoms. Applications that use sparse representation are many and include compression, regularization in inverse problems, feature extraction, and more. Recent activity in this field concentrated mainly on the study of pursuit algorithms that decompose signals with respect to a given dictionary. Designing dictionaries to better fit the above model can be done by either selecting one from a pre-specified set of linear transforms, or by adapting the dictionary to a set of training signals. Both these techniques have been considered, but this topic is largely still open. In this paper we propose a novel algorithm for adapting dictionaries in order to achieve sparse signal representations. Given a set of training signals, we seek the dictionary that leads to the best representation for each member in this set, under strict sparsity constraints. We present a new method – the K-SVD algorithm – generalizing the K-Means clustering process. K-SVD is an iterative method that alternates between sparse coding of the examples based on the current dictionary, and a process of updating the dictionary atoms to better fit the data. The update of the dictionary columns is combined with an update of the sparse representations, thereby accelerating convergence. The K-SVD algorithm is flexible and can work with any pursuit method (e.g., basis pursuit, FOCUSS, or matching pursuit). We analyze this algorithm and demonstrate its results on both synthetic tests and in applications on real image data.