稀疏编码算法

‘壹’ 稀疏表示的性质

信号稀疏表示的目的就是在给定的超完备字典中用尽可能少的原子来表示信号，可以获得信号更为简洁的表示方式，从而使我们更容易地获取信号中所蕴含的信息，更方便进一步对信号进行加工处理，如压缩、编码等。信号稀疏表示方向的研究热点主要集中在稀疏分解算法、超完备原子字典、和稀疏表示的应用等方面。
在稀疏表示理论未提出前，正交字典和双正交字典因为其数学模型简单而被广泛的应用，然而他们有一个明显的缺点就是自适应能力差，不能灵活全面地表示信号，1993年，Mallat基于小波分析提出了信号可以用一个超完备字典进行表示，从而开启了稀疏表示的先河，经研究发现，信号经稀疏表示后，越稀疏则信号重建后的精度就越高，而且稀疏表示可以根据信号的自身特点自适应的选择合适的超完备字典。对信号稀疏表示的目的就是寻找一个自适应字典使得信号的表达最稀疏。
稀疏分解算法首先是由Mallat提出的，也就是众所周知的匹配追踪算法（Matching Pursuit,MP）算法，该算法是一个迭代算法，简单且易于实现，因此得到了广泛的应用。随后，Pati等人基于MP算法，提出了正交匹配追踪算法（Orthogonal Matching Pursuit,OMP），OMP算法相较于MP算法，收敛速度更快。在以后的研究中，为了改进OMP算法，学者也提出了各种不同的其它算法，例如：压缩采样匹配追踪（Conpressive Sampling Matching Pursuit,CoSaMP）算法、正则化正交匹配追踪（Regularized Orthogonal Matching Pursuit,ROMP）算法、分段式正交匹配追踪（Stagewise OMP,StOMP）算法、子空间追踪（Subspace Pursuit,SP）算法等等。
信号稀疏表示的两大主要任务就是字典的生成和信号的稀疏分解，对于字典的选择，一般有分析字典和学习字典两大类。常用的分析字典有小波字典、超完备DCT字典和曲波字典等，用分析字典进行信号的稀疏表示时，虽然简单易实现，但信号的表达形式单一且不具备自适应性；反之，学习字典的自适应能力强，能够更好的适应不同的图像数据，在目前的研究中，常用的学习字典的方法包括：Engan于1999年提出的最优方向（Method Of Optimal Directions,MOD）算法，该算法是学习字典的鼻祖，它的字典更新方式简单，但与此同时，它的收敛速度很慢，在该算法的基础上，一些研究人员同时还提出了一些其它的字典学习算法，如FOCUSS字典学习算法，广义PCA（Generalized PCA）算法等等，Micheal Elad也于2006年提出了基于超完备字典稀疏分解的K-SVD算法，该算法相较于MOD算法，收敛速度有了很大的提高，但是随着噪声的逐渐加大，使用该算法进行去噪后的图像因纹理细节的丢失会产生模糊的效果。Mairal于2010年提出了一种online字典学习算法，该算法速度较快且适用于一些特殊的信号处理，例如视频信号，语音信号等等 。

‘贰’ 稀疏自编码器出自哪个论文

出自AndrewNg教授的教程。
稀疏自编码器（SparseAutoencoder）可以自动从无标注数据中学习特征，可以给出比原始数据更好的特征描述。在实际运用时可以用稀疏编码器发现的特征取代原始数据，这样往往能带来更好的结果。本文将给出稀疏自编码器的算法描述，并演示说明稀疏编码器自动提取边缘特征。
稀疏性可以被简单地解释如下。如果当神经元的输出接近于1的时候我们认为它被激活，而输出接近于0的时候认为它被抑制，那么使得神经元大部分的时间都是被抑制的限制则被称作稀疏性限制。这里我们假设的神经元的激活函数是sigmoid函数。

‘叁’ KSVD去噪

      在解释KSVD去噪原理之前先解释几个名词，首先：

       原子：信号的基本李物构成成分，比如一个长为N的列向量；

       字典：许多原子的排序集合，一个N*T的矩阵，如果T>N（列数大于行数），则为过完备或冗余字典。信号稀疏之前在压缩感知学习的时候有介绍过，就是信号的非零值很少，这个概念主要应用与信号处理领域，自然信号中主要是低频信息，高频信息大多就是噪声了，在图像中应用滤波器滤除高频成分也就是去噪了。具体怎么完成，就要依靠下面介绍的KSVD。

       KSVD的目的就是找到最稀疏的稀疏矩阵X，使得原始矩阵（Y）有最稀疏的表示。假设现在有了一个N*T的过完备字典 D，一个要表示的对象y（要还原的图像），求一套系数x，使得y=Dx，这里y是一个已知的长为N的列向量，x是一个未知的长为T的列向量，解方程。这是一个T个未知数，N个方程的方程组，T>N，所以是有无穷多解，但是针对问题目标我们会给这个方程添加约束条件，比如在图像去噪中，我们想要x最稀疏，就是非零值最少，这个在已知D和y求解x的过程就是稀疏编码。

       稀疏编码求解的模型就是：x = argminxnorm(y − Dx, 2)2,  s.t.norm(x, 1)≤ε。这里又被分为了两种可能，D已知情况下可以用OMP算法（大意是先找到D和y最接近的一个原子D(m)，求出合适的系数x(m)，新的y'=D(m) * x(m)，再找下一个最接近的原子，直到找完合适的x）；当D未知时就变成了矩阵分解问题，比如MOD算法的路子：Sparse Coding和Dictionary Update，两步走，第一步固定D,更新x：x = argminxnorm(y − Ax, 2)2, s.t.norm(x, 1)≤k；第二步更新D: D = argminxnorm(y − Ax, 2)2很像EM算法。

       KSVD和MOD最大的不同就是K每次只更新D当中的一个原子，就是D矩阵当中的某一列，因为矩阵相乘可以看做是前一个矩阵的列向量分别乘后一个矩阵的行向量。Loss函数在这里可以进行转化：

      而SVD就用在对E的分解，和上面的MOD类似，也是迭代察扰皮进行就是每次更改D的原子。就比如败差说KSVD用于图像去噪的话，假如有一个零均值高斯白噪声，即 n ∼ N(0, σ) ，σ是噪声的标准差，有噪声的图像为 z = y + n ，目的是从信号 z 中恢复出原始无噪信号 y，通过最大后验概率，求得目标函数的解，即可恢复出y：x = argminx∥z−Dx∥22,   s.t.∥x∥0 ≤ T 。其中T依赖于 ε 和 σ 。为方便优化计算，实际操作中往往转化成： x = argminx∥z−Dx∥22+ μ∥x∥0选取恰当的μ可以让上面两式等价。

‘肆’ 稀疏编码的研究历史

1959年,David Hubel和Toresten Wiesel通过对猫的视觉条纹皮层简单细胞感受野的研究得出一个结论:主视皮层V1区神经元的感受野能对视觉感知信息产生一种“稀疏表示”。
1961年,H.B.Barlow[5]基于这一知识提出了“利用感知数据的冗余”进行编码的理论.
1969年,D.J.Willshaw和O.P.Buneman等人提出了基于Hebbian 学习的局部学习规则的稀疏表示模型.这种稀疏表示可以使模型之间有更少的冲突,从而使记忆能力最大化.Willshaw模型的提出表明了稀疏表示非常有利于学习神经网络中的联想.
1972年,Barlow推论出在稀疏性(Sparsity)和自然环境的统计特性之间必然存在某种联系.随后,有许多计算方法被提出来论证这个推论,这些方法都成功地表明了稀疏表示可以体现出在大脑中出现的自然环境的统计特性.
1987年,Field提出主视皮层V1区简单细胞的感受野非常适于学习视网膜成像的图像结构,因为它们可以产生图像的稀疏表示.基于这个结论,1988年,Michison明确提出了神经稀疏编码的概念,然后由牛津大学的E.T.Roll 等人正式引用.随后对灵长目动物视觉皮层和猫视觉皮层的电生理的实验报告,也进一步证实了视觉皮层复杂刺激的表达是采用稀疏编码原则的.
1989年,Field提出了稀疏分布式编码(Sparse Distributed Coding)方法.这种编码方法并不减少输入数据的维数,而是使响应于任一特殊输入信息的神经细胞数目被减少,信号的稀疏编码存在于细胞响应分布的四阶矩(即峭度Kurtosis)中.
1996年,Olshausen和Field在Nature杂志上发表了一篇重要论文指出,自然图像经过稀疏编码后得到的基函数类似于V1区简单细胞感受野的反应特性.这种稀疏编码模型提取的基函数首次成功地模拟了V1区简单细胞感受野的三个响应特性:空间域的局部性、时域和频域的方向性和选择性.考虑到基函数的超完备性(基函数维数大于输出神经元的个数),Olshausen 和Field在1997年又提出了一种超完备基的稀疏编码算法,利用基函数和系数的概率密度模型成功地建模了V1区简单细胞感受野.
1997年,Bell和Sejnowski 等人把多维独立分量分析(Independent Component Analysis, ICA)用于自然图像数据分析,并且得出一个重要结论:ICA实际上就是一种特殊的稀疏编码方法.
2014年，
21世纪以来,国外从事稀疏编码研究的人员又提出了许多新的稀疏编码算法,涌现出了大量的稀疏编码方面的论文,国内研究者在稀疏编码算法和应用方面也作了一些工作],但远远落后于国外研究者所取得的成果.