抗雜訊低複雜度壓縮感知還原演算法

A Noise-Tolerant and Low-Complexity Compressive Sensing Reconstruction Algorithm for Noisy Scenario

郭泓圻(Hung-Chi Kuo)

指導教授 ： 吳安宇

國立臺灣大學/電機資訊學院/電子工程學研究所/碩士(2017年)

https://doi.org/10.6342/NTU201701135

摘要

壓縮感知是新興的訊號處理技術，吸引了許多研究者的目光，它能以遠低於傳統奈奎斯理論的取樣量來取樣訊號，並將訊號由這些較少的取樣中還原。本篇論文將著重於訊號還原的演算法。
隨著壓縮感知技術從理論發展到實際應用，量測雜訊是不可避免的問題。少量的雜訊就能造成還原的失敗。因此，我們需要抗雜訊的壓縮感知還原演算法。現行的還原演算法被稱為盲解演算法，它是設計給無雜訊的環境。在有雜訊的環境之下，其還原品質會急劇的下降。我們發現有另一類還原演算法被稱為半盲解演算法。在雜訊環境之下，相較於盲解演算法，半盲解演算法的還原品質大大的提升。然而半盲解演算法需要一個額外輸入的稀疏值。稀疏值是原始稀疏訊號之中，非零項的數目。但稀疏值在多數的應用中是無法取得的。簡而言之，在雜訊環境之下，盲解演算法的表現十分差勁，半盲解演算法表現良好但因為需要輸入稀疏值而無法被使用。
本篇論文的目標為提出一個低複雜度的盲解演算法，其能夠在雜訊環境中與半盲解演算法有同等甚至更佳的表現。此演算法讓壓縮感知技術更適合應用於實際應用。我們提出一個結合稀疏值估計與半盲解演算法的架構。稀疏值估計讓半盲解演算法能夠實際應用。然而，在面對雜訊環境時，現有的稀疏值估計技術跟半盲解演算法有其各自的問題。因此我們提出了一個基於殘差之稀疏值估計技術(residual-based sparsity estimation technique)跟一個改良的半盲解演算法，稱為考量稀疏值之子空間追蹤演算法(sparsity-aware subspace pursuit，SASP)。
我們結合基於殘差之稀疏值估計技術與考量稀疏值之子空間追蹤演算法，提出一個嶄新的壓縮感知還原演算法，稱為稀疏值估計匹配追蹤演算法(sparsity estimation matching pursuit，SEMP)。此演算法有幾個特點。其一，他是個盲解演算法，不需要額外的稀疏值輸入。其二，即使不需要額外的稀疏值，此演算法在抗雜訊的表現上，比現有最佳的半盲解演算法還要良好。其三，此演算法擁有低的運算複雜度。總結來說，有了本論文所提出的盲解低複雜度抗雜訊壓縮感知還原演算法，壓縮感知技術更適合於實際的應用。

關鍵字

壓縮感知 ； 稀疏訊號還原 ； 量測雜訊 ； 抗雜訊

並列摘要

Compressive sensing (CS) is an emerging signal processing technique that attracts intensive interest. It samples sparse signals efficiently with fewer measurements than Nyquist rate, and reconstructs signals from these few measurements. In this work, we’ll focus on CS reconstruction algorithms.
As CS technique develops from theory to realistic applications, measurement noise is an inevitable problem. Even a small amount of noise may cause failed reconstruction. Hence, a noise-tolerant CS reconstruction algorithm is desirable. The prevailing reconstruction algorithms, which are called blind algorithms, are designed for noiseless scenario. The reconstruction quality drastically degrades in noisy scenario. We find that another type of algorithms called non-blind algorithms can reconstruct signal with much better quality in noisy scenario. However, non-blind algorithms need an extra input of sparsity, which is the number of nonzero terms, of the sparse signal. While sparsity is not available in most applications. In other words, blind algorithms perform badly and non-blind algorithms perform well but are not feasible due to the need of input sparsity.
In this thesis, we aim to propose a low-complexity blind algorithm with the performance as good as or even better than non-blind algorithms in noisy scenario, in order to make CS more feasible in realistic applications. We propose a framework of combining sparsity estimation with non-blind algorithm. The estimation of sparsity is required to make non-blind algorithm work. Nevertheless, there are problems of the existing works of sparsity estimation and non-blind algorithms in noisy scenario. As a result, we propose a residual-based sparsity estimation technique and an improved non-blind algorithm called sparsity-aware subspace pursuit (SASP) algorithm.
We combine the residual-based sparsity estimation technique and SASP algorithm and propose a novel sparsity estimation matching pursuit (SEMP) algorithm. There are some features in the proposed SEMP algorithm. First, it’s a blind algorithm which is no need of explicit sparsity. Second, although without input of sparsity, its performance in noise-resilience is even better than the state-of- the-art non-blind algorithm. Last but not least, the SEMP has the properties of small overhead and low-complexity. To conclude, with the proposed blind low-complexity noise-tolerant CS reconstruction algorithm SEMP, the CS technique becomes more suitable to realistic applications.

並列關鍵字

compressive sensing ； sparse signal reconstruction ； measurement noise ； noise-tolerant

參考文獻

[1] D. L. Donoho, “Compressed sensing,” IEEE Trans. Inf. Theory, vol.52, no. 4, pp. 1289–1306, Apr. 2006.

[2] R. G. Baraniuk, “Compressive sensing,” IEEE Signal Process. Mag., vol. 24, no. 4, pp. 118–122, Jul. 2007.

[3] A. M. R. Dixon, E. G. Allstot, D. Gangopadhyay and D. J. Allstot, "Compressed Sensing System Considerations for ECG and EMG Wireless Biosensors," IEEE Trans. Biomed. Circuits and Syst., vol. 6, no. 2, pp. 156-166, Apr. 2012.

[4] M. Mishali and Y. C. Eldar, “Blind multiband signal reconstruction: Compressed sensing for analog signals,” IEEE Trans. Signal Process., vol. 57, pp. 993–1009, Mar. 2009.

[5] C. R. Berger, Z. Wang, J. Huang and S. Zhou, "Application of compressive sensing to sparse channel estimation," IEEE Commun. Mag., vol. 48, no. 11, pp. 164-174, Nov. 2010.