英语原文共 12 页，剩余内容已隐藏，支付完成后下载完整资料
K-SVD:一种用于稀疏表示的超完备字典设计算法
摘要
近年来，人们对稀疏表示的信号的研究越来越感兴趣。
使用包含标准信号原子的超完备字典，信号由这些原子的稀疏线性组合来描述。
使用稀疏表示的应用程序很多，包括压缩，逆问题中的正则化，特征提取等等。
最近在这个领域的活动主要集中在对给定的字典的前提下分解信号追踪算法的研究上。
设计字典以更好地适应上述模型可以通过从预先指定的一组线性变换中选择一个字典或使字典适应一组训练信号来完成。
虽然这两种技术都已经考虑过了，但这个话题在很大程度上仍然是开放的。
在本文中，我们提出了一种新颖的字典自适应算法，以实现稀疏信号表示。
给定一组训练信号，我们在严格的稀疏约束条件下寻找能够为此集合中每个成员提供最佳表示的字典。
我们提出了一种新的方法—K-SVD算法—推广K均值聚类过程。
K-SVD是一种迭代方法，在基于当前字典的示例的稀疏编码和更新字典原子以更好地适合数据的过程之间交替。
字典列的更新与稀疏表示的更新相结合，从而加速收敛。
K-SVD算法是灵活的，并且可以用于任何追求方法（例如基础追求，FOCUSS或匹配追求）。
我们分析这个算法，并在合成测试和实际图像数据应用上展示其结果。
- 介绍
- 信号的稀疏表示
近年目睹了在寻找稀疏信号上日益浓厚的兴趣。
使用包含K个原子信号原子的过完备字典矩阵，可以将信号y表示为这些原子的稀疏线性组合。
y的表示可以是精确的或近似的，满足。
矢量包含信号y的表示系数。
在近似方法中，用于测量偏差的典型准则是p = 1,2和的范数。
在本文中，我们将集中讨论p = 2的情况。
如果和D是一个满秩矩阵，则表示问题可以有无数个解，因此必须设置解决方案的约束条件。
具有最少数量的非零系数的解决方案当然是一个吸引人的表示。
这个最稀少的表示是解决方案
或
其中是范数，计算向量的非零条目。
可以从稀疏性和过度完备性概念（共同或单独）中受益的应用程序包括压缩，逆问题中的正则化，特征提取等等。
的确，JPEG2000编码标准的成功可归因于自然图像小波系数的稀疏性[1]。
在去噪中，利用过度完备表示的小波方法和平移不变变量是该任务中最有效的已知算法[2] - [5]。稀疏性和过度完备性已成功用于图像动态范围压缩[6]，图像中纹理和动画内容的分离[7]，[8]，修复[9]等。
最稀疏表示的提取是一个在过去几年被广泛研究的难题。
我们在第二部分回顾一些最流行的方法。
在所有这些方法中，都有一个初步假设，即字典是已知的并且是固定的。
在本文中，我们解决设计适当字典的问题，以便更好地适应所实施的稀疏模型。
- 字典的选择
导致稀疏表示的完整字典D可以选择为预定义的一组函数，也可以通过调整其内容以适合给定的一组信号示例进行设计。
选择预先指定的变换矩阵很优选，因为它更简单。
而且，在许多情况下，它引导用于评估稀疏表示的简单快速的算法。
对于过完备的小波，曲波，轮廓线，可控小波滤波器，短时傅里叶变换等等的确如此。
通常优先考虑可以很容易被伪逆转的紧框架。
这些字典在应用中的成功取决于他们如何适当地描述所讨论的信号。
具有定向基函数和移位不变性质的多尺度分析是这种结构中的指导原则。
在本文中，我们考虑基于学习设计词典D的不同路线。
我们的目标是找到由训练信号生成稀疏表示的字典D。
我们相信这些字典有可能超越常用的预定字典。
随着计算能力的不断增长，计算成本可能变得次要，因为通过适应特定类别信号的字典的方法可以实现改进的性能。
- 这篇文章的贡献和结构
在本文中，我们提出了一种新颖的词典适应算法，以便稀疏地表示信号。
给定一组训练信号，我们寻找能够为严格稀疏约束条件下的每个成员提供最佳表示的字典D。
我们介绍了解决上述任务的K-SVD算法，推广了K-means算法。
K-SVD是一种迭代方法，它在基于当前字典的示例的稀疏编码和字典原子的更新过程之间进行交替，以便更好地适合数据。
字典列的更新与更新与其相关的稀疏表示系数一起完成，导致加速收敛。
K-SVD算法是灵活的，可以与任何追求方法一起工作，从而根据应用程序定制字典。
在本文中，我们介绍K-SVD算法，分析它，讨论它与之的关系
现有技术，并证明其优越的性能。
我们在合成测试和涉及的应用中演示K-SVD结果
真实的图像数据。
在第二节中，我们调查了K-SVD后来使用的追踪算法，以及一些最近的理论结果证明了它们用于稀疏编码。
在第三节中，我们提到最近在稀疏表示字典设计领域所做的工作，并描述了所提出的不同算法
这个任务。
在第四节中，我们描述了我们的算法，其可能的变化，以及它与以前提出的方法的关系。
第五部分介绍了合成数据的K-SVD结果，第六部分给出了一些涉及实际图像数据的初步应用。
我们在第七节中总结和讨论未来可能的研究方向。
- 现有技术的稀疏编码
稀疏编码是基于给定信号y和字典D计算表示系数x的过程。
这个过程通常称为“原子分解”，需要求解（1）或（2），这通常是通过寻找近似解的“追踪算法”来完成的。
在本节中，我们简要讨论几种这样的算法及其成功的前景。这些方法的更详细的描述可以在[10]中找到。
稀疏编码是本文后面我们开发的K-SVD方法中的一个必要阶段，因此重要的是对实现它的方法有一个很好的概述。
对最稀疏表示的精确确定证明是一个NP难题[11]。
因此，相反地考虑近似解，并且在过去的十年左右，已经提出了几种有效的追踪算法。
最简单的是匹配追踪（MP）[12]和正交匹配追踪（OMP）算法[13] - [16]。
这些是贪婪的算法，依次选择字典和原子。
这些方法非常简单，涉及信号和字典列之间的内积计算，并可能部署一些最小二乘法求解器。通过改变算法的停止规则，（1）和（2）都很容易解决。
第二个众所周知的追求方法是基础追求（BP）[17]。
它建议通过用范数替换范数来凸显（1）和（2）中提出的问题。
焦点欠定系统求解器（FOCUSS）非常相似，它使用范数来代替范数 [18] -[21]。
因此，与真实稀疏度量的相似性更好，但总体问题变为非凸性，导致局部最小值，这可能会在寻找解决方案时产生误导。
使用拉格朗日乘子将约束转换为惩罚项，并且基于迭代重新加权最小二乘的想法导出迭代方法，其将范数作为加权范数来处理。
BP和FOCUSS都可以基于最大后验（MAP）估计来激励，事实上，一些作品直接使用了这种推理[22] - [25]。 MAP可用于通过最大化将系数估计为随机变量
后部。
假设系数向量上的先验分布是有利于稀疏性的超高斯独立同分布。
对于拉普拉斯分布，这种方法相当于BP [22]。
近年来对这些算法的大量研究已经证实，如果寻求的解决方案x足够稀疏，这些技术在确切的情况下可以很好地恢复[16]，[26] - [30]。
进一步的工作考虑了近似的版本，并已显示[31]，[32]恢复x的稳定性。
最近的活动前沿在概率设置中重新讨论这些问题，获得更加真实的追踪算法性能和成功评估[33] - [35]。
字典D的属性设置了系数向量的稀疏性的限制，从而导致其成功的评估。
- 现有技术的字典设计
我们现在来看这篇文章的主题，即基于一系列例子的词典训练。
给定这样一个集合，我们假设存在一个字典D，它通过稀疏组合产生了给定的信号示例，即我们假设存在D，所以对每个示例的求解（）给出一个稀疏表示。
在这个设置中，我们问什么是正确的字典D。
- K均值聚类过程的归纳
在稀疏表示和聚类（即矢量量化）之间有一种有趣的关系。
这种联系以前在几份报告[36] - [38]中已经提到过。
在聚类中，学习一组描述向量，每个样本由其中一个向量表示（最靠近它的一个向量，通常在距离度量中）。
我们可以认为这是一个极端稀疏表示，在
信号分解中只允许有一个原子，而且系数乘以它必须是1。
有一种矢量量化（VQ）编码方法的变体，称为增益形状VQ，其中该系数允许变化[39]。
相反，在本文讨论的稀疏表示中，每个示例都表示为几个向量的线性组合。
因此，稀疏表示可以被称为聚类问题的泛化。
由于K-means算法（也称为广义Lloyd算法-GLA [39]）是矢量量化设置中训练最常用的过程，因此在转向解决字典训练问题时考虑该算法的推广是自然而然的。
聚类问题及其解决方案将在第IV-A节中更详细地讨论，因为我们的工作通过概括K-means来解决字典训练问题。
这里我们将简要地提一下K-means过程每次迭代应用两个步骤：
- 给定，将训练样例分配给最近的邻居;和ii）给定该任务，更新x以更好地适合示例。
到目前为止，已经尝试过的字典设计方法非常符合上述的两步过程。
第一步找到给出字典的系数 - 我们称之为“稀疏编码”的一个步骤。
然后，假定已知和固定的系数，字典被更新。
已经提出的各种算法之间的差异在于用于计算系数的方法和用于修改字典的过程中。
- 最大似然法
文献[22] - [25]中报道的方法在概率论推理D中使用概率推理。
提出的模型表明，对于每个例子y的关系
适用于具有方差x的稀疏表示和高斯白色残差向量v。
给定示例，这些作品考虑似然函数并寻找使其最大化的字典。
需要进行两项假设才能继续进行：第一，测量是独立绘制的，很容易提供
第二个假设是关键的，并且指的是“隐藏变量”x。
似然函数的成分使用关系计算
回到（3）中的初始假设，我们有
表示向量x的先验分布被假定为使得其条目x是零均值的独立同分布，具有Cauchy [24]或拉普拉斯分布[22]，[23]。
假设例如拉普拉斯分布，我们得到
这种整合很难评估，事实上，奥尔斯豪森和菲尔德[23]用x的极值来代替它。
整体问题变成了
这个问题不会惩罚D的条目，因为它与x的条目相同。
因此，解决方案将倾向于增加字典条目的值，以便使系数变得更接近零。
通过限制每个基本元素的l范数来处理这个困难，以便系数的输出方差保持在适当的水平[24]。
提出了一种迭代方法来解决（8）。 它在每次迭代中包括两个主要步骤：i）使用简单梯度下降程序计算系数x，然后ii）使用[24]更新字典
之前提到的迭代精化思想作为K均值算法的推广，后来被其他研究人员再次使用，并有一些变化[36,37,48,48]。
Lewicki和Sejnowski [25]提出了一种处理（7）中的积分的不同方法。
他们将后验估计为高斯，从而实现了集成的分析解决方案。
这允许客观比较不同的图像模型（基础或先验）。
它还消除了执行规范约束的附加重新缩放的需要。然而，这种模式在描述预期的真实行为方面可能过于有限。
这种技术和密切相关的技术被称为近似ML技术[37]。
上述方法和独立分量分析（ICA）算法之间有一个有趣的关系[43]。
后者处理完整字典的情况（元素的数量等于维度），而不假设加性噪声。
上述方法与ICA类似，因为该算法可以解释为试图最大化输入（采样）和输出（系数）之间的互信息[24,22,25]。
- MOD方法
Engan等人提出了一种吸引人的词典训练算法，称为最优方向法（MOD）。[36]，
[40]，[41]。 该方法更贴近K均值提纲，使用OMP或FOCUSS进行稀疏编码，然后更新字典。
MOD方法的主要贡献是更新字典的简单方法。
假设每个例子的稀疏编码是已知的，我们定义错误。 整体表示均方误差由下式给出
在这里，我们将所有例子连接为矩阵Y的列，并类似地收集表示系数向量以构建矩阵X。
符号代表Frobenius范数，定义为。
假设X是固定的，我们可以寻求对D的更新，以使上述误差最小化。
将（10）的导数相对于D，我们得到关系，导致
MOD与Olshausen和Field的工作密切相关，在稀疏编码和字典更新阶段都有所改进。
鉴于[23]，[24]和[22]中的工作采用最速下降来评估，那么使用OMP或FOCUSS就可以更高效地评估这
全文共12134字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[12291]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
