稀疏表示 工程, 领域, 先来, 知识

yuyang911220

在我们引入稀疏表达的领域之前，我们先来看这么几个问题。
  在一个欠定性的线性系统当中，矩阵（n<m）,定义一个等式：Ax=b。那么我们根据线性代数的知识可以获知，x可以是无解，也可以是无穷多解。为了避免出现无解的情况，我们设A为满秩矩阵。
  而在工程中，我们常常遇到这种欠定性的线性系统形式。b往往是经过处理的某种信号，而x则是原信号。比如在图像处理中：b可以是经过模糊处理，缩小等操作的图像，而这种图像在人眼视觉系统中往往是低质量的图像。A则代表了这一系列的操作。我们在工程中碰到的情况是给定一张模糊不清的图像，要你恢复出清晰的原图像x。但是，可以有无数多张图像x经过操作变为b,那么如何寻找出最佳的图像x就成为了我们的工作。
  为了获得这种最优解，我们一般是定义广义最优化问题：
   
   通俗地讲，我们希望为了获取我们所希望的最优解，那么我们通过增加限制，即狭隘了挑选解的空间。从统计学的角度来讲就是正则化约束。这里的J(x)往往是衡量这个解x有多适合这个线性系统。从图像的角度来讲，往往指得是点与点之间平滑约束。
  解决这种问题，我们可以采用拉格朗日乘子，J(x)我们一般是采用2范式。
   
接下来的问题就比较简单了，为了最小化Pj这个式子，也就是求解的最小值问题，我们可以对该式子对x的求导，令其导数为0，得最优解：
  
   
因为 还是未知数，所以再带入限制方程Ax=b,求得。再带回上式子，最终得到最优解。
  --------------------------------------------------------------稀疏表达（2）---------------------------------------------------------------------
     1927年的时候，奈奎斯特确定了如果对某一带宽的有限时间连续信号（模拟信号）进行抽样，且在抽样率达到一定数值时，根据这些抽样值可以在接收端准确地恢复原信号。为不使原波形产生“半波损失”，采样率至少应为信号最高频率的两倍，这就是著名的奈奎斯特采样定理。
       我是学通信出生，虽然通信方面学的比较烂，但是奈奎斯特采样定理在信号领域的地位的重要性我还是知道的，它影响了我们上世纪的信号领域，直到现在也还一直影响着。
       而近些年来比较活跃spase representation和compressive sensing领域所要做的从某种意义上来说，是与奈奎斯特采样定理相悖的。通俗得来讲，奈奎斯特认为如果我们要恢复一个信号，那么我们在采样该信号的时候采样频率至少要为信号频率的两倍。而从sparse和cs基本理论角度说，在获知信号是可稀疏表示这一先验知识的情况，信号可压缩感知，即可用较少的基向量恢复出原信号。
  

         我们再次回到上一篇Ax=b的欠定性线性系统，由于图是从吴老师的ppt中挖来的，所以变量的命名有些不同，此处的y就是等式的b,p为m。
  我们假设以下条件：
  1 该方程是欠定性的。
  2 A是满秩矩阵----->为了避免无解情况。
         那么我们现在的问题就是：希望x的解尽可能稀疏，即0在x的向量中出现的次数较多。从信号恢复的角度来讲，就是在矩阵A中用最少的基向量通过测量值y恢复出信号x来。接下来0-normal就登场了。我们用数学语言来描述我们所要解决的问题就是：
  

  这其实就是sparse和cs的核心问题。
  ------------------------------------------------------------稀疏表达（3） L0-norm-----------------------------------------------------------

  先定义一类Lp-norm优化问题：
  
  p为norm,我们从图中直观的来分析p的取值对优化问题的影响：
  
  图1
  注：紫色的为AX=b平面,青色的为norm ball
         左上：p=2;
         右上：p=1.5;
         左下：p=1;
         右下：p=0.7;
  从图中我们可以明显的看到：
  当p>=1时，norm ball和平面的交点，即可行解有多个。
  当0<p<1时，可行解很稀疏。
  但是鱼和熊掌往往是不能相得的。
  虽然当p>=1时，这显然这是一个凸优化问题，我们可以利用现有的一些工程手段来解决。
  而当0<p<1时，这显然是一个非凸优化问题，解这类问题将会产生很多困难。但是从工程师的角度来讲，解的稀疏性是我们所期望的要求，我们所希望解是越稀疏越好。
  那么现在我们来定义L0-norm:
  
  当p趋向与0时的norm称之为L0-norm。从等式上我们可以看出，其实通俗点来说，L0-norm就是在数x非0元素的个数。
  因为当x=0时，定义x的0次等于0
  而当x=other时，x的0次等于1。
  所以就是累加x的非0元素。
  L0-norm的优化问题：
  

  很显然，这是个NP难问题。那么我们如何来着手解这个问题呢，联系标准的凸优化问题，我们需要对L0-norm（非凸优化）提出以下两个问题：
  1 在什么条件下它的解是唯一的？
  2 如果解是可行的，那么它是否是全局最优解？
----------------------------------------------------稀疏表达（4）唯一性和非确定性的讨论-------------------------------------------
在上一篇中提到了L0-norm的优化问题，我们就定义成P0问题：

该优化问题的描述：对于一个欠定性的线性方程Ax=b来说，寻找如何用最少的基向量来表达出信号b。对于该问题解的唯一性和非确定性，下面引入一个实例来讨论：
         我们知道信号可以通过傅里叶变换由难以处理的时域转换成频域来处理，其实质也就是将满足一定条件下的某个信号函数表示成正弦基函数的线性组合。
        那么我们将信号b分别表示在时域和频域中表示：


是时域基向量，可以理解为单位矩阵，是频域基向量，可以理解为傅里叶变换矩阵；b在时域和频域的解的唯一性显然是可以被确定的。但是我们现在其实比较感兴趣的问题是这两个解，即和是否能同时被稀疏？接着看。
       我们假设信号b是由和线性组合而成，即：

然后我们定义一个mutual-coherence概念：

描述的是两组基向量的相似性，选取两组基向量两两内积的最大值（至于为什么这么定义，我也不知道，等待大牛解答）。
很显然是有范围的：

因为A是正交阵，所以必然是小于1。如果小于这个下限值，那么累加所有的n个内积，那么所得到的值将会小于1。
假设，即，那么我们可以如下证明：


而进一步可以转化成1-norm形式：

再利用三角不等式转换上式：
（1）
这并非是我们的最终目的，我们的目的是最终引导到L0-norm的非确定性讨论。
我们再来定义一个优化问题：
（2）
注意：此处的A代表的是有A个数目的非0向量。
整个问题描述是：正交基向量组有A个非0向量，我们希望获取基向量组L1-norm的最长距离。我们假设该问题的解为：

那么个g(A)>=,再联系等式（1），我们就可得：
（3）
建立一个g(A)的优化问题其实也就是给等式(1)寻找一个值的上限。而解等式（2）的优化问题可以利用拉格朗日乘子法进行求导计算最优解。计算所得：

联系到我们最感兴趣的L0-norm，等式（3）又可转化为：

再进行一次三角不等式转化，最终可得：
（4）
这就是著名的非确定法则1。该结论也说明了，当两组基向量的mutual-coherence很小时，两组解不能被同时稀疏。