上一篇《初識壓縮感知Compressive Sensing》中我們已經講過了壓縮感知的作用和基本想法，涉及的領域，本文通過學習陶哲軒對compressive sensing（CS）的課程，對壓縮感知做進一步理解，針對其原理做出講解。本文較為理論性，代碼請參考《“壓縮感知”之“Hello world”》。

Keywords: 壓縮感知 compressive sensing,?稀疏（Sparsity）、不相關（Incoherence）、隨機性（Randomness）

主要內容

===============================

回憶傳統壓縮

壓縮感知概念 &線性度量

壓縮感知適合解決什么問題？

壓縮感知是否可行？

怎樣恢復原信號？

Basis Pursuit & RIP

噪聲

線性編碼應用——single pixel camera

===============================

回憶傳統壓縮

對于原始信號x∈C(N*1)，傳統壓縮是構造正交矩陣D∈C（N*N）,正變換為y=Dx, 反變換x=D^-1y= D^Ty,?D^-1= D^T。

將初始信號x變換到y∈C(N*1)后，將保留其中的K個分量（K人工指定），對其他N-K個分量置零，這樣的信號y就稱為K稀疏（K-Sparse）的。于是得到編碼策略如下：

Code（編碼）：構造正交矩陣D，做正變換y=Dx, 保留y中最重要的K個分量及其對應位置。

Decode（解碼）：將K個分量及其對應位置歸位，其他位置置零，得到y，構造D，并用x=D^-1y恢復x。

換句話說，傳統壓縮就是構造正交陣進行編解碼，將所有N維信號全部存儲下來。其弊端是，

1. 由于香農定理的限制，采樣頻率很大，這樣造成了原始信號很長（N很大），消耗時間和空間。

2. K個重要分量要分別存儲其位置，多分配空間。

3. K中分量（在傳輸過程中）丟失的話不好恢復。

?[ S-sparse ]:A model case occurs?when x is known to be S-sparse for some 1≤S≤n,?which means that at most S of the coefficients of x can?be non-zero.

===============================

壓縮感知概念 & 線性度量

卍 壓縮感知初識（詳見上一篇具體介紹）：

? ? ? 與傳統壓縮不同的是，壓縮感知采用的y=Dx中，D不是N*N, 而是D∈C(M*N)的，其中M<N,也就是說D是一個扁矩陣，未知數個數大于方程個數。對于方程Dx=y, x∈C(N*1),y∈C(M*1),

? ? ? 我們知道，當M>=N的時候，這是一個determined或over-determined的problem，而且容易求解；而M<N的時候問題是under-determined的，如果我們假設x是稀疏的，最好的solution就是能夠滿足Ax≈b的最稀疏的x。CS驚人之處就是可以解決這種under-determined的問題：給定M*1的y，可以根據D恢復出N*1的x, 其中M<<N。如果x是S稀疏（S-sparse）的（或者想要讓它是S稀疏的），那么我們只需要取那S個度量（from N個未知量x）就好了。

卍 線性度量：

? ? ? 對于上面的問題y=Dx, 當M<N時我們已知有無窮多解。假設x₀是其中一個特解的話，那么通解形式即為x₀+WZ，其中W∈C(N*（N-M）),是D的零空間的一組基，Z是這組基的線性組合，總有DWZ=0。所以我們的任務就是找x₀+WZ中最稀疏的解x（為什么找最稀疏的后面會有證明的定理）。

? ? ?這里，原先傳統壓縮中N*N的D越冗余，其零空間越大，尋找更稀疏矩陣的選擇越多（即x₀+WZ越多）。

卍 求解問題：

[example of CS-imaging]：（from ppt of 陶哲軒）

A typical example of when this assumption is reasonable?is in imaging. An image may consist of ～10⁶?pixels and
thus require a vector of n～10⁶?to fully represent. But, if?expressed in a suitable wavelet basis, and the image does
not contain much noise or texture, only a small fraction?(e.g.?10⁴) of the wavelet coefficients should be significant.
(This is the basis behind several image compression?algorithms, e.g. JPEG2000.)

Intuitively, an S-sparse vector x has only S degrees of freedom, and so one should now be able to reconstruct x using only S or so measurements.This is the philosophy of compressed sensing(or compressive sensing, or compressive sampling): the number of measurements needed to accurately capture an object should be comparable to its compressed size, not its uncompressed size.

===============================

壓縮感知適合解決什么問題？

卍 信號是稀疏的

卍 sensor方計算代價較大，receiver方計算代價較小（即不適合將信息全部存儲下來，而適合取少量信息，之后恢復）

PS：single-pixel camera之后講(*^__^*)?

===============================

壓縮感知是否可行？

說起這個問題可能有人會奇怪，什么叫是否可行呢？就是說給出D和M維的y，是否可以唯一地把x恢復出來？答案是肯定的！

Compressive Sensing中有兩個問題，對于

• 一個是怎樣確定出一個stable的基θ，或者測量矩陣Φ
• 另一個是如何進行信號x的恢復（下一小節）

首先看看怎么確定一個stable的基： 2 conditions：下圖是說明了一切。

定理：假設Ax=b中，A是m*n的矩陣，x是n維向量，y是m維向量，A中任意2S列都是線性無關的(即無法線性組合得到0向量)，則s-sparse的向量x可以被b和A唯一地重構出來，i.e.

證明：假設可以重建出兩個向量x,x'同時滿足Ax=Ax'=b,其中x和x'都是S-Sparse的；那么就有A(x-x')=0; 因為x-x'中非零元素個數<=2S，所以x-x'是2S-Sparse的，又因為給出條件A中任意2S個列向量都是線性獨立（線性無關）的，這就與A(x-x')=0矛盾了，所以假設不成立，即，可以根據b和A唯一地恢復出x∈C(n*1)。

===============================

怎樣恢復原信號？

我們已知所選擇的最稀疏的x即x中非零元素最少的，即x的零范數最小的（向量的零范數即為其稀疏度sparsity）。

然而，求x=argmin||x||₀使得x滿足Ax=b的一個子問題是一個NP完全問題，需要在S個compoments中選出1,2,...,n個，看能從中選出最少多少個，滿足Ax=b,這樣，對于每一個n都有排列組合C(S,n)種方法，顯然不可行。所以我們想能不能換個什么方法來恢復信號，自然而然的，我們想到了最小平方法。具體見下圖Fig B。

Fig A. 用二范數代替零范數?

Fig B. L2范數下尋找滿足Ax=b的x，發現有一定偏差。

symmerize:

2-methods to methods:
1. L2-norm: quick, efficient, but get the wrong answer
2. L0-norm: precise but impractical

否定了L0范數和L2范數之后，我們想到取中——用L1范數（Basis pursuit的思路）。
so get select the L1-norm , that is the abs of each element

===============================

Basis Pursuit & RIP

Basis pursuit的方法在2000年由Candes-Romberg-Tao, Donoho提出，其基本思路見下圖（以二維為例）：

從圖中可見，L1-norm比L2-norm靠譜多了。從上圖中可見，x*處，x的L1-norm最小，這樣推廣到n維向量x，就是其每一維的值的絕對值的和。

下面這個Theorem就是對L1-norm方案（Basis pursuit）可行性的定理（具體證明看論文吧）：大概是說，原始S-sparse的信號f為n維，從其中隨機抽取m維分量，如果想利用Basis pursuit的方法把這m維向量重建出n維原始信號，只要滿足m>cS*log(n)即可，其中c是一個常數。

很多實驗結果表明呢，大多數S-sparse信號 f 可以在m>=4*S的時候得以很好的重建，由此有了下面更強的RIP假設：

假設A中任意4S列都是幾乎正交的，i.e. 在這4S列中，前4S個奇異值都在[0.9,1,1]范圍內，則任意S-sparse信號x可以通過basis pursuit 由 Ax重建。

2006年，Tao和Donoho的弟子Candes合作證明了在RIP條件下，0范數優化問題與以下1范數優化問題具有相同的解

上面已經說過一個定理：對于Ax=b，A中任意2S列都線性獨立，則任意S-sparse的向量x都可以被恢復出來，這是理論上的說法。實際上，利用basis pursuit進行恢復時需要增強條件：A中的每4S列都是幾乎正交的。這個精確的條件就是RIP，許多matrix都服從這個條件。

補充：

實際上以上的1范數優化問題是一個凸優化，故而必然有唯一解，至此sparse representation的大坑初步成型?？偨Y一下：

• ?如果矩陣滿足sparsity=2S，則0范數優化問題有唯一解。
• ?進一步如果矩陣A滿足RIP條件，則0范數優化問題和1范數優化問題的解一致。
• ?1范數優化問題是凸優化，故其唯一解即為0范數優化問題的唯一解。

===============================

噪聲

實際應用中，我們用b=Ax+z來進行擬合，對付噪聲的干擾，其中z是高斯噪聲向量。

Fig. Reconstructing a sparse signal x approximately from noisy data b=Ax+z, assuming that z has norm less than error tolerance e.

===============================

CS應用——single pixel camera

Rice大學首先研究出的單像素相機是CS的一個主要應用。

test image(65536 pixels ) and CS construction using 11000 and 1300 measurements

Reference：

我都整合起來放在這里了，其中包括陶哲軒的講座內容，我對其做的筆記，和大牛的一些解釋。對CS的一個基本代碼寫在了下一篇《“壓縮感知”之“Hello world”》，另外推薦一篇很好的博文。嗯。。。還有兩篇文章值得一看，一是《Compressive Sensing (Signal Processing Magazine 2007 715')?》，二是《An introduction to compressive sampling (Signal Processing Magazine 2008 1061')》。

from:?http://blog.csdn.net/abcjennifer/article/details/7748833

總結

以上是生活随笔為你收集整理的压缩感知进阶——有关稀疏矩阵的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。