今天同學問了一個最佳化的問題： 給定三個點 $x_1=2,y_1=1,x_2=3,y_2=0,x_3=-2,y_3=2$ 求 $min_{\mathbf{w}}{\frac{1}{3}\sum_i(w_0+w_1x_i-y_i)^2+|\mathbf{w}|_1}$
這讓我想到之前看過某個印度教授講述關於 LASSO regression 和壓縮感知 (Compressive Sensing) 的影片。他探討了兩者概念上的相似性，並用圖像化來呈現兩者緊密的關聯。我認為這個有趣的概念值得和各位分享。
LASSO和壓縮感知的數學描述式
下面的式子可以用來統一描述這一類的問題： $min_{\mathbf{w}}{f(\mathbf{w})}, |\mathbf{w}|_l<=t$ 其中 $f(\mathbf{w})$ 通常假設是凸函數，$|\mathbf{w}|_l$ 是 $l$ norm，例如 $l_2$ 就是常見的歐式距離，$l_1$ 就是全部的絕對值之和，而 $l_0$ 的定義比較特別，是指說 $\mathbf{w}$ 有幾個非零的數值。
壓縮感知
當我們使用 $l_0$ 時，上面的問題就會是一個壓縮感知的問題。常見的形式為 $min_{\mathbf{w}}{|\mathbf{A}\mathbf{w}-\mathbf{y}|^2}, |\mathbf{w}|_0<=t$。$\mathbf{y}$ 通常描述的是要復原的訊號，$\mathbf{A}$ 是常見的所有基底訊號。一個應用是：$\mathbf{y}$ 描述腦內結構完整的3D結構圖，$\mathbf{A}$ 是所有核磁共振拍攝角度的圖片。如果我們要以最少的拍照次數來復原大腦的結構圖，這會對應到解一個最小化 $|\mathbf{w}|_0$ 的問題。除此之外，壓縮感知近年來也已經被大量的使用在各個領域。
LASSO 和壓縮感知共同的圖像化
如果給定函數 $f(\mathbf{w})$ 的等高面，下圖呈現的是 $l$ norm 不同時地狀況。可以觀察到當使用 $l_0$ 時，這個限制邊界就會凹線，在這樣的情況下，這個問題就會變得非常的難(不是凸函數)。也因此，Basic pursuit 問題常會被作為一個壓縮感知的近似解(可以由這個解開始做搜尋並優化)。
