稀疏隨機矩陣有限等距性質分析

張 波 劉郁林 王 開

?

稀疏隨機矩陣有限等距性質分析

張 波*劉郁林 王 開

(重慶通信學院DSP研究室 重慶 400035)

稀疏隨機矩陣由于具有存儲容量小、編碼和重構復雜度低、易于更新等優良特性而適用于分布式應用。為確保稀疏隨機矩陣可作為壓縮感知觀測矩陣，該文證明了稀疏隨機矩陣的有限等距性質(RIP)。首先，證明了測量矩陣滿足有限等距性質等價于其子矩陣的格拉姆矩陣特征值分布于1附近；在此基礎上，證明了當測量值個數滿足特定條件時，稀疏隨機矩陣以接近于1的概率滿足有限等距性質。仿真實驗表明，稀疏隨機矩陣在保證稀疏信號精確重建的同時，大大節約了測量和重建所需的時間。

壓縮感知；稀疏隨機矩陣；有限等距性質；測量矩陣

1 引 言

2 基本理論

2.1 壓縮感知

2.2 稀疏隨機矩陣

3 有限等距性質的特征值分布條件

即

4 稀疏隨機矩陣有限等距性質分析

證畢

證畢

借助以上引理可證明稀疏隨機矩陣滿足有限等距性質。

則有

證畢

5 仿真實驗

本節將通過仿真實驗分析稀疏隨機矩陣的性能，驗證稀疏隨機矩陣作為壓縮感知觀測矩陣的可行性和實用性。

圖1 1維稀疏信號重建

結合以上仿真結果可知：對稀疏隨機矩陣加入大量零元素，可在略微增加精確重建所需的測量值個數的情況下，大大減少測量和重建時間，對于圖像壓縮傳感、傳感器網絡數據壓縮傳感等實際應用具有重要的意義。

圖2 重建成功率比較

圖3 測量時間隨測量矩陣稀疏率變化情況

6 結束語

測量矩陣滿足RIP是確保重構稀疏信號的充分條件。本文證明了稀疏隨機矩陣滿足RIP，為應用稀疏隨機矩陣作為CS觀測矩陣解決實際問題提供了理論指導。該證明分兩步進行：首先，推導得到了測量矩陣滿足RIP的特征值分布條件，將RIP的證明問題轉化為格拉姆矩陣特征值分布范圍的討論問題；然后，證明了當測量值個數滿足特定條件時，稀疏隨機矩陣以接近1的概率滿足RIP。下一步將以本文的結論為基礎，針對WSNs的具體應用，深入研究適用于WSNs數據收集的稀疏測量矩陣設計問題。

[1] Donoho D L. Compressed sensing[J]., 2006, 52(4): 1289-1306.

[2] Candes E J and Tao T. Decoding by linear programming[J]., 2005, 51(12): 4203-4215.

[3] Candes E J, Romberg J, and Tao T. Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information[J]., 2006, 52(2): 489-509.

[4] CandesE J, EldarYC, NeedellD,.. Compressed sensing with coherent and redundant dictionaries[J]., 2011, 31(1): 59-73.

[5] Zhang T. Sparse recovery with orthogonal matching pursuit under RIP[J]., 2011, 57(9): 6215-6221.

[6] Haupt J, Bajwa W, Raz G,.. Toepitz compressed sensing matrices with applications to sparse channel estimation[J]., 2010, 56(11): 5862-5875.

[7] Luo J, Liu X, and Rosenberg C. Does compressed sensing improve the throughput of wireless sensor networks?[C]. IEEE International Conference on Communications, Cape Town, 2010: 1-6.

[8] Lee S, Pattem S, Sathiamoorthy M,.. Spatially-localized compressed sensing and routing inmulti-hop sensor networks[C]. Proceedings of the Third International Conference on Geosensor Networks, Oxford, 2009: 11-20.

[9] Wang Wei, GarofalakisM, and RamchandranK. Distributed sparse randomprojections for refinable approximation[C].IEEE International Symposium on Information Processing in Sensor Networks,Cambridge,2007: 331-339.

[10] Gilbert A and Indyk P. Sparse recovery using sparse matrices [J]., 2010, 98(6): 937-947.

[11] Wu K and Guo X. Compressive sensing with sparse measurement matrices[C]. Proceedings of the 73rd IEEE Vehicular Technology Conference, Budapest, 2011: 1-5.

[12] 孫晶明, 王殊, 董燕. 稀疏隨機矩陣的觀測次數下界[J]. 信號處理, 2012, 28(8): 1156-1163.

Sun Jing-ming, Wang Shu, and Dong Yan. Lower bounds on the number of measurements of sparse random matrices[J]., 2012, 28(8): 1156-1163.

[13] CandesEJ, RombergJ, and TaoT. Stable signal recovery from incomplete and inaccuratemeasurements [J]., 2006, 59(8): 1207-1223.

[14] CaiT T, WangL, and Xu G W. New bounds for restricted isometry constants[J]., 2010, 56(9): 4388-4394.

[15] Tropp J A and Gilbert A C. Signal recovery from random measurements via orthogonal matching pursuit[J]., 2007, 53(12): 4655-4666.

[16] 甘偉, 許錄平, 蘇哲, 等. 基于貝葉斯假設檢驗的壓縮感知重構[J]. 電子與信息學報, 2011, 33(11): 2640-2646.

Gan Wei, Xu Lu-ping, Su Zhe,.. Bayesian hypothesis testing based recovery for compressed sensing[J].&, 2011, 33(11): 2640-2646.

[17] Liu Y L, Wang K, and He J W. Signal recovery by compressed sensing in IR-UWB systems[J]., 2012, 21(2): 339-344.

張 波： 男，1987年生，碩士，助教，研究方向為壓縮感知、無線傳感器網絡.

劉郁林： 男，1971年生，教授，博士生導師，研究方向為盲信號處理、超寬帶通信、無線傳感器網絡等.

王 開： 男，1984年生，碩士，講師，研究方向為超寬帶通信、壓縮感知及其應用.

Restricted Isometry Property Analysis for Sparse Random Matrices

Zhang Bo Liu Yu-lin Wang Kai

(,,400035,)

Sparse random matrices have attractive properties, such as low storage requirement, low computational complexity in both encoding and recovery, easy incremental updates, and they show great advantages in distributed applications. To make sure sparse random matrices can be used as the measurement matrix, the Restricted Isometry Property (RIP) of such matrices is proved in this paper. Firstly, it is shown that the measurement matrix satisfies RIP is equivalent to the Gram matrix of its submatrix has all of eigenvalues around 1; then it is proved that sparse random matrices satisfy RIP with high probability provided the numbers of measurements satisfy certain conditions. Simulation results show that sparse random matrices can guarantee accurate reconstruction of original signal, while greatly reduce the time of measuring and reconstruction.

Compressed Sensing (CS); Sparse random matrix; Restricted Isometry Property (RIP); Measurement matrix

TN911.72

A

1009-5896(2014)01-0169-06

10.3724/SP.J.1146.2013.00023

2013-01-8收到，2013-10-21改回

教育部新世紀優秀人才支持計劃(NCET-10-0873)，重慶市自然科學基金重點項目(CSTC2011BA2016)，重慶高校創新團隊建設計劃(KJTD201343)和重慶市基礎與前沿研究計劃項目(cstc2013jcyjA 40045)資助課題

張波 zhangboswjtu@163.com