压缩感知理论分析综述
目录
TOC\o1-3\h\u51压缩感知理论分析综述 1
59951.1压缩感知概述 1
303611.1.1压缩感知简介 1
156791.1.2信号的稀疏度表示 3
11941.1.3测量矩阵的设计 5
175401.1.4压缩感知重构算法 6
189661.2压缩感知贪婪重构算法 7
50431.2.1SAMP算法 8
273431.2.2OMP算法 9
1.1压缩感知概述
2004年，Donoho、Candes以及Romberg等人正式提出了压缩感知理论，该理论认为，如果信号具有稀疏特性，那么就可以通过较少的采样值高概率地恢复出原始信号。这一理论的提出弥补了奈奎斯特（Nyquist）采样定理对采样速率要求过高的不足，为信号处理研究提供了新的方向。大量的物理实验表明，实际的无线多径信道普遍呈现出稀疏结构，即信道的多条传播路径中的能量往往集中在几条路径上。伴随着稀疏信道概念的普及与压缩感知理论的逐渐成熟，基于压缩感知的信道估计技术被运用在越来越多的无线通信系统中。
1.1.1压缩感知简介
压缩感知(CS)，又称压缩感知、压缩采样和稀疏采样，是一种为欠定线性系统提供稀疏解的技术。在工程中，CS是利用先验信息的稀疏性或可压缩性来获取和重构信号的过程。压缩感知理论是在数据采样的同时完成压缩过程，其数学形式是将一个高维信号通过特定的矩阵投射到低维空间。重构时，采用线性或非线性重构算法对原始信号进行重构。
压缩感知理论框架主要由信号的稀疏表示、编码测量以及重构算法的设计这三个部分组成。其中，信号的编码测量和重构是基于信号的可稀疏性。编码时，测量矩阵的选取应满足有限等距准则(RestrictedIsometryProperty,RIP),即观测矩阵的选取应满足与稀疏基不相关的原则。压缩感知采样原理如1.1所示。
图1.1压缩感知采样原理框图
假如某信号x是长度为N的一维可压缩的信号，其稀疏形式可以表示为式
(22)。
x=Ψθ
其中，中是标准的正交基，θ是K(KN)稀疏表示系数。通过测量矩阵Φ∈R
y=Φθ
A=ΦΨ
y=Aθ
上式中,A∈R
整个压缩感知理论的线性测量过程可以用图1.2表示。
图1.2压缩感知线性测量过程
对于信号重构问题，就是通过优化算法获得一个最稀疏的解θ，然后通过反演稀疏解获得原始信号的估计值x，其重构示意图如图1.3所示。
图1.3压缩感知信号重构过程
1.1.2信号的稀疏度表示
如果信号只有很少的非零元素，那么这个信号就是稀疏的。通常，时域下的自然信号都是明显非稀疏的，不能直接进行压缩感知处理信号，但是将信号投影到某些变换域(如空间频域)时就是稀疏的，经稀疏变换后的信号即可应用压缩感知处理。信号的稀疏性还可以理解为:变换系数中有K个较大值系数，其他N-K个系数等于或接近于零,则可以认为该信号是K系数信号。如一副自然场景图像,它的像素几乎都不为零,经过小波变换后,频域大部分系数趋近于零,因此，直接处理有限个非零系数就可以重构整个图像的信息。
假设信号x∈RN×1,则可以用一组基向量
x=i=1
其中，Θ∈RN×1是标准正交基下信号的稀疏表示。当信号x在正交基Ψ下稀疏系数θ只有K(KN)非零元素，那么我们就说
稀疏向量θ可以从测量值y中重构出来,也就是求解一个有正则约束的线性方程问题。相关理论表明该线性方程可以通过求解式(30)最优l0
θ=argmin
其中，θ0表示零范数，即向量中非0元素的数量。如果直接求解上式则是一个NP-hard问题且求解的数值不稳定。后来有人证明当测量矩阵满足RIP条件时，可以将求解最小l0范数问题可以转化为求解最小
θ=argmin
对于含噪声的信号y=Aθ+ε
θ=argmin
这类算法称为LP(线性规划)重构算法。对于任意参数λ,之前的约束优化求解将转化为无约束优化问题，其等价形式如式(33)。
min1
根据稀疏基Ψ=ψ
1.1.3测量矩阵的设计
测量矩阵(也称观测矩阵)是用来对N维的稀疏信号进行观测得到M(MN)维的观测向量y,而目标信号x可以利用凸优化等方法从该观测值y中重构出来。因此，理想的测量矩阵是能够实现采样得到M个观测值，并确保能从这M个值中重构出长度为N的信号x(或是等价的稀疏系数向量值)。为了保证压缩感知算法中测量矩阵能够较准确重构信号，其需要满足如下一些的条件:
(1)约束等距性原则(RestrictedIsometryProperty,RIP)，该原则定义如下:对于任意信号x假设其稀疏度为K,若存在常数δk
1?δ
则矩阵Φ满足K阶RIP原则。观测基矩阵Φ与稀疏基矩阵Ψ的乘积矩阵A称之为测量矩阵(传感矩阵)，该矩阵同样需要满