稀疏表示入门_稀疏表示的发展

1.稀疏学习学什么

稀疏学习的任务主要是有稀疏编码、字典学习。

关于稀疏信号的定义，这里给出4种形式：严格k稀疏信号，可压缩信号、稀疏基下的稀疏信号、稀疏基下的可压缩信号

（1）严格k稀疏信号：考虑一个有限长信号x属于Rⁿ，如果x至多有k个非零元素，即||x||₀≤k，则称信号x为严格k稀疏信号，

（2）可压缩信号：如果信号可以用一个k稀疏向量来近似表示，则称这样的信号为可压缩信号。

（3）稀疏基下的稀疏信号：大多数的情况下，信号本身不是稀疏的，但是在某些合适的基或变换下稀疏。

（4）稀疏基下的可压缩信号：给定值k，信号x的最佳近似k项元素的线性组合，称为x的最佳k稀疏近似。

字典的概念：字典A来自信号空间的元素集，其线性组合可以表示或近似表示信号。在我们经常关注的稀疏学习任务中，往往要求字典是一个扁矩阵，也称为过完备字典。

2.稀疏编码

稀疏编码的概念来自于神经生物学。生物学家提出，哺乳类动物在长期的进化中，生成了能够快速，准确，低代价地表示自然图像的视觉神经方面的能力。我们直观地可以想象，我们的眼睛每看到的一副画面都是上亿像素的，而每一副图像我们都只用很少的代价重建与存储。我们把它叫做稀疏编码，即Sparse Coding.

稀疏编码的目的是在大量的数据集中，选取很小部分作为元素来重建新的数据。

稀疏编码难点之一是其最优化目标函数的求解。

哺乳动物初级视觉皮层简单细胞的感受野的三个性质：1.空间局部化、方向性和带通特性。

X为一个n为特征向量，可以是一个小波信号，可以是一副图片等。

D为标准化的基础矩阵，由组成元素的基本原子构成，也称为字典。在信号中可以是不同频率的波形，在图像中可以是构成图像的基本边，角。

X可以由D中和少量原子线性组合而成，及其表示系数为稀疏。如下：

数学模型

引出稀疏表示的两个基本要求，1是尽可能与原特征相似，2是系数为稀疏。

上式中，我们要求p>m，根据线性代数的知识我们知道，稀疏系数有无穷多组的解。根据稀疏的条件，我们可以在所有的可行解中挑出非零元素最少的解，也就是满足稀疏性。于是得到如下的数学模型：

如果再考虑噪声的话，就得到如下的模型：

目标函数中为零范数约束，是NP难题。

有人做了一个证明，在一定条件下，上述的最优化问题有唯一的解。

Terry tao又证明了，在满足一定条件下，零范数问题与一范数问题是等价的。于是上述模型转化为：

基于上面的思想，还有各种不同版本的数学模型。

常见模型

我们知道上式为非凸优化问题，常用的解法有：greedy algorithm，代表有Matching Pursuit, Orthogonal Matching Pursuit

上式为解不等式约束问题，常用的解法：LASSO

再写成拉格朗日乘子的形式，如果已知lambda，可用soft thresholding方法，常见的还有coordinate descent, Bregman Iteration等；

如果未知lambda，则用Homotopy.

稀疏表示

一、

1、先来考虑这么一个问题：有一个信号y，假设它是mx1维的，我们现在得到了n个这样的信号（设m<<n），也可理解为对这个信号采样n次，于是我们把这n个不同的信号从1到n依次排开，就得到了一个m行n列的矩阵，记为A吧。

2、然后呢，假设我们得到了一个新的y，也就是又重新采了一次样得到y，我们可以认为矩阵A里面的信号可以估计这个新的信号y，因为A就是由不同的采样信号y组成嘛，当然可以估计这个新的信号y啦。那么如何估计呢，我们不妨设这个新的信号y是矩阵A中各个信号的线性组合，不一定全部包含A中的每一列哈，可以理解为A中有太多的这样的信号啦，我们只去其中的一部分就可以足够来表示这个新信号y啦。

3、有了上面这些信息，我们可以表示为这样：给定一个mx1的向量y，和一个mxn的矩阵A，求一个nx1向量x，使得方程y=Ax。简单吧。

这个问题很简单的一个求法就是两边同时乘以A’（A的转置），然后移项（就是两边在同时乘以A’A的逆。于是得到方程的解x=(A^TA)^-1A^T。。（这个方法得到的是最小二乘解，应该是这么叫吧。。为什么是这样网上查一下吧）。

我们用这种放法得到解x当然是正确的。可是很有可能x向量中n个元素全是非0的。所以稀疏的问题就来了，我们能不能求一个x使它中的元素非零项的个数很少呢，比如过我要求里面只有n个里面只有5个非零项（这就是x的稀疏性为5）？就是我们想要得到A中最能表示新信号y的那几项，其他的都可以省略掉。为什么非要找最少的表示啊，多麻烦，直接解出来x就不好了啊，多简单。我这么想的，如果让你完成一件事情，需要借很多东西完成它，我可以只像10个人借就可以完成，也可以像100个人借东西完成，你说哪一个办法好呢？用最少的资源获得最大的收益哈。

4、怎么可以解得这个最少非零项的解呢？有问题，就必然有解决方法。我们不用上面的直接解方程了。我们来看另一种方法：

我们这样来想，有一组向量OA,OB,OC,OD。我们想要OA用OB,OC,OD来表示，学过线性代数的人都知道怎么解吧。我们换另一种方法来解，如图示

（1）先找到OA到其他各个向量的投影，找投影最大的那个对应的向量，图途中OB，那么OA就可表示成OA=OM+MA，这里为向量运算。假设OM和OB的长度比值为a，则OA=a（OB）+MA。嘿嘿有第一个表示向量了。如果求出来MA就搞定了，MA成为残差吧

（2）MA怎么求呢。和第一步一样，我们找MA到各个向量的投影，取最大的向量，比比如说找到了OC如右图，同样MA可以表示为MA=OA’=ON+NA’，假设ON和OC的长度比为b则MA=b（OC）+NA’.只要再求NA’就可以了。

（3）这样一直循环求，可以证明残差是不断减小的（证明网上去找吧），

（4）不妨让残差小于一定阈值的时候，我们就认为他们可以表示这个未知向量了。这样求出来了就是一个非零项较少的表示啦。比如我们认为这步骤（1）（2）两次就可以满足条件啦，如图3中蓝色线所示，那么我们最终得到向量为OM+ON+NA’=OM+MO’+O’A=OA，如果忽略残差NA’（因为她很小），则有OA≈OO’=a(OB)+b(OC)。于是OA就可以用OB和OC表示了，而不是全部向量来表示OA。这就是稀疏表示了。

上面的这个算法就是追踪算法，即MP算法。简单吧。MP算法不是最优的，得到的解是次优解。因为上图中，第（2）部的时候得到的NA’残差只是和OC垂直的，并不和OB垂直，这里是二维的情况。至于为什么请看它的改进算法OMP算法，就是每一次找最相似向量的时候要将已经找到的向量正交化。

矩阵A称为字典（大概是因为就像查字典一样吧，我想找到y，我就查这个A字典，A是一个过完备基，就是它包含了y像要的信息，那么怎么查呢，就是找到x，不妨认为x是页码吧，所以只要给定了这个字典A，然后再给我们一个字y，我们就能查到y在A中的页码x）。

二、

如果认为稀疏表示就是上面介绍的那么简单，那就太小看所遇到的问题了。还有一个问题，如何建立这个词典A呢，绝对不是上面举得那个简单的例子通过简单的采样得到。例如：给定一组信号y，如何建立一个词典A，使得每一个信号y的表示x最稀疏。这就是字典学习问题。

这个问题的解决办法目前有三种

efficient sparsecoding algorithm NIPS 06;

K-SVD tsp 06;

Online dictionary learning for sparse coding,ICML 09 & JMLR 10

http://blog.sina.com.cn/s/blog_6d0e97bb01015wol.html

http://blog.csdn.net/aichipmunk/article/details/8823537

http://blog.csdn.net/AIchipmunk/article/details/8712384

http://blog.csdn.net/scucj/article/details/7467955