压缩传感综述

是高斯随机矩阵时, 传感矩阵 ~ © 能以较大概率满足约束等距性条件. 因此可以通过选择一个大小为 M£ N 的高斯测量矩阵得到, 其中每一个值都满足N(0; 1=N) 的独立正态分布. 高斯测量矩阵的优点在于它几乎与任意稀疏信号都不相关, 因而所需的测量次数最小. 但缺点是矩阵元素所需存储空间很大, 并且由于其非结构化的本质导致其计算复杂.其他常见的能使传感矩阵满足约束等距性的测量矩阵还包括一致球测量矩阵、二值随机矩阵、局部傅里叶矩阵、局部哈达玛测量矩阵以及托普利兹(Toeplitz) 矩阵等[15]. 一致球测量矩阵指矩阵的列在球 Sn¡1 上是独立同分布随机一致的, 并且当测量次数为 M = O(K ln(N)) 时, 准确重构信号的概率很大[1; 18¡19]. 二值随机矩阵是指矩阵中每个值都服从对称伯努利分布 P(©ij = §1=pM) = 1=2[3; 15],研究表明当 K · C £ M= ln(N=M) 时, 准确重构信号的概率极大, 并且重构速度很快. 方红等将亚高斯随机投影引入到压缩传感理论, 给出了两种新类型的测量矩阵: 稀疏投影矩阵和非常稀疏投影矩阵[20]. 局部傅里叶矩阵可以首先从傅里叶矩阵中随机选择 M 行, 然后再对列进行单位正则化得到[15; 21]. 傅里叶矩阵的一个突出优点是可以利用快速傅里叶变换快速计算, 大大降低了采样系统的复杂性, 然而由于其通常只与时域稀疏的信号不相关,应用范围受到了限制. 局部哈达玛测量矩阵是从 N维哈达玛矩阵中随机选择 M 行得到[22¡23], 当 M¸ KpN=B(lnN)2 (其中 B 是块的维数) 时, 置乱(Scrambled) 块哈达玛矩阵可以以极大概率准确重点.4 信号重构算法信号重构算法是压缩传感理论的核心, 是指由M 次测量向量 y y y 重构长度为 N (M ¿ N) 的稀疏信号 x x x 的过程. Candµes 等证明了信号重构问题可以通过求解最小 l0 范数问题 (3) 加以解决. 但Donoho 指出, 最小 l0 范数问题是一个 NP-hard 问题, 需要穷举x x x 中非零值的所有CK N 种排列可能, 因而无法求解[27]. 鉴于此, 研究人员提出了一系列求得次最优解的算法, 主要包括最小 l1 范数法、匹配追踪系列算法、迭代阈值法以及专门处理二维图像问题的最小全变分法等.4.1 最小l l l1 范数法采用 l1 范数代替 l0 范数[2], 得到了如下问题:^ x x x = argmin kx x xk1 s:t: ©x x x = y y y (9)文献 [28¡29] 证明了问题 (9) 和问题 (3) 是等价的.问题 (9) 是一个凸最优问题, 可以转化为一个线性规划问题加以求解, 计算复杂度为O(N3), 这种方法也称为基追踪方法 (Basis pursuit, BP)[28]. 如果考虑重构误差, 上述问题可以转换为如下最小 l1 范数问题:min kx x xk1 s:t: k©x x x ¡y y yk2 · " (10)该问题可以利用二阶圆锥规划求解[17].从对称伯努利分布 P(©ij = §1=pM) = 1=2[3; 15],研究表明当 K · C £ M= ln(N=M) 时, 准确重构信号的概率极大, 并且重构速度很快. 方红等将亚高斯随机投影引入到压缩传感理论, 给出了两种新类型的测量矩阵: 稀疏投影矩阵和非常稀疏投影矩阵[20]. 局部傅里叶矩阵可以首先从傅里叶矩阵中随机选择 M 行, 然后再对列进行单位正则化得到[15; 21]. 傅里叶矩阵的一个突出优点是可以利用快速傅里叶变换快速计算, 大大降低了采样系统的复杂性, 然而由于其通常只与时域稀疏的信号不相关,应用范围受到了限制. 局部哈达玛测量矩阵是从 N维哈达玛矩阵中随机选择 M 行得到[22¡23], 当 M¸ KpN=B(lnN)2 (其中 B 是块的维数) 时, 置乱(Scrambled) 块哈达玛矩阵可以以极大概率准确重构信号. Tsaig 对一致球测量矩阵、二值随机矩阵、局部哈达玛测量矩阵以及局部傅里叶矩阵的性能进行了比较, 发现将这几类矩阵作为测量矩阵时重构信号的误差都比较小, 并且随着测量数目的增加进一步减小[22].文献 [24] 提出了形式固定的托普利兹矩阵以及循环矩阵, 发现当 K · C £M3=ln(N=M) 时, 这两种矩阵使传感矩阵以很大概率满足约束等距性, 并且可以直接应用快速傅里叶变换得到快速的重构算法, 能够明显减少高维问题的计算和存储复杂度, 因而对高维问题特别有效. Sebert 等提出将块托普利兹矩阵应用于压缩传感, 并做了大量实验, 结果表明应用这种测量矩阵不仅有很好的重构结果, 而且可以明显加快运算速度和减少存储空间[25].此外, Do 等提出了结构化随机矩阵[26], 该矩阵具有与几乎所有其他正交矩阵 (单位阵和极度稀疏矩阵除外) 不相关的优点, 可以分解成定点、结构化分块对角矩阵与随机置换向量或伯努利向量点积的形式. 该矩阵可以看成是随机高斯/伯努利矩阵和部4.1 最小l l l1 范数法采用 l1 范数代替 l0 范数[2], 得到了如下问题:^ x x x = argmin kx x xk1 s:t: ©x x x = y y y (9)文献 [28¡29] 证明了问题 (9) 和问题 (3) 是等价的.问题 (9) 是一个凸最优问题, 可以转化为一个线性规划问题加以求解, 计算复杂度为O(N3), 这种方法也称为基追踪方法 (Basis pursuit, BP)[28]. 如果考虑重构误差, 上述问题可以转换为如下最小 l1 范数问题:min kx x xk1 s:t: k©x x x ¡y y yk2 · " (10)该问题可以利用二阶圆锥规划求解[17].问题(9) 也可以用内点法[30]、 梯度投影法[31]以及同伦算法[32]求解. 比较而言, 内点法速度较慢但非常精确, 梯度投影法则具有很好的运算速度, 而同伦算法对小尺度问题比较实用. 此外, 为进一步减少测量噪声对重构算法的影响, Candµes 等还提出了加权最小 l1 范数重构算法[12], 这种方法通过重新设置最小化 l1 范数问题来提高稀疏信号的重构质量.4.2 匹配追踪算法匹配追踪算法(Matching pursuit, MP) 是一种贪婪迭代算法, 其基本思想是在每一次的迭代过程中, 从过完备原子库 (即测量矩阵 ©) 里选择与信号最匹配的原子来构建稀疏逼近, 并求出信号表示残差, 然后继续选择与信号残差最为匹配的原子, 经过一定次数的迭代, 信号可以由一些原子线性表示. 但是由于信号在已选定原子 (测量矩阵的列向量) 集合上的投影的非正交性使得每次迭代的结果可能是次最优的, 因此为获得收敛可能需要经过较多次迭代.正交匹配追踪算法 (Orthogonal matching pursuit,

形式. 该矩阵可以看成是随机高斯/伯努利矩阵和部分傅里叶变换矩阵的混合模型, 并保持了各自的优正交匹配追踪算法 (Orthogonal matching pursuit,OMP)[13]则有效克服了这个问题, 该算法沿用了匹配追踪算法中的原子选择准则, 只是通过递归地对

已选择原子集合进行正交化以保证迭代的最优性,从而减少了迭代次数. 文献 [13] 中的实验表明, 对固定 K 稀疏 N 维离散时间信号x x x, 用一个 M £ N的高斯矩阵测量时, 只需 M = O(KlnN). 正交匹配追踪算法以极大概率准确重构信号, 而且比最小l1 范数法更快. 但是, 正交匹配追踪算法精确重构的理论保证比最小 l1 范数法弱, 并非对所有信号都能准确重构, 而且对于测量矩阵的要求比约束等距性更加严格[33].Needell 等在 OMP 基础上提出了正则正交匹配追踪(Regularized orthogonal matching pursuit,ROMP) 算法, 对所有满足约束等距性条件的矩阵和所有稀疏信号都可以准确重构[33]. 另外, 压缩采样匹配追踪算法 (Compressive sampling matchingpursuit, CoSaMP) 也可以用于很好地重构信号, 提供了比 OMP、ROMP 更全面的理论保证, 并且能在采样过程中对噪声鲁棒[34].综合考虑, 匹配追踪系列算法对于维数较低的小尺度信号问题运算速度很快, 但是对于存在噪声的大尺度信号问题, 重构结果不是很精确, 也不具有鲁棒性.4.3 最小全变分法相对于适合一维信号重构的最小 l1 范数法,Candµes 等从大量自然图像的离散梯度都是稀疏的角度出发, 提出了更适合二维图像重构的最小全变分法[2]. 图像压缩传感的全变分模型为5 压缩传感的应用压缩传感理论带来了信号采样理论的变革, 具有广阔的应用前景, 包括压缩成像、模拟信息转换、生物传感等. 本节将对这些应用作简要介绍.5.1 压缩成像运用压缩传感原理, 美国 RICE 大学成功研制了 \单像素" 压缩数码照相机[38], 设计原理是首先通过光路系统将成像目标投影到一个数字微镜器件上, 其反射光由透镜聚焦到单个光敏二极管上, 光敏二极管两端的电压值即为一个测量值y, 将此投影操作重复 M 次, 得到测量向量y y y, 然后用最小全变分算法构建的数字信号处理器重构原始图像 f f f. 数字微镜器件由数字电压信号控制微镜片的机械运动以实现对入射光线的调整, 相当于式 (4) 的 0-1 随机测量矩阵 ©. 由于该相机直接获取的是 M 次随机线性测量值, 而不是获取原始信号的 N (M ¿ N)个像素值, 为低像素相机拍摄高质量图像提供了可能. 压缩传感技术也可以应用于雷达成像领域, 与传统雷达成像技术相比压缩传感雷达成像实现了两个重要改进: 在接收端省去脉冲压缩匹配滤波器; 同时由于避开了对原始信号的直接采样, 降低了接收端对模数转换器件带宽的要求. 设计重点由传统的设计昂贵的接收端硬件转化为设计新颖的信号恢复算法, 从而简化了雷达成像系统[39]. Bhattacharya 等将压缩传感理论应用到合成孔径雷达图像数据获取

4.3 最小全变分法相对于适合一维信号重构的最小 l1 范数法,Candµes 等从大量自然图像的离散梯度都是稀疏的角度出发, 提出了更适合二维图像重构的最小全变分法[2]. 图像压缩传感的全变分模型为minTV(f f f) s:t: y y y = ©f f f (11)其中, 目标函数 TV(f f f) 为图像离散梯度之和, 即TV(f f f) = Pijp(fi+1;j ¡ fi;j)2 + (fi;j+1 ¡ fi;j)2 .该问题的求解可以转换为二阶锥规划问题[35]. 最小全变分模型可以有效地解决图像压缩重构问题,重构结果精确而且鲁棒, 但是运算速度较慢.4.4 迭代阈值法最小 l1 范数法以及匹配追踪等算法可以有效地解决压缩传感的信号重构问题, 但是这些算法都没有对 l0 范数问题 (3) 进行直接求解. 对此, Kings-bury 等提出了求解该问题的迭代阈值算法[36¡37].然而由于问题 (3) 的非凸特性, 这些算法只能保证收敛到局部最优解, 而且这些解有可能是非稀疏的.因而迭代阈值算法对初值非常敏感, 很难直接应用于信号重构. 但是如果能够找到一个合适的初值, 迭代算法可以找到问题 (3) 的全局最优解. 因此该算法可以与其他算法, 如MP 相结合, 由这些算法提供初值. 实验证明这种策略能够提供比单独匹配追踪算法更好的结果[14].重要改进: 在接收端省去脉冲压缩匹配滤波器; 同时由于避开了对原始信号的直接采样, 降低了接收端对模数转换器件带宽的要求. 设计重点由传统的设计昂贵的接收端硬件转化为设计新颖的信号恢复算法, 从而简化了雷达成像系统[39]. Bhattacharya 等将压缩传感理论应用到合成孔径雷达图像数据获取上[40], 解决了海量数据采集和存储问题, 显著降低了卫星图像处理的计算代价.此外, 压缩传感技术也可以应用于医学成像领域, 如稀疏核磁共振成像[41]、压缩传感三维磁共振波谱成像[42]等.5.2 信道编码压缩传感理论中关于稀疏性、随机性和凸最优化的结论可以直接应用于设计快速误差校正编码, 这种编码方式在实时传输过程中不受误差的影响[16]. 在压缩编码过程中, 稀疏表示所需的基对于编码器可能是未知的. 然而在压缩传感编码过程中, 它只在译码和重构原信号时需要, 并不需要考虑它的结构, 所以可以用通用的编码策略进行编码.Haupt 等通过实验表明如果图像是高度可压缩的或者信噪比(Signal to noise ratio, SNR) 充分大, 即使测量过程存在噪声, 压缩传感方法仍然可以准确重构图像[43]. Wakin 等研究了基于压缩传感理论的视频序列表示和编码方法[44]; Stankovic 和 Marcia 分别发展了视频压缩采样和压缩视频编码孔径重建问题[45¡46]; 为解决高维图像重建算法慢的问题, Gan提出了基于块的压缩传感技术[47]; Cevher 等利用源

图像与背景差图像更加稀疏的性质, 进行背景抽取,可直接对图像中的关注目标成像[48].5.3 模拟/信息转换对于带宽非常高的信号, 例如雷达和通信信号处理系统涉及的射频信号, 根据香农采样定理, 要获得完整的信号信息, 所采用的模数转换器必须有很高的采样频率. 然而由于传感器及转换硬件性能的限制, 获得的信号的带宽远远低于实际信号的带宽,存在较大的信息丢失. 对此Kriolos 等设计了基于压缩传感理论的模拟/信息转换器[49¡50], 利用压缩传感理论中测量信息可以得到完整信号的原理, 首先获得原始信号的线性测量, 再利用后端数字信号处理器重构原始信号或直接计算原始信号的统计数据等信息. Laska 等进一步发展了基于随机采样系统的模拟/信息转换器[51], 并给出了随机抽样系统的两种实现模型. 第一种模型采用多个并行低采样率的模数转换器, 每个模数转换器之间有等间隔的位移,通过随机控制来自不同的模数转换器的采样, 实现随机采样. 然而这种方法需要多个模数转换芯片, 每个芯片利用率不高. 基于此作者又设计了第二种模型, 通过一组电容和数字控制换向器随机采样, 该系统只需要一个模数转换芯片即可.5.4 生物传感是更复杂的非确定性测量矩阵在硬件实现上比较复杂, 虽然它们在仿真实验中能够取得很好的效果, 但是难以硬件实现, 因此有必要对确定性测量矩阵进行深入研究. 此外, 压缩传感技术建立在非自适应线性测量基础之上, 不具有灵活性, 因而有必要研究自适应压缩传感技术, 即根据不同的信号类型采用不同的数据采样和重构策略.2) 测量矩阵的优化问题在第 1 节中提到, 当图像不能在正交基上稀疏表示时, 可以将其扩展到冗余字典上进行稀疏表示.例如对于某一类型的图像, 用学习算法如K-SVD 等得到的字典通常可以使图像信号更加稀疏. 然而在压缩传感技术中, 利用冗余的字典代替标准正交基虽然可以更好地重构图像, 但由于在相应传感矩阵中会出现较多相关列, 这些相关列对于图像重构没有任何价值, 增加了算法的存储和计算的成本, 因此, 如何平衡冗余字典的冗余度与传感矩阵中相关列的数量, 即找到最优的冗余字典及其对应的传感矩阵是值得研究的.3) 测量值的应用研究许多图像处理的最终目的并不是重构图像, 而是为了得到有关目标的信息. 由压缩传感理论可知,在一定条件下, 通过少量的测量值就可以准确重构出原始图像, 也就是说少数的测量值能够保持原始信号的结构和足够多信息. 因此, 少量的测量值可以

生物传感中的传统 DNA 芯片能平行测量多个有机体, 但是只能识别有限种类的有机体, Sheikh等运用压缩传感和群组检测原理设计的压缩传感DNA 芯片克服了这个缺点[52], 压缩传感DNA 芯片中的每个探测点都能识别一组目标, 从而明显减少了所需探测点数量. 此外, 基于生物体基因序列稀疏特性, Sheikh 等验证了可以通过置信传播的方法实现压缩传感 DNA 芯片中的信号重构[53].压缩传感理论还应用于信号检测和分类[54¡56]、无线传感器网络[57]、数据通信[58¡59]以及地球物理数据分析[60]等众多领域.6 总结与展望压缩传感理论的提出极大地丰富了信号获取理论, 并为其他相关领域的研究提供了新技术和新思路, 研究前景广阔. 然而目前压缩传感理论还不是很完善, 相应的应用研究也刚刚起步, 尚有较多问题需要在未来研究中得到突破:1) 测量矩阵构造研究在压缩传感中, 测量矩阵需要满足约束等距性条件, 目前所采用的测量矩阵大多为非确定性测量矩阵, 即随机矩阵. 例如在 RICE 大学单像素相机信号的结构和足够多信息. 因此, 少量的测量值可以直接用于实现各种图像处理任务, 如图像分类、特征提取、目标检测以及信息融合等, 并且由于测量值数目较少, 信息密度高, 可以大大减少相关算法的时间和存储代价.4) 图像超分辨率重构图像的超分辨率重构是指从一幅或者多幅低分辨率图像产生或者构建高分辨率图像的过程, 本质上属于维数增加的问题, 具有不适定性. 在压缩传感中, 从测量值到原始信号也是一个从低维到高维的维数增加问题, 与超分辨率图像重构类似. 由于低分辨率图像通常决定了高分辨图像的结构和大部分信息, 因此借鉴压缩传感的相关思想实现新型的超分辨率图像重构算法也是值得研究的. 例如, 如果将低分辨率图像看成是在某种测量矩阵 (或者字典) 下的测量值, 则超分辨图像重构问题便转换为如何构建测量矩阵的字典构建问题.5) 运动目标提取基于图像序列的运动目标提取是计算机视觉领域的一个核心问题, 广泛应用在视频监控、视频分析、视频检索、基于运动信息的身份识别等方面. 当把背景看成不变量时, 运动的目标可以更加稀疏地表示, 符合压缩传感理论对信号的稀疏性要求. 因

研制中, 采用的就是较为简单的 0-1 伪随机矩阵. 但 此, 如何在压缩传感框架内, 利用图像序列运动目标

稀疏特性, 设计测量矩阵, 然后对图像序列的背景差进行线性测量, 最后精确重构出运动目标也是值得注意的研究方向.6) 实时压缩传感成像系统研制相对于压缩传感的理论研究进展, 其硬件实现还处于起步阶段. 目前已取得成功的例子主要有美国 RICE 大学研制的 \单像素" 数码相机, ARI-ZONA 大学 Baheti 和 Neifeld 设计的具有特定功能的结构成像设备, 以及 DUCK 大学研制的单景光谱成像装置[61]. 然而由于压缩重构算法的计算量比较大, 难以达到实时性要求, 因此实时高性能压缩传感成像系统是未来重要的研究方向.除了构建高分辨成像系统, 压缩传感还可应用于音频采集设备、节电型音频和图像采集设备、天文学观测、军事侦察、资源探测、超声图像以及数字减影血管造影技术等诸多方面.References1 Donoho D L. Compressed sensing. IEEE Transactions onInformation Theory, 2006, 52(4): 1289¡13062 Candµes E, Romberg J, Tao T. Robust uncertainty princi-ples: exact signal reconstruction from highly incompletefrequency information. IEEE Transactions on InformationTheory, 2006, 52(2): 489¡5093 Candµes E. Compressive sampling. In: Proceedings of In-ternational Congress of Mathematicians. Madrid, Spain:European Mathematical Society Publishing House, 2006.1433¡14524 Baraniuk R G. Compressive sensing. IEEE Signal Processing11 Candµes E, Romberg J. Sparsity and incoherence in compres-sive sampling. Inverse Problems, 2007, 23(3): 969¡98512 Candµes E, Braun N, Wakin M B. Sparse signal and imagerecovery from compressive samples. In: Proceedings of the4th IEEE International Symposium on Biomedical Imaging:From Nano to Macro. Washington D. C., USA: IEEE, 2007.976¡97913 Tropp J A, Gilbert A C. Signal recovery from random mea-surements via orthogonal matching pursuit. IEEE Transac-tions on Information Theory, 2007, 53(12): 4655¡466614 Blumensath T, Davies M E. Iterative thresholding for sparseapproximations. Journal of Fourier Analysis and Applica-tions, 2008, 14(5-6): 629¡65415 Candµes E, Tao T. Near optimal signal recovery from randomprojections: Universal encoding strategies? IEEE Transac-tions on Information Theory, 2006, 52(12): 5406¡542516 Candµes E, Tao T. Decoding by linear programming.IEEE Transactions on Information Theory, 2005, 51(12):4203¡421517 Candµes E, Romberg J, Tao T. Stable signal recovery fromincomplete and inaccurate measurements. Communicationson Pure and Applied Mathematics, 2006, 59(8): 1207¡122318 Donoho D L. For most large underdetermined systems of lin-ear equations the minimal l1-norm solution is also the spars-est solution. Communications on Pure and Applied Mathe-matics, 2006, 59(6): 797¡82919 Donoho D L. For most large underdetermined systems ofequations, the minimal l1-norm near-solution approximatesthe sparsest near-solution. Communications on Pure andApplied Mathematics, 2006, 59(7): 907¡9344 Baraniuk R G. Compressive sensing. IEEE Signal ProcessingMagazine, 2007, 24(4): 118¡1215 Olshausen B A, Field D J. Emergence of simple-cell recep-tive ¯eld properties by learning a sparse code for naturalimages. Nature, 1996, 381(6583): 607¡6096 Mallat S. A Wavelet Tour of Signal Processing. San Diego:Academic Press, 19967 Candµes E, Donoho D L. Curvelets | A Surprisingly E®ec-tive Nonadaptive Representation for Objects with Edges,Technical Report 1999-28, Department of Statistics, Stan-ford University, USA, 19998 Sun Yu-Bao, Xiao Liang, Wei Zhi-Hui, ShaoWen-Ze. Sparserepresentations of images by a multi-component Gabor per-ception dictionary. Acta Automatica Sinica, 2008, 34(11):1379¡1387(孙玉宝, 肖亮, 韦志辉, 邵文泽. 基于 Gabor 感知多成份字典的图像稀疏表示算法研究. 自动化学报, 2008, 34(11): 1379¡1387)9 Aharon M, Elad M, Bruckstein A M. The K-SVD: an algo-rithm for designing of overcomplete dictionaries for sparserepresentations. IEEE Transactions on Image Processing,2006, 54(11): 4311¡432210 Rauhut H, Schnass K, Vandergheynst P. Compressed sens-ing and redundant dictionaries. IEEE Transactions on In-formation Theory, 2008, 54(5): 2210¡221920 Fang Hong, Zhang Quan-Bing, Wei Shui. A method of im-age reconstruction based on sub-Gaussian random projec-tion. Journal of Computer Research and Development, 2008,45(8): 1402¡1407(方红, 章权兵, 韦穗. 基于亚高斯随机投影的图像重建方法. 计算机研究与发展, 2008, 45(8): 1402¡1407)21 Gilbert A C, Guha S, Indyk P, Muthukrishnan S, StraussM. Near-optimal sparse Fourier representations via sam-pling. In: Proceedings of the 34th Annual ACM Symposiumon Theory of Computing. Quebec, Canada: ACM, 2006.152¡16122 Tsaig Y, Donoho D L. Extensions of compressed sensing.Signal Processing, 2006, 86(3): 549¡57123 Pinkus A. N-Widths in Approximation Theory. New York:Springer-Verlag, 198524 Bajwa W U, Haupt J D, Raz G M, Wright S J, Nowak R D.Toeplitz-structured compressed sensing matrices. In: Pro-ceedings of the IEEE Workshop on Statistical Signal Pro-cessing. Washington D. C., USA: IEEE, 2007. 294¡29825 Sebert F, Zou Y M, Ying L. Toeplitz block matrices in com-pressed sensing and their applications in imaging. In: Pro-ceedings of International Conference on Technology and Ap-plications in Biomedicine. Washington D. C., USA: IEEE,2008. 47¡50

26 Do T T, Trany T D, Gan L. Fast compressive samplingwith structurally random matrices. In: Proceedings of theIEEE International Conference on Acoustics, Speech andSignal Processing. Washington D. C., USA: IEEE, 2008.3369¡337227 Donoho D L. For most large underdetermined systems of lin-ear equations, the minimal l1-norm solution is also the spars-est solution. Communications on Pure and Applied Mathe-matics, 2006, 59(6): 797¡82928 Chen S B, Donoho D L, Saunders M A. Atomic decomposi-tion by basis pursuit. SIAM Journal on Scienti¯c Comput-ing, 1998, 20(1): 33¡6129 Donoho D L, Elad M, Temlyakov V N. Stable recovery ofsparse overcomplete representations in the presence of noise.IEEE Transactions on Information Theory, 2006, 52(1):6¡1830 Kim S J, Koh K, Lustig M, Boyd S, Gorinevsky D. Aninterior-point method for large-scale l1 regularized leastsquares. IEEE Journal of Selected Topics in Signal Process-ing, 2007, 1(4): 606¡61731 Fiqueiredo M A T, Nowak R D, Wright S J. Gradient pro-jection for sparse reconstruction: application to compressedsensing and other inverse problems. IEEE Journal of Se-lected Topics in Signal Processing, 2007, 1(4): 586¡59732 Donoho D L, Tsaig Y. Fast Solution of l1-Norm Minimiza-tion Problems When the Solution May Be Sparse, TechnicalReport, Department of Statistics, Stanford University, USA,200833 Needell D, Vershynin R. Greedy signal recovery and un-certainty principles. In: Proceedings of the Conference onComputational Imaging. San Jose, USA: SPIE, 2008. 1¡1234 Needell D, Tropp J A. CoSaMP: Iterative signal recoveryfrom incomplete and inaccurate samples. Applied and Com-putational Harmonic Analysis, 2008, 26(3): 301¡32135 Lobo M S, Vandenberghe L, Boyd S, Lebret H. Applicationsof second-order cone programming. Linear Algebra and ItsApplications, 1998, 284(1-3): 193¡22841 Lustig M, Donoho D L, Pauly J M. Sparse MRI: the applica-tion of compressed sensing for rapid MR imaging. MagneticResonance in Medicine, 2007, 58(6): 1182¡119542 Hu S, Lustig M, Chen A P, Crane J, Kerr A, Kelley D AC. Compressed sensing for resolution enhancement of hyper-polarized 13C °yback 3D-MRSI. Journal of Magnetic Res-onance, 2008, 192(2): 258¡26443 Haupt J, Nowak R. Compressive sampling vs. conventionalimaging. In: Proceedings of the IEEE International Confer-ence on Image Processing. Washington D. C., USA: IEEE,2006. 1269¡127244 Wakin M B, Laska J N, Duarte M F, Baron D, Sarvotham S,Takhar D. An architecture for compressive imaging. In: Pro-ceedings of IEEE International Conference on Image Pro-cessing. Washington D. C., USA: IEEE, 2006. 1273¡127645 Stankovic V, Stankovic L, Cheng S. Compressive video sam-pling. In: Proceedings of the European Signal ProcessingConference. Lausanne, Switzerland: Elsevier, 2008. 1¡546 Marcia R F,Willett R M. Compressive coded aperture videoreconstruction. In: Proceedings of the European Signal Pro-cessing Conference. Lausanne, Switzerland: 2008. 6¡1047 Gan L. Block compressed sensing of natural images. In:Proceedings of the 15th International Conference on Digi-tal Signal Processing. Washington D. C., USA: IEEE, 2007.403¡40648 Cevher V, Sankaranarayanan A, Duarte M F, Reddy D,Baraniuk R G, Chellappa R. Compressive sensing for back-ground subtraction. In: Proceedings of the 10th Euro-pean Conference on Computer Vision. Marseille, France:Springer, 2008. 155¡16849 Kirolos S, Laska J,Wakin M, Duarte M F, Baron D, RaghebT. Analog-to-information conversion via random demodula-tion. In: Proceedings of the IEEE Dallas Circuits and Sys-tems Workshop. Richardson, USA: IEEE, 2006. 71¡7450 Ragheb T, Kirolos S, Laska J, Gilbert A, Strauss M, Bara-

Applications, 1998, 284(1-3): 193¡22836 Kingsbury N. Complex wavelets for shift invariant analysisand ¯ltering of complex wavelets for shift invariant analysisand ¯ltering of signals. Applied and Computational Har-monic Analysis, 2001, 10(3): 234¡25337 Herrity K K, Gilbert A C, Tropp J A. Sparse approxima-tion via iterative thresholding. In: Proceedings of the IEEEInternational Conference on Acoustics, Speech and SignalProcessing. Washington D. C., USA: IEEE, 2006. 624¡62738 Duarte M F, Davenport M A, Takhar D, Sun T, KellyK F, Baraniuk R G. Single-pixel imaging via compressivesampling. IEEE Signal Processing Magazine, 2008, 25(2):83¡9139 Baraniuk R, Steeghs P. Compressive radar imaging. In: Pro-ceedings of the Radar Conference. Washington D. C., USA:IEEE, 2007. 128¡13340 Bhattacharya S, Blumensath T, Mulgrew B, Davies M. Fastencoding of synthetic aperture radar raw data using com-pressed sensing. In: Proceedings of the 14th Workshopon Statistical Signal Processing. Washington D. C., USA:IEEE, 2007. 448¡45250 Ragheb T, Kirolos S, Laska J, Gilbert A, Strauss M, Bara-niuk R. Implementation models for analog-to-informationconversion via random sampling. In: Proceedings of the 50thMidwest Symposium on Circuits and Systems. WashingtonD. C., USA: IEEE, 2007. 325¡32851 Laska J, Kirolos S, Massoud Y, Baraniuk R, Gilbert A,Iwen M. Random sampling for analog-to-information con-version of wideband signals. In: Proceedings of the IEEEDallas/CAS Workshop on Design, Applications, Integra-tion and Software. Washington D. C., USA: IEEE, 2006.119¡12252 Sheikh M A, Milenkovic O, Baraniuk R G. Designing com-pressive sensing DNA microarrays. In: Proceedings of theIEEE International Workshop on Computational Advancesin Multi-Sensor Adaptive Processing. Washington D. C.,USA: IEEE, 2007. 141¡14453 Sheikh M A, Sarvotham S, Milenkovic O, Baraniuk R G.DNA array decoding from nonlinear measurements by beliefpropagation. In: Proceedings of the 14th Workshop on Sta-tistical Signal Processing. Washington D. C., USA: IEEE,2007. 215¡219

54 Haupt J, Nowak R. Compressive sampling for signal detec-tion. In: Proceedings of the IEEE International Conferenceon Acoustics, Speech and Signal Processing. WashingtonD.C., USA: IEEE, 2007. 1509¡151255 Davenport M A, Wakin M B, Baraniuk R G. Detectionand Estimation with Compressive Measurements, TechnicalReport TREE 0610, Department of Electrical Engineering,Rice University, USA, 200656 Haupt J, Castro R, Nowak R, Fudge G, Yeh A. Compressivesampling for signal classi¯cation. In: Proceedings of the For-tieth Asilomar Conference on the Signals, Systems and Com-puters. Washington D. C., USA: IEEE, 2006. 1430¡143457 Bajwa W, Haupt J, Sayeed A, Nowak R. Compressive wire-less sensing. In: Proceedings of the International Conferenceon Information Processing in Sensor Networks. Nashville,USA: ACM, 2006. 134¡14258 Taubock G, Hlawatsch F. A compressed sensing techniquefor OFDM channel estimation in mobile environments: ex-ploiting channel sparsity for reducing pilots. In: Proceed-ings of the IEEE International Conference on Acoustics,Speech, and Signal Processing. Las Vegas, USA: IEEE, 2008.2885¡288859 BajwaWU, Haupt J, Raz G, Nowak R. Compressed channelsensing. In: Proceedings of the 42nd Annual Conference onInformation Sciences and Systems. Washington D. C., USA:IEEE, 2008. 5¡1060 Hennenfent G, Herrmann F J. Simply denoise: wave ¯eld re-construction via jittered undersampling. Geophysics, 2008,73(3): 19¡2861 Gehm M E, John R, Brady D J, Willett R M, Schulz Tdisperser architecture. Optics Express, 2007, 15(21): 14013¡14027李树涛 湖南大学电气与信息工程学院教授. 2001 年于湖南大学获得控制理论与控制工程专业博士学位. 主要研究方向为图像处理, 模式识别和信息融合. 本文通信作者.E-mail: shutao li@yahoo.com.cn(LI Shu-Tao Professor at the Col-lege of Electrical and Information Engineering, Hunan Uni-versity. He received his Ph.D. degree in control theory andcontrol engineering from Hunan University in 2001. Hisresearch interest covers image processing, pattern recogni-tion, and information fusion. Corresponding author of thispaper.)魏 丹 湖南大学电气与信息工程学院博士研究生. 主要研究方向为图像处理与模式识别.E-mail: weiweidandan@163.com(WEI Dan Ph.D. candidate at theCollege of Electrical and InformationEngineering, Hunan University. Her re-search interest covers image processing and pattern recog-nition.)61 Gehm M E, John R, Brady D J, Willett R M, Schulz TJ. Single-shot compressive spectral imaging with a dual-