面向稀疏訊號處理之快速取樣與重建: 演算法及分析

Toward Fast Sampling and Reconstruction in Sparse Signal Processing: Algorithms and Analysis

謝松憲(Sung-Hsien Hsieh)

指導教授 ： 貝蘇章

國立臺灣大學/電機資訊學院/電信工程學研究所/博士(2019年)

https://doi.org/10.6342/NTU201900255

摘要

稀疏訊號處理近年來獲得許多關注。藉由假設訊號在某種轉換域下為稀疏係數(大多數係數為零)，能更進一步改善傳統訊號取樣或重建，例如減少取樣次數。由於自然訊號天生符合稀疏性假設，已經有許多重要應用如頻譜感測、通訊同步、稀疏成份分解等。

現存兩個與稀疏訊號處理相關的重要技術分別為壓縮感知和稀疏傅立葉轉換。這兩個技術的主特性為：在編碼器(encoder) 方面，取樣頻率低於奈奎斯特頻率(Nyquist rate)；在解碼器(decoder) 方面，重建演算法只使用較少的取樣點。本論文的貢獻是針對上述兩個技術，提出演算法減少在取樣和重建過程中的計算複雜度和記憶體需求，並且提供理論和實驗結果來佐證。更精確來講，我們提出新的解碼器，稱為降採樣稀疏傅立葉轉換，能於接近最優時間來重建稀疏訊號。該研究的想法能更進一步延伸到減少找圓周摺積最大點的計算複雜度。找圓周摺積最大點與許多重要應用相關，如通訊同步和影像追蹤。此外，在壓縮感知方面，傳統方法常遇到下列問題：編碼端不容易於硬體實現和解碼端對於大訊號重建需要龐大計算量。因此我們利用上述降採樣稀疏傅立葉轉換的概念，去設計一個新的採樣方法，並且能根據採樣點來重建頻域上具有稀疏性的訊號。我們同時也放寬稀疏性的假設，從頻域到任一能使用循環矩陣為基底的域。我們也討論如何將計算負擔放到雲端來協助重建，並討論相關的資料安全議題。最後在理論部份，對於分散式壓縮感知(更廣義的壓縮感知) 提出重建效能分析。

總結來看，實驗和理論結果顯示本論文提出的方法，能達到快速感測、快速重建、以及維持重建品質。

關鍵字

稀疏性 ； 壓縮感知 ； 快速傅立葉轉換

並列摘要

Sparse signal processing, based on the assumption that signals are sparse in a certain transform domain or dictionary, has appeared in recent years. Benefited from nature signals inherently satisfy this assumption, many algorithms and techniques were developed for leveraging sparsity to improve various fields (e.g., sparse signal reconstruction requires fewer measurements). The key application domains of sparse signal processing include spectrum sensing, synchronization in communication, sparse component analysis and etc.

In this thesis, we focus on two important techniques, compressive sensing (CS) and sparse Fourier transform (SFT), where both of them aim to design a sampling scheme below Nyquist rate and reconstruct a sparse signal in a certain transform domain given few measurements. Our contributions are to reduce the computation complexity and memory consumption in both encoder and decoder, which can be validated via theoretical and empirical results.

Specifically, in SFT, we proposed a novel decoder, called sparse fast Fourier transform with downsampling (sFFT-DT), in SFT for exactly and generally K-sparse signals,
which achieve nearly optimal computation complexity. The idea of sFFT-DT is extended to speed up finding the position of maximum of circular convolution by replacing fast Fourier transform (FFT) with SFT. This method efficiently reduces the computation costs in two key applications, synchronization in global positioning system (GPS) and video tracking.

In CS, for large-scale signals, it conventionally suffers from hardware implementation unfriendliness at the encoder and slow reconstruction at the decoder. It motivates us to propose a new SFT-based sensing matrix benefiting from rapidly sensing and reconstructing
frequency-sparse signals. This assumption ”frequency-sparse“ is further relaxed into ”sparse in a circulant dictionary“. Furthermore, we design a framework where the decoder can put the computation overheads into the cloud and the privacy and security are still guaranteed. Finally, we theoretically show the performance analysis under distributed CS, which is a more general framework of CS. In sum, experimental and theoretical results validate the proposed methods in this thesis achieve fast sensing, fast recovery, and maintain the reconstruction quality.

並列關鍵字

Sparsity ； Compressive Sensing ； Fast Fourier Transform

參考文獻

[1] S. D. A. Averbuch and S. Deutsch. Adaptive compressed image sensing using dictionaries. SIAM Journal on Imaging Sciences, 5(1):57–89, 2012.

[2] M. Aharon, M. Elad, and A. Bruckstein. K-svd: An algorithm for designing overcomplete dictionaries for sparse representation. IEEE Transactions on Signal Processing, 54(11):4311–4322, 2006.

[3] X. Alameda-Pineda and R. Horaud. A geometric approach to sound source localization from time-delay estimates. IEEE Trans. on Audio, Speech, and Language Processing, 22(6):1082–1095, 2014.

[4] A. Alba, E. Arce-Santana, R. M. Aguilar-Ponce, and D. U. Campos-Delgado. Phase-correlation guided area matching for realtime vision and video encoding. Journal of Real-Time Image Processing, 9:621–633, 2014.

[5] D. Amelunxen, M. Lotz, M. B. McCoy, and J. A. Tropp. Living on the edge: phase transitions in convex programs with random data. Information and Inference, 3(3):224–294, 2014.