壓縮式感測算子在受限保距性質下近似保角特性之研究

A STUDY OF NEAR CONFORMALITY OF COMPRESSED SENSING OPERATORS UNDER THE RESTRICTED ISOMETRY PROPERTY

張玲華

指導教授 ： 吳卓諭

國立交通大學/電機學院/電信工程系所/博士(2016年)

摘要

在壓縮式感測的文獻中，確保訊號還原穩定性的充分條件大都要求壓縮式感測算子需具有受限保距性質，其描述任兩個稀疏訊號之間的距離在經過壓縮式感測後大致保持不變，概念上感測算子的保距特性也隱含了某種程度的保角特性，因此本篇論文探討在受限保距性質下，壓縮式感測算子的保角特性。假設兩稀疏向量u和v之間的夾角是theta，我們的目標即在受限保距性質下探討F_u和F_v間夾角可能發生的最大角和最小角。利用餘弦定理，我們由幾何的觀點去考慮受限保距性質所歸納出的長度和距離的限制，經過進一步平面幾何的分析後，我們推導出最大角和最小角的解析公式，藉由電腦模擬我們也證實提出的結果比現有的最大最小角的估計更加準確。基於我們的理論成果，我們也探討兩個常見的稀疏訊號還原演算法，即正交比對演算法和子空間演算法，其基於受限保距性質的效能保證。對正交比對演算法和子空間演算法，我們證明在較不嚴苛的充分條件下即可確保訊號還原穩定性。此外，我們也探討壓縮式感測在通訊及網路中的應用，如干擾消除和隨機存取的問題，首先我們證明壓縮空間正交投影干擾消除法的等效系統矩陣滿足受限保距性質，且其系統參數比現有文獻中的估計還要小，因此能得到更準確的系統效能評估。我們也考慮了隨機存取網路中有效使用者判斷的問題，我們放寬了現有相關文獻中都採用的使用者之間完美同步假設，提出了一套以壓縮式感測技術為基礎的偵測法則，電腦模擬指出在有效使用者較多的情況下，比起現有的偵測方式，我們可以較準確地進行使用者偵測。

關鍵字

壓縮式感測 ； 保角 ； 正交比對演算法 ； 子空間演算法 ； 隨機存取 ； 干擾消除

並列摘要

In the literature, a compressed sensing (CS) operator is commonly characterized by the so-called restricted isometry property (RIP), asserting that the Euclidean distance between two sparse vectors is approximately preserved upon compression. Conceptually, the RIP implies sort of conformality. This naturally motivates the fundamental question: How conformal a CS operator satisfying RIP can be? Toward an answer, assuming that u and v are two sparse vectors with angle theta, we investigate the achievable angle between u and v upon compression under RIP. With the aid of the well-known law of cosines, it is shown that all the RIP-induced norm/distance constraints can be jointly elucidated from a plane geometry perspective. Through further plane geometry analyses, closed-form formulae for the maximal and the minimal achievable angles are derived. Computer simulations show that our bounds are much tighter than as reported in the literature. Based on our theoretical study, we go on to develop improved RIP-based performance guarantees of two popular greedy-type signal reconstruction algorithms, namely, orthogonal matching pursuit (OMP) and subspace pursuit (SP). For both OMP and SP, we derive less stringent sufficient conditions guaranteeing exact/stable sparse signal recovery in the noiseless/noisy case. Also, applications of CS to communication and networking, including interference cancellation and random access, are studied. Firstly, we consider compressed-domain interference cancellation via orthogonal projection. Again, with the aid of our theoretical results we show that, as compared to the exising studies, the effective system matrix satisfies RIP with a smaller constant; this implies the signal reconstruction performance upon interference removal is better than as expected. Then, we consider active user detection in random access networks, without the perfect synchronization assumption widely made in the existing works. A CS-based detector is developed; computer simulations show that, when the active user set is large, our method achieves better detection accuracy than existing ones.

並列關鍵字

compressed sensing ； conformality ； OMP ； SP ； random access ； interference cancellation

參考文獻

[1] R. G. Baraniuk, “Compressive sensing,” IEEE Signal Processing Magazine, vol. 24, no. 4, pp, 118-124, July 2007.

[2] E. J. Candes and M. B. Wakin, “An introduction to compressive sampling,” IEEE Signal Processing Magazine, vol. 25, no. 2, pp, 21-30, March 2008.

[4] J. A. Tropp, J. N. Laska, M. F. Duarte, J. K. Romberg, and R. G. Baraniuk, “Beyond Nyquist: Efficient sampling of spare bandlimited signals,” IEEE Trans. Information Theory, vol. 56, no. 1, pp. 520-544, Jan. 2010.

[5] M. Elad, M. A. T. Figueiredo, and Y. Ma, “On the role of sparse and redundant representations in image processing,” Proceedings of the IEEE, vol. 98, no. 6, pp. 972-982, June 2010.

[6] W. U. Bajwa, J. Haupt, A. M. Sayeed, and R. Nowak, “Compressed channel sensing: A new approach to estimating sparse multipath channels,” Proceedings of the IEEE, vol. 98, no. 6, pp. 1058-1076, June 2010.