使用疊代式基底搜尋演算法之壓縮感測

Abstract

近年來，人們為了節省儲存空間或方便傳輸而發展出許多壓縮信號的方法，而這些方法通常都是先將信號完整取得，然後以不嚴重失真為原則將其中不必要的部分刪除。對於感測儀器來說(例如:照相機、收音機等)，將所有信號完整接收之後又將其中大部分的資料刪除是ㄧ種浪費的行為，尤其是壓縮率大為提高的今天，ㄧ個信號的主要資訊只集中在一小部份而其他絕大多數部分將被捨棄。 如今我們將介紹一種新的方法，將信號的壓縮與感測在同一時間完成，稱之為『壓縮感測』(Compressive Sensing)。而經過壓縮的感測值可以經由『疊代式基底搜尋演算法』(Greedy Basis Pursuit)將原本的信號重建回來。 當我們擷取ㄧ段信號時，取樣定理指出若要避免混疊效應(aliasing effect)而重建此信號，則取樣頻率必須大於信號最高頻率的兩倍，也就是我們熟知的奈奎斯速率(Nyquist rate)。由於壓縮感測將壓縮及感測結合在一起，所以其取樣頻率將會大幅減小而低於奈奎斯速率，也因此顛覆了取樣定理。

In the last few years, people compress signals after acquiring them. In the process of compression, there would be some information discarded from the signal by the compression algorithm. It is a waste that one obtains a signal and then throws parts of them away. If the compression ratio is large, it means one spend unnecessary time on acquiring this signal. Now we introduce a novel method that acquires and compresses a signal simultaneously, called Compressive Sensing. After compressive sensing a signal, one can get a condensed measurement. The minimization of l 1-norm is used to recover the signal from the measurement. Many algorithms can handle this problem, such as Matching Pursuit, Basis Pursuit and so on. Now we apply a faster algorithm to the problem, that is, Greedy Basis Pursuit. By the CS theory, one acquires a signal in a condensed form. Hence this theory beats the Shannon sampling theorem because it samples signals at a rate significantly below the Nyquist rate.