壓縮感知理論研究簡(jiǎn)述

任肖麗

1，廣東海洋大學(xué)信息學(xué)院 524088；

2，電子科技大學(xué)電子工程學(xué)院 611731

壓縮感知理論研究簡(jiǎn)述

任肖麗12

1，廣東海洋大學(xué)信息學(xué)院 524088；

2，電子科技大學(xué)電子工程學(xué)院 611731

壓縮感知（Compressive Sensing, CS）理論是一個(gè)充分利用信號(hào)稀疏性或可壓縮性的全新信號(hào)采集、編解碼理論。本文系一文獻(xiàn)綜述，主要闡述了CS理論模型及主要算法、C S理論應(yīng)用與研究現(xiàn)狀。

compressive sensing; sparse representation; measurement matrix; algorithm

1 引言

傳統(tǒng)方式下的信號(hào)處理，依照Shannon/Nyquist采樣理論采樣會(huì)產(chǎn)生大量的采樣數(shù)據(jù)，需要先獲取整個(gè)信號(hào)再進(jìn)行壓縮[20]，即采樣后大部分采樣數(shù)據(jù)將會(huì)被拋棄，這就極大地增加了存儲(chǔ)和傳輸?shù)拇鷥r(jià)。由于帶寬的限制，許多信號(hào)只包含少量的重要頻率的信息，所以大部分信號(hào)是稀疏的或可壓縮的，對(duì)于這種類型的信號(hào)，我們知道，傳統(tǒng)方式采樣后的多數(shù)數(shù)據(jù)都會(huì)被拋棄，那么，為什么還要獲取全部數(shù)據(jù)呢？難道不能直接獲取已壓縮數(shù)據(jù)而不需要拋棄任何數(shù)據(jù)？由Candes和Donoho 等人于2004 年提出壓縮感知（Compressive Sensing或Compressed Sensing、Compressed Sampling, CS）理論[1-6]。該理論可以理解為將模擬數(shù)據(jù)節(jié)約地轉(zhuǎn)換成壓縮數(shù)字形式，避免了資源浪費(fèi)。即，在采樣信號(hào)的同時(shí)就對(duì)數(shù)據(jù)進(jìn)行適當(dāng)?shù)膲嚎s，相當(dāng)于在采樣過(guò)程中尋找最少的系數(shù)來(lái)表示信號(hào)，并能用適當(dāng)?shù)闹貥?gòu)算法從壓縮數(shù)據(jù)中恢復(fù)出原始信號(hào)。壓縮感知的主要目標(biāo)是從少量的非適應(yīng)線性測(cè)量中精確有效地重建信號(hào)。核心概念在于試圖從原理上降低對(duì)一個(gè)信號(hào)進(jìn)行測(cè)量的成本。壓縮感知包含了許多重要的數(shù)學(xué)理論，具有廣泛的應(yīng)用前景，最近幾年引起廣泛關(guān)注，得到了蓬勃的發(fā)展。

2 CS理論模型及主要算法

壓縮感知(CS)，也被稱為壓縮傳感或壓縮采樣，是一種利用稀疏的或可壓縮的信號(hào)進(jìn)行信號(hào)重建的技術(shù)?；蛘呖梢哉f(shuō)是信號(hào)在采樣的同時(shí)被壓縮，從而在很大程度上降低了采樣率。壓縮感知跳過(guò)了采集N個(gè)樣本這一步驟，直接獲得壓縮的信號(hào)的表示[2][4]。CS理論利用到了許多自然信號(hào)在特定的基Ψ上具有緊湊的表示，即這些信號(hào)是“稀疏”的或“可壓縮”的。

CS理論主要包括三部分：一是信號(hào)的稀疏表示，二是設(shè)計(jì)測(cè)量矩陣，要在降低維數(shù)的同時(shí)保證原始信號(hào)x 的信息損失最小；三是設(shè)計(jì)信號(hào)恢復(fù)算法，利用M個(gè)觀測(cè)值無(wú)失真地恢復(fù)出長(zhǎng)度為N的原始信號(hào)。

2.1 信號(hào)稀疏表示換。

信號(hào)的稀疏表示就是將信號(hào)x投影到正交變換基Ψ時(shí)，絕大部分變換系數(shù)的絕對(duì)值很小，所得到的變換向量S=ΨTx是稀疏的或者近似稀疏的[4]。如果變換系數(shù)si的支撐域的勢(shì)小于等于K，則信號(hào)x是K-項(xiàng)稀疏的[1]。

2.2 測(cè)量矩陣設(shè)計(jì)

CS的測(cè)量過(guò)程可表示為：

隨機(jī)高斯矩陣與大多數(shù)固定正交基構(gòu)成的矩陣不相關(guān),這一特性決定了選擇由高斯隨機(jī)變量形成的測(cè)量矩陣為普適的CS測(cè)量矩陣，但是，它在硬件實(shí)現(xiàn)和重建算法構(gòu)造上卻難以實(shí)用。相對(duì)高斯矩陣等硬件上較難實(shí)現(xiàn)的其他隨機(jī)矩陣形式，伯努利分布的±1矩陣成為構(gòu)建硬件可實(shí)現(xiàn)的壓縮感知方式的一個(gè)前提。

從CS的整個(gè)過(guò)程來(lái)看，選擇合適的測(cè)量矩陣，可以達(dá)到壓縮的目的，能夠精確地重構(gòu)信號(hào)。在CS理論中，對(duì)測(cè)量矩陣的約束是比較寬松的，測(cè)量矩陣所必需滿足的一些具體條件請(qǐng)參閱文獻(xiàn)[6]。

2.3 信號(hào)恢復(fù)主要算法

對(duì)于NP難題CS提供了解決稀疏恢復(fù)問(wèn)題的許多方法及應(yīng)用。一個(gè)主要方法是利用線性規(guī)劃求解稀疏恢復(fù)問(wèn)題的基追蹤（Basis Pursuit, BP）算法，把最小化問(wèn)題轉(zhuǎn)換成1最小化問(wèn)題,1最小化方法確保了一致穩(wěn)定性。BP算法具有全局最優(yōu)優(yōu)點(diǎn)，但計(jì)算復(fù)雜度極高。

另一個(gè)主要方法是采用貪婪算法，如正交匹配追蹤算法（OMP[14]），分段正交匹配追蹤（StOMP[15]），迭代閥值法[16,17]。這些方法中大多數(shù)需要的采樣點(diǎn)數(shù)為M=O(SlogN)。可以從測(cè)量向量y中重建信號(hào)x

其中，ΦS表示只限于測(cè)量矩陣Φ的S列，ΦS為ΦS的廣義逆。貪婪算法以多于BP算法需要的采樣數(shù)目換取計(jì)算復(fù)雜度的降低，計(jì)算速度快，但是缺乏穩(wěn)定性。

用一個(gè)新的算法——正則化正交匹配追蹤算法（ROMP）可以建立這兩種算法間的聯(lián)系。ROMP和BP一樣提供了相似的穩(wěn)定性結(jié)果。壓縮采樣匹配追蹤（C o S a M P），是對(duì)R O M P結(jié)果的改進(jìn)，是在稀疏恢復(fù)中在所有重要方面都可證明是最優(yōu)的首要算法。

3 CS理論應(yīng)用及研究現(xiàn)狀

稀疏恢復(fù)問(wèn)題應(yīng)用于很多領(lǐng)域，從醫(yī)學(xué)、編碼理論到天文學(xué)和地球物理學(xué)。稀疏信號(hào)以一種自然的方式出現(xiàn)在實(shí)際中，所以CS適用于很多環(huán)境。三個(gè)直接的應(yīng)用是糾錯(cuò)編碼，成像，雷達(dá)。CS已經(jīng)擴(kuò)展出了許多新的分支和應(yīng)用方向[19]，包括多傳感器和分布式的CS、基于模型的CS、壓縮成像[18]（其與線性成像效果比較如圖1示）、醫(yī)學(xué)成像[20][21]、模擬-信息轉(zhuǎn)換（A/I Conversion）、計(jì)算生物學(xué)、地理數(shù)據(jù)分析、CS雷達(dá)等等;與CS相關(guān)或相結(jié)合的研究領(lǐng)域有編碼理論與信息論、通信信號(hào)處理、高維度幾何、統(tǒng)計(jì)信號(hào)處理、機(jī)器學(xué)習(xí)、貝葉斯CS、有限速率新息（Finite Rate of Innovation）等。目前壓縮感知領(lǐng)域的工作主要集中在理論層面,即測(cè)量矩陣和重建算法的性能分析和優(yōu)化上，對(duì)壓縮感知實(shí)現(xiàn)方法的研究仍處在起步階段，這就造成了理論研究和實(shí)際應(yīng)用的脫節(jié)和不同步。針對(duì)模擬信號(hào)的壓縮感知方式構(gòu)建友好的硬件是壓縮感知過(guò)程物理實(shí)現(xiàn)的關(guān)鍵步驟，也是將該理論推向?qū)嶋H應(yīng)用的必要環(huán)節(jié)。

圖1 [18] 線性成像與壓縮成像效果比較

4 結(jié)語(yǔ)

本文闡述了CS理論的產(chǎn)生背景，模型框架，基于CS的信號(hào)恢復(fù)主要算法和CS理論應(yīng)用與研究現(xiàn)狀。CS理論提出之后便引起了廣泛的關(guān)注，許多機(jī)構(gòu)和領(lǐng)域的研究人員都投入了極大的熱情參與進(jìn)這一新領(lǐng)域的研究工作。CS理論是信號(hào)處理領(lǐng)域中一個(gè)非常新的研究方向，具有廣泛的應(yīng)用前景。

[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.

壓縮感知；稀疏表示；測(cè)量矩陣；算法