压缩感知中的lp球：p范数最优化为什么总会导致一个稀疏的解的原因（2） efficient, methods, wrong

yuyang911220

symmerize:

2-methods to methods:
1. L2-norm: quick, efficient, but get the wrong answer
2. L0-norm: precise but impractical
否定了L0范数和L2范数之后，我们想到取中——用L1范数（Basis pursuit的思路）。
so get select the L1-norm , that is the abs of each element

===============================

Basis Pursuit & RIP

Basis pursuit的方法在2000年由Candes-Romberg-Tao, Donoho提出，其基本思路见下图（以二维为例）：



从图中可见，L1-norm比L2-norm靠谱多了。从上图中可见，x*处，x的L1-norm最小，这样推广到n维向量x，就是其每一维的值的绝对值的和。
下面这个Theorem就是对L1-norm方案（Basis pursuit）可行性的定理（具体证明看论文吧）：大概是说，原始S-sparse的信号f为n维，从其中随机抽取m维分量，如果想利用Basis pursuit的方法把这m维向量重建出n维原始信号，只要满足m>cS*log(n)即可，其中c是一个常数。

以上都是采用lp球去解释问题，似乎看起来很直观，但我看了好久都没看明白，今天琢磨之后终于想明白了，接着往下说……
================正文================

在论文“戴琼海，付长军，季向阳.压缩感知研究[J].计算机学报，2011，34(3)：425-434.”（以下简称论文）中看了几遍没看明白，但看了Rachel_Zhang博客的文章“压缩感知进阶——有关稀疏矩阵”，虽然也没有看明白，但我得到了一个重要信息，这个图是在2维的情况下画出来的，下面就来详细解释一下。
下面的叙述以论文为框架，即如果提到式(1)指的是论文中的式(1)。
假定式(1)中的信号f是二维的，设f=[x1,x2]T(列向量，没法写转置，只能用T表示了)，f是稀疏的，经过φ变换得到y，y的维数肯定比x要小，这里假定了f是2维的，那么y只能是1维了（也就是一个数了，维数不能再低了），φ是一个1乘2的矩阵，设φ=[φ1,φ2]。
通过观测我们得到了y（也就是说y是一个已知常量），我们现在关心的是如果根据y重构稀疏信号f，文章中的式(2)和式(3)说明了这个问题：可以求0范数和p范数最优化的问题来重构信号f，为什么总可以得到f呢？然后作者就用lp球直观形象的解释了这个问题，得出结论：p<=1时可以得到唯一解（与直线交点在坐标轴上），p>1时的解将不准确（Rachel_Zhang的博客中用p=2说明了这时得到的结果是不准确的）。
我有几点不明白：一是为什么论文中的式(1)是一条直线？二是图2中的横轴和纵轴到底代表着什么？三是图2中的那些不同p值时是圆(p=2)还是菱形(p=1)是怎么得来的？四是两者的交点为什么一定要在坐标轴上？下面一一解答……
先说第一个问题：为什么论文中的式(1)是一条直线？
对于式(1)来说，在恢复信号f时，观测值y是一个常数（一维，即一个常数），矩阵φ是已知的，即它的两个元素φ1和φ2是两个常数，我们现在想要得到的是信号f中的两个元素x1和x2，因此把式(1)矩阵的形式写开即得到y=φ1*x1+φ2*x2，注意这里面x1和x2是未知量，其它三个量是常数，这时候如果以x1为横轴，以x2为纵轴(二维空间就是这样子的)，则式(1)的轨迹（可能取的值）画出来就是一条直线（一次函数嘛，只是一定要注意这时谁是常量谁是变量就OK了）。
到此为止第二个问题也就明白了，横轴是x1，纵轴是x2，即f的两个待求解的元素，不要被常见的x-y直角坐标系搞混了就行了。
再来说第三个问题：那些不同p值时是圆(p=2)还是菱形(p=1)是怎么得来的？
搞明白了第一个和第二个问题，第三个问题就简单了，对于式(3)来说（式(2)是一样子的），求解的x1和x2即要满足min ||f||p成立，也要受约束于式(1) y=φf，即也要保证式(1)成立，如要在一个坐标系中同时画出式(1)曲线和min||f||p曲线，要取它们的交点才行。p范数的公式论文里说了，这里因为信号是二维的，只有两个元素，因此||f||p=((x1)^p+(x2)^p)^(1/p)，前面说了x1和x2是待恢复信号f的两个元素，对于||f||p取不同值的时候，它在坐标系中的曲线是不一样子的，当取到某一个值的时候，它就与式(1)直线相交了（如图2所示一共画了||f||p取两种值的情况，实线时不相交，虚线时就有交点了），当然这个并不是一对一的函数，所以画起来比较麻烦，可以四个象限分开来画就容易理解了，比如只考虑第一象限的曲线形状，这时因为x1>0,x2>0所以理解起来容易多了，求出两者之间的表达式，在matlab里很容易画出来的，其它三个象限就是一个对称的关系罢了。
[plain] view plain copy

• %lp sphere  
• clear all;close all;clc;  
• p=0.5;c1=0.5;c2=1;  
• x1=linspace(0,c1,100);  
• y1=(c1^p-x1.^p).^(1/p);  
• x2=linspace(0,c2,100);  
• y2=(c2^p-x2.^p).^(1/p);  
• figure(1);  
• subplot(221);plot(x1,y1,x2,y2);title('p=0.5');  
• xlim([0 1.1]);  
• ylim([0 1.1]);  
• p=1.0;c1=0.5;c2=1;  
• x1=linspace(0,c1,100);  
• y1=(c1^p-x1.^p).^(1/p);  
• x2=linspace(0,c2,100);  
• y2=(c2^p-x2.^p).^(1/p);  
• figure(1);  
• subplot(222);plot(x1,y1,x2,y2);title('p=1.0');  
• xlim([0 1.1]);  
• ylim([0 1.1]);  
• p=1.5;c1=0.5;c2=1;  
• x1=linspace(0,c1,100);  
• y1=(c1^p-x1.^p).^(1/p);  
• x2=linspace(0,c2,100);  
• y2=(c2^p-x2.^p).^(1/p);  
• figure(1);  
• subplot(223);plot(x1,y1,x2,y2);title('p=1.5');  
• xlim([0 1.1]);  
• ylim([0 1.1]);  
• p=2.0;c1=0.5;c2=1;  
• x1=linspace(0,c1,100);  
• y1=(c1^p-x1.^p).^(1/p);  
• x2=linspace(0,c2,100);  
• y2=(c2^p-x2.^p).^(1/p);  
• figure(1);  
• subplot(224);plot(x1,y1,x2,y2);title('p=2.0');  
• xlim([0 1.1]);  
• ylim([0 1.1]);  

在Matlab中运行以上m文件即可画出如下图形，这里分别取范数||f||p等于0.5和1两种情况（即代码中的c1和c2），p分别取了0.5，1.0，1.5，2.0四种特殊情况:
可以看出所得到的图与论文的图2中的第一象限是一致的。
最后说一下第四个问题：两者的交点为什么一定要在坐标轴上？
这个问题很关键，说难也难，但说简单也很简单。
为什么在坐标轴上呢？首先这里要回到最早的前提：信号f是稀疏的，p无论为多少，它最终都是要等价到0范数的情况，这是最原始重构方法所在，但对于这里一个只有两维的信号来说，最稀疏能是什么情况呢？不能稀疏到一个非零元素都没有吧，所以最稀疏也只就是两个元素x1,x2一个为零，一个非零。这时候明白了吧，x1和x2一个为零一个非零，那么把它的坐标在坐标系里画出来是哪里呢？也就是直线与横轴或纵轴的交点了嘛，至于说到底是与横轴还是与纵轴的交点，这个很重要么？只要交换一下x1和x2两个轴，点不就变了么？论文中是以纵轴交点为例来说明问题的，其实你以与横轴的交点为例来说明问题也是可以的啊。


至此，有关lp球的问题就全部说完了，初识压缩感知，有很多很多不明白的问题，认识也是越来越深的，不妥之处敬请多多包含！