压缩感知理论研究简述

任肖丽

1，广东海洋大学信息学院 524088；

2，电子科技大学电子工程学院 611731

压缩感知理论研究简述

任肖丽12

1，广东海洋大学信息学院 524088；

2，电子科技大学电子工程学院 611731

压缩感知（Compressive Sensing, CS）理论是一个充分利用信号稀疏性或可压缩性的全新信号采集、编解码理论。本文系一文献综述，主要阐述了CS理论模型及主要算法、C S理论应用与研究现状。

compressive sensing; sparse representation; measurement matrix; algorithm

1 引言

传统方式下的信号处理，依照Shannon/Nyquist采样理论采样会产生大量的采样数据，需要先获取整个信号再进行压缩[20]，即采样后大部分采样数据将会被抛弃，这就极大地增加了存储和传输的代价。由于带宽的限制，许多信号只包含少量的重要频率的信息，所以大部分信号是稀疏的或可压缩的，对于这种类型的信号，我们知道，传统方式采样后的多数数据都会被抛弃，那么，为什么还要获取全部数据呢？难道不能直接获取已压缩数据而不需要抛弃任何数据？由Candes和Donoho 等人于2004 年提出压缩感知（Compressive Sensing或Compressed Sensing、Compressed Sampling, CS）理论[1-6]。该理论可以理解为将模拟数据节约地转换成压缩数字形式，避免了资源浪费。即，在采样信号的同时就对数据进行适当的压缩，相当于在采样过程中寻找最少的系数来表示信号，并能用适当的重构算法从压缩数据中恢复出原始信号。压缩感知的主要目标是从少量的非适应线性测量中精确有效地重建信号。核心概念在于试图从原理上降低对一个信号进行测量的成本。压缩感知包含了许多重要的数学理论，具有广泛的应用前景，最近几年引起广泛关注，得到了蓬勃的发展。

2 CS理论模型及主要算法

压缩感知(CS)，也被称为压缩传感或压缩采样，是一种利用稀疏的或可压缩的信号进行信号重建的技术。或者可以说是信号在采样的同时被压缩，从而在很大程度上降低了采样率。压缩感知跳过了采集N个样本这一步骤，直接获得压缩的信号的表示[2][4]。CS理论利用到了许多自然信号在特定的基Ψ上具有紧凑的表示，即这些信号是“稀疏”的或“可压缩”的。

CS理论主要包括三部分：一是信号的稀疏表示，二是设计测量矩阵，要在降低维数的同时保证原始信号x 的信息损失最小；三是设计信号恢复算法，利用M个观测值无失真地恢复出长度为N的原始信号。

2.1 信号稀疏表示换。

信号的稀疏表示就是将信号x投影到正交变换基Ψ时，绝大部分变换系数的绝对值很小，所得到的变换向量S=ΨTx是稀疏的或者近似稀疏的[4]。如果变换系数si的支撑域的势小于等于K，则信号x是K-项稀疏的[1]。

2.2 测量矩阵设计

CS的测量过程可表示为：

随机高斯矩阵与大多数固定正交基构成的矩阵不相关,这一特性决定了选择由高斯随机变量形成的测量矩阵为普适的CS测量矩阵，但是，它在硬件实现和重建算法构造上却难以实用。相对高斯矩阵等硬件上较难实现的其他随机矩阵形式，伯努利分布的±1矩阵成为构建硬件可实现的压缩感知方式的一个前提。

从CS的整个过程来看，选择合适的测量矩阵，可以达到压缩的目的，能够精确地重构信号。在CS理论中，对测量矩阵的约束是比较宽松的，测量矩阵所必需满足的一些具体条件请参阅文献[6]。

2.3 信号恢复主要算法

对于NP难题CS提供了解决稀疏恢复问题的许多方法及应用。一个主要方法是利用线性规划求解稀疏恢复问题的基追踪（Basis Pursuit, BP）算法，把最小化问题转换成1最小化问题,1最小化方法确保了一致稳定性。BP算法具有全局最优优点，但计算复杂度极高。

另一个主要方法是采用贪婪算法，如正交匹配追踪算法（OMP[14]），分段正交匹配追踪（StOMP[15]），迭代阀值法[16,17]。这些方法中大多数需要的采样点数为M=O(SlogN)。可以从测量向量y中重建信号x

其中，ΦS表示只限于测量矩阵Φ的S列，ΦS为ΦS的广义逆。贪婪算法以多于BP算法需要的采样数目换取计算复杂度的降低，计算速度快，但是缺乏稳定性。

用一个新的算法——正则化正交匹配追踪算法（ROMP）可以建立这两种算法间的联系。ROMP和BP一样提供了相似的稳定性结果。压缩采样匹配追踪（C o S a M P），是对R O M P结果的改进，是在稀疏恢复中在所有重要方面都可证明是最优的首要算法。

3 CS理论应用及研究现状

稀疏恢复问题应用于很多领域，从医学、编码理论到天文学和地球物理学。稀疏信号以一种自然的方式出现在实际中，所以CS适用于很多环境。三个直接的应用是纠错编码，成像，雷达。CS已经扩展出了许多新的分支和应用方向[19]，包括多传感器和分布式的CS、基于模型的CS、压缩成像[18]（其与线性成像效果比较如图1示）、医学成像[20][21]、模拟-信息转换（A/I Conversion）、计算生物学、地理数据分析、CS雷达等等;与CS相关或相结合的研究领域有编码理论与信息论、通信信号处理、高维度几何、统计信号处理、机器学习、贝叶斯CS、有限速率新息（Finite Rate of Innovation）等。目前压缩感知领域的工作主要集中在理论层面,即测量矩阵和重建算法的性能分析和优化上，对压缩感知实现方法的研究仍处在起步阶段，这就造成了理论研究和实际应用的脱节和不同步。针对模拟信号的压缩感知方式构建友好的硬件是压缩感知过程物理实现的关键步骤，也是将该理论推向实际应用的必要环节。

图1 [18] 线性成像与压缩成像效果比较

4 结语

本文阐述了CS理论的产生背景，模型框架，基于CS的信号恢复主要算法和CS理论应用与研究现状。CS理论提出之后便引起了广泛的关注，许多机构和领域的研究人员都投入了极大的热情参与进这一新领域的研究工作。CS理论是信号处理领域中一个非常新的研究方向，具有广泛的应用前景。

[1] E Candès, Compressive Sampling [A],Proceedings of the International Congress of Mathematicians[C],Madrid, Spain,2006,3,pp.1433～1452.

[2] E Candès, J Romberg, Terence Tao, Robust Uncertainty Principles: Exact Signal Reconstruction from Highly Incomplete Frequency Information [J],IEEE Trans. on Information Theory,2006,52 (2),pp.489-509.

[3] E Candès and J Romberg, Quantitative Robust Uncertainty Principles and Optimally Sparse Decompositions [J], Foundations of Comput Math,2006,6 (2),pp.227-254.

[4] D L Donoho, Compressed sensing [J], IEEE Trans.on Information Theory,2006,52 (4), pp.1289-1306.

[5] E J Cand ès, J Romberg, Practical signal recovery from random projections [OL], Http: / /www. acm. caltech. edu/ -emmanuel/ papers/Practical Recovery. pdf.

[6] D L Donoho, Y Tsaig, Extensions of Compressed Sensing [J], Signal Processing,2006,86 (3), pp.533-548.

[7] D. L. Donoho, X. Huo, Uncertainty Principle and Ideal Atomic Decomposition, IEEE Trans. Inform Theory, Nov,2001, Vol.47, No.7, pp.2845-2862.

[8] R Baraniuk, A Lecture on Compressive Sensing[J], IEEE Signal Processing Magazine,2007,24 (4),pp.118-121.

[9] E Candès and J Romberg, Sparsity and Incoherence in Compressive Sampling, Inverse Problems,2007,23(3), pp.969-985.

[10] Petros Boufounos and Richard G. Baraniuk,Sigma Delta Quantization for Compressive Sensing.(Preprint,2007)

[11] Cand ès, E. J., Tao, T., Near-optimal signal recovery from random projections and universal encoding strategies. IEEE Trans. Inform. Theory,2004, submitted.

[12] Cand ès, E. J., Tao, T., Decoding by linear programming. IEEE Trans. Inform. Theory51(2005),4203～4215.

[13]Deanna Needell, Topics in Compressed SensingDavis[D], University of California,2009

[14] J. A. Tropp and A. C. Gilbert, Signal recovery from random measurements via orthogonal matching pursuit. IEEE Trans. Info. Theory,53(12):4655～4666,2007.

[15] D. L. Donoho, Y. Tsaig, I. Drori, and J.-L.Starck, sparse solution of underdetermined linear equations by stagewise Orthogonal Matching Pursuit(StOMP), Submitted for publication,2007.

[16] T. Blumensath and M. E. Davies, Iterative hard thresholding for compressed sensing, preprint,2008.

[17]M. Fornasier and H. Rauhut, iterative thresholding algorithms, preprint,2007.

[18]Justin Romberg, Imaging via Compressive Sampling, IEEE Signal Processing Magazine,25(2),March2008, pp.14～20

[19] http://dsp.rice.edu/cs

[20] D L Donoho, Y Tsaig, I Drori etc. Sparse solution of underdetermined linear equations by stagewise orthogonal matching pursuit [ R], Technical Report ,2006.

[21] Argyrios Zymnis, Stephen Boyd, and Emmanuel Can dès, Compressed Sensing With Quantized Measurements[J], IEEE Signal Processing Letters, Vol.17, No.2, Feb.2010, pp.149-152.

Brief Introduction of Compressive Sensing Theory Research

REN Xiaoli12

1.Information School, Guangdong Ocean University, Guangdong Zhanjiang524088, China;
2. Electronic Engineering School, University of Electronic Science and Technology of China, Chengdu611731, China

Compressive sensing (CS) is a new theory of signal acquisition and coding, which makes full use of signal’s sparsity and compressibility. This paper is of a literature review, in which CS theory model and main algorithms, CS theory application and research current situation are illustrated.

压缩感知；稀疏表示；测量矩阵；算法