稀疏表達的意義在於？為什麼稀疏表達得到廣泛的應用？

01-15

從2004年壓縮感知的提出到現在正好十年過去了，這十年里在工程，應數，統計等領域，關於稀疏性的研究一度過熱，即不管合不合理，把稀疏這一套東西試了再說。

實際上稀疏性早在壓縮感知便有著廣泛應用，大概可以分為兩個階段，而時間節點便是2004。

04年之前

Total Variation Image Denoising，L. Rudin, S. Osher, E. Fatemi, 1992; ( $ell_1$ -norm of the gradient of the image)
Denoising by Soft Thresholding，D. Donoho, 1995; ( $ell_1$ -norm)
LASSO, R. Tibshirani, 1996; ( $ell_1$ -norm of the regression coefficient)
Sparse representation in Visual Cortex (V1) direction selectivity, B. Olshausen, D. Field, 1996; (Gabor filter)
JPEG standards: JPEG (Local DCT), JPEG 2000 (Wavelet); ( $ell_1$ -norm of the DCT/Wavelet transform coefficient)
....

以上幾個例子（1-4）都是各自領域的經典著作。再往前便是七八十年代，地質學家在地震勘探中使用了稀疏性。

如括弧所示，這些例子中都用到了 $ell_1$ 範數，但它和稀疏性之間的關係並沒有系統性的研究。直到04年E. J. Candes，J. Romberg和T. Tao的文章[1]和D. Donoho的Compressed Sensing[2]. (據Candes說，[1]中給出的醫學圖像的例子，他對於重建結果如此完美起初並不是很理解。之所以會和Tao合作，是因為他們家小孩在同一個幼兒園上學，於是在放學等接小孩的時候討論了那個問題。。。)

Candes和Tao的文章就信號的稀疏性和 $ell_1$ 範數之間的關係給出了明確地定理。一個很粗略的解釋如下

設一個 $N$ 維信號的稀疏度為 $k$ ( $kll N$ )(非零元素位置與幅值未知)，對其進行 $m$ 採樣( $m<N$ )，如果 $m$ 和 $k$ 之間滿足一定的關係，那麼通過最小化 $ell_1$ 範數可以精確恢復原信號。

Candes的博士老闆Donoho，將這個過程成為Compressed Sensing。有了這兩邊奠基性的文章，壓縮感知，稀疏優化等便井噴式的發展起來，直到今日。

扯了這麼多。從上面的那些例子中，可以得出

稀疏表達的意義在於降維。

且這個降維並不局限於節省空間。更多地意義在於，在Machine Learning，Signal/Image Processing等眾多領域，很多反問題(Inverse Problem)都是不適定/病態的(under-determined, ill-posed)。如

$y = Ax + varepsilon, x in mathbb{R}^n, A:mathbb{R}^n o mathbb{R}^m, yinmathbb{R}^m, m<n, varepsilon extrm{ is noise}$

為了能獲得比較好的解，人們需要 $x$ 的先驗知識。而稀疏性便是眾多先驗知識中，最為主要的一種。這種降維主要表現於雖然原始信號 $x$ 的維度很高，但實際的有效信息集中在一個低維的空間里。這種性質使得不適定的問題變得適定(well-posed)，進而獲得「好的解」成為可能。

至於應用廣泛，則是因為現實當中，很多問題都是稀疏或者近似稀疏的。比如

圖像在小波變換，梯度運算元下是（近似）稀疏的；
分類過程中需要輸入在不同的基下面表達不同，這是稀疏性；
Deep Learning在不斷地提出feature的過程也是稀疏性；
推薦系統背後是因為用戶產品評價是一個低秩矩陣；
。。。

大概以上

[1] E. J. Candès, J. Romberg, T. Tao, Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information, IEEE Transactions on Information Theory

[2] D. L. Donoho, Compressed Sensing, IEEE Transactions on Information Theory

在最初，稀疏性自然地產生於信號處理領域，因為自然界中的信號低頻居多，高頻部分基本都是雜訊，因此使用小波或傅立葉做基矩陣時，表達係數往往只在幾個低頻的基上比較大，而高頻的基所對應的係數基本都接近零。Donoho等人為此提出了對表達係數做soft-thresholding，去掉高頻分量，從而能濾掉雜訊提升信號恢復效果。由於這些基矩陣是正交的，可以證明min|y-Ax|_2^2+lamba|x|_1的解為對A"y做soft-thresholding。後來人們脫離信號處理的背景，開始考慮一般性的基矩陣A，並把上面的問題當作對最小二乘的正則化來考慮，從而引出了LASSO（Tibshirani），以及壓縮感知（Candes）等人的工作。

事實上對最小二乘做l2正則化早已有之（Stein, 1956 James），因此考慮l1正則化也是一個自然的思路。這類正則化背後的基本原則都是bias-variance tradeoff，即降低模型複雜度，雖然犧牲一點bias，但通過大大降低variance而從整體上提升預測精度。這在高維問題（high variance）中是非常常用的手段，這種手法甚至幾乎貫穿了整本Elements of Statistical Learning: data mining, inference, and prediction.
2nd Edition.。l1正則化的另一個新意在於引入了稀疏性，從而給模型帶來了解釋性（Model interpretability），即根據非零係數所對應的基的實際意義來解釋模型的實際意義（例如Face Recognition via Sparse Representation）。注意，利用l2等傳統方法可以得到大量很小的係數，似乎可以額外做一步截斷來獲得大量為零的係數。但需要強調的是：零和非零的小數有本質區別。因為首先要確定什麼才是足夠小，這一點就相當於引入額外的參數（即截斷閾值），帶來額外的誤差（實際中要人工調整這個截斷閾值）。係數也可能有不同的scale，有的時候0.001實際是很大的係數卻被截斷了，而有的時候0.1實際是很小卻被留下了。另外，有的求解演算法要引入一些數值計算上的近似策略，使得實際得到的小係數實際上有可能是數值計算不穩定所造成的，這就更難以區分到底其實際為零還是非零。而l1的解，零與非零是確切的，用LARS等方法畫出解隨lambda變化的圖甚至都能看到在lambda取到某些值時某些係數開始從零變為非零。這可以說是一個優勢。

2006年以後，稀疏表示產生了幾個有趣的新思路。一是將係數的稀疏性，拓展到矩陣奇異值的稀疏性上。如果矩陣是一行行（或一列列）數據構成的，那麼其非零奇異值個數就是數據真正所在的低維子空間的維數。傳統的PCA方法即源自於此，通過觀察奇異值下降的曲線，做個人工的截斷來判斷降維的維數（因此可以看作Donoho那種思路在矩陣上的對應版本）。Candes等人提出了Robust PCA，通過對矩陣施加奇異值的稀疏性（從l1變成了nuclear norm）來自動學得降維的維數，同時還能對原始矩陣去噪（可以看我寫的另一個答案如何理解矩陣的「秩」？ - 過擬合的回答）。這也引出了另一個新思路：一般來說數據矩陣可能存在野點，即少部分行被污染了，因此可以求取某個行稀疏的野點矩陣，來「凈化」原始矩陣。這裡稀疏性就是施加在待求解的野點矩陣上。還有一個新思路是Zou Hastie提出的Sparse PCA，其大意是對loading vector施加稀疏性，從而可以對主成分做模型解釋。總的來說，這個領域的人現在基本都在矩陣上搞新思路（有些人甚至開始玩更高階的張量了）。

值得一提的是，本文提到的所有人物，均出自stanford統計系。

事實上，這個領域的經典文章大部分也都出自這裡。

July 7, 2015更新。

之前的答案說的的壓縮是sparse representation的第一個用處。因為相比於dimension reduction，sparsity的條件更加general，因此往往具有更大的壓縮空間。關於dimensionality reduction和sparsity的對比和關係，可以參見我的回答：

為什麼sparse representation比起其它成分分析方法（DFT，Wavelet）能得到更好的效果？ - Bihan Wen 的回答

第二的用處更加有意義，就是作為自然信號的regularizer（約束器）。

這裡提出一個問題：什麼樣的信號才是自然信號（Natural Signal），例如自然圖片，語音，視頻，醫療圖像？什麼樣的信號才是有」有意義「的？

我們在解決inverse problem（逆問題）的時候，例如要想從一切損壞或者雜訊中把他們提取出來，例如denoising, inpainting, classification, compressed sensing等等應用，這本身是一個ill-posed question。或者你可以想像成在接一組不定方程，如果不加約束的話，會出現很多滿足條件的解，並且你無法判斷某一個解比其他解更加合適。

所以我們需要一個regularizer，作為這些想要的信號的固有模型。而稀疏表達被廣泛地使用來作為自然信號的regularizer：認為這些信號都具有某個域（domian）或者某組基（bases, 或者dictionary）下的sparse representation。不具備如此特性的認為是noise, distortion, non-desirable solution...等這些可以被排除掉。

根據答主所知道的情況，並沒有很明顯的數學解釋，可以證明稀疏性是自然信號的最佳約束。因為我們本身就缺乏對自然信號的約束：比如如何定義natural image？什麼樣的圖才能叫是natural的？

實際應用裡面，sparsity也只是已知的很多regularizer中的一種，但被廣泛地證明有效。據我所知和工作實驗中的感覺，sparsity在unsupervised learning中是極少的被顯示出來廣泛有效的prior information。另外在醫療成像中，這種sparse regularizer（關於這個regularizer是linear還是non-linear，要看如何定義，感謝 @rc du 和@Kevin Sun的指正）也是被廣泛使用。

這裡就不引用相關文獻了，僅做科普使用。

排名第一的答案提到了compressed sensing和l1範數，值得指出的是，compressed sensing只是稀疏表達的用處之一。不過確實，稀疏表達在compressed sensing的概念被提出之後，獲得了廣泛的關注。

然後l1範數只是獲得sparsity的約束之一，而最原始的regularizer應該是使用l0範數，直接限定non-zeros的個數。而問題在於l0會到處優化問題成為non-convex的，l1有些情況下可以巧妙地解決這一問題，從而獲得解法的performance guarantee。

我覺得稀疏表達有兩點好處：

1) 省空間；

2) 奧卡姆剃刀說：如果兩個模型的解釋力相同，選擇較簡潔的那個。稀疏表達就符合這一點。

我覺得，稀疏表達的作用有兩個：

1）降低數據維數，稀疏表達後的特徵向量各維之間的依賴性變低，更為獨立

2）從人工智慧的角度來看，這更加接近「自動分析出隱藏在數據背後的解釋因子」這一思想

稀疏表達求取時所加的稀疏約束，使得計算後得到的各個「基「對於解釋數據具有相同的重要性，其目的正是在嘗試找出隱藏在數據背後的解釋因子

降維

貼一個很有趣的例子，現在都喜歡用找對象來打比方哈哈哈。圖片來自香港理工大學張磊教授Image Restoration: From Sparse and Low-rank Priors to Deep Priors的lecture notes。

L. Zhang, W. Zuo, "Image Restoration: From Sparse and Low-rank Priors to Deep Priors," IEEE Signal Processing Magazine, Sept. 2017.

補充一下

2004那幾篇文章之前的基礎性工作是Chen和Donoho在1998年的technical report

後來發在SIAM上

2004那幾篇文章尤其是Tao Candes 和Romberg工作的重要意義在於嚴格的數學證明,

事實上1998年那篇文章開始已經有一些小組在解決這裡的數學問題

Chen後來跑到文藝復興去了