機器學習講座總結-北航-互聯(lián)網(wǎng)應用下的大規(guī)模在線學習算法(四)-為什么要正則化

監(jiān)督機器學習問題無非就是“minimize your error while regularizing your parameters”谊却，也就是在規(guī)則化參數(shù)的同時最小化誤差。最小化誤差是為了讓我們的模型擬合我們的訓練數(shù)據(jù)灾杰，而規(guī)則化參數(shù)是防止我們的模型過分擬合我們的訓練數(shù)據(jù)尼荆。因為參數(shù)太多砚蓬，會導致我們的模型復雜度上升圣勒，容易過擬合解虱，也就是我們的訓練誤差會很小攘须。但訓練誤差小并不是我們的最終目標，我們的目標是希望模型的測試誤差小殴泰，也就是能準確的預測新的樣本于宙。所以，我們需要保證模型“簡單”的基礎上最小化訓練誤差艰匙，這樣得到的參數(shù)才具有好的泛化性能（也就是測試誤差也小）抹恳，而模型“簡單”就是通過規(guī)則函數(shù)來實現(xiàn)的员凝。另外，規(guī)則項的使用還可以約束我們的模型的特性奋献。這樣就可以將人對這個模型的先驗知識融入到模型的學習當中健霹，強行地讓學習到的模型具有人想要的特性，例如稀疏瓶蚂、低秩糖埋、平滑等等。

規(guī)則化符合奧卡姆剃刀(Occam's razor)原理窃这。不過它的思想很平易近人：在所有可能選擇的模型中瞳别，我們應該選擇能夠很好地解釋已知數(shù)據(jù)并且十分簡單的模型。
從貝葉斯估計的角度來看，規(guī)則化項對應于模型的先驗概率祟敛。

統(tǒng)計學習角度

\mathcal{R}_{ept} \le \mathcal{R}_{emp} + \mathcal{G}_m[\mathcal{F}]

\mathcal{F}

\mathcal{R}_{emp} \le \mathcal{R}_{ept}

\mathcal{R}_{emp} \le \mathcal{R}_{ept} \le \mathcal{R}_{emp} + \mathcal{G}_m[\mathcal{F}]

如果此時泛化復雜度為0望侈，那么測試集上的效果就和訓練集上的效果一致，這時乍构，學習機就具有了絕對的泛化能力甜无。然而實際上，我們很難找到一個模型哥遮，其在訓練集上損失小并且同時泛化復雜度也小岂丘。
言歸正傳，我們對于線性模型或者說更為廣泛意義下的線性模型（比如前饋神經(jīng)網(wǎng)絡可以看做一種層疊的線性模型）眠饮，有如下泛化方程：

\mathcal{R}_{ept} \le \mathcal{R}_{emp} + (RL)^{K-1}ln^{\frac{3}{2}(K-1)}(m)\sqrt{\frac{R^2N^2}{m}} + \sqrt{\frac{ln(\delta^{-1})}{m}}

其中：

R=||\vec w||_l

||\vec w||_l

最小化權系數(shù)范數(shù)

\min ||\vec w||_l

的統(tǒng)計學習本質(zhì)是提高泛化能力雅倒。

求解可逆性角度璃诀，條件數(shù)，解的穩(wěn)定性

線性回歸有 closed-form 解法蔑匣，例如 如下是 最小二乘法(嚴謹點是 ORDINARY least square劣欢，簡寫OLS) 求解線性回歸時用到的 mse loss

L = \frac{1}{N}|Y - XW|^2

W = (X^TX)^{-1}X^TY

|X^TX| = 0

L = \frac{1}{N}|Y-XW|^2 + \lambda|W|^2

W = (X^TX - \lambda I)^{-1}X^TY

\lambda

規(guī)則化是結構風險最小化策略的實現(xiàn)膳算，是在經(jīng)驗風險上加一個正則化項(regularizer)或懲罰項(penalty term)。
一般來說弛作，監(jiān)督學習可以看做最小化下面的目標函數(shù)：

其中涕蜂，第一項L(yi,f(xi;w)) 衡量我們的模型（分類或者回歸）對第i個樣本的預測值f(xi;w)和真實的標簽yi之前的誤差。因為我們的模型是要擬合我們的訓練樣本的映琳，所以我們要求這一項最小机隙，也就是要求我們的模型盡量的擬合我們的訓練數(shù)據(jù)。但正如上面說言萨西，我們不僅要保證訓練誤差最小有鹿，我們更希望我們的模型測試誤差小，所以我們需要加上第二項谎脯，也就是對參數(shù)w的規(guī)則化函數(shù)Ω(w)去約束我們的模型盡量的簡單葱跋。

到這里，你會發(fā)現(xiàn)源梭，機器學習的大部分帶參模型都和這個不但形似娱俺，而且神似。是的废麻，其實大部分無非就是變換這兩項而已荠卷。對于第一項Loss函數(shù)，如果是Square loss烛愧，那就是最小二乘油宜；如果是Hinge Loss，那就是著名的SVM屑彻；如果是exp-Loss馏颂，那就是牛逼的 Boosting了姆另；如果是log-Loss标锄，那就是Logistic Regression了癌别；還有等等住涉。不同的loss函數(shù)墩蔓，具有不同的擬合特性攘烛，這個也得就具體問題具體分析的舶赔。

規(guī)則化函數(shù)Ω(w)也有很多種選擇，一般是模型復雜度的單調(diào)遞增函數(shù)熟空，模型越復雜藤巢，規(guī)則化值就越大。比如息罗，規(guī)則化項可以是模型參數(shù)向量的范數(shù)掂咒。然而，不同的選擇對參數(shù)w的約束不同迈喉，取得的效果也不同绍刮，但常見的都聚集在：零范數(shù)、一范數(shù)挨摸、二范數(shù)孩革、跡范數(shù)、Frobenius 范數(shù)和核范數(shù)等等得运。

一膝蜈、L0范數(shù)與L1范數(shù)

L0范數(shù)是指向量中非0的元素的個數(shù)。如果我們用L0范數(shù)來規(guī)則化一個參數(shù)矩陣W的話熔掺，就是希望W的大部分元素都是0饱搏。換句話說，讓參數(shù)W是稀疏的瞬女。

L1范數(shù)是指向量中各個元素絕對值之和窍帝，也有個美稱叫“稀疏規(guī)則算子”（Lasso regularization）。為什么L1范數(shù)會使權值稀疏诽偷？有人可能會這樣給你回答“它是L0范數(shù)的最優(yōu)凸近似”坤学。實際上，還存在一個更美的回答：任何的規(guī)則化算子报慕，如果他在Wi=0的地方不可微深浮，并且可以分解為一個“求和”的形式，那么這個規(guī)則化算子就可以實現(xiàn)稀疏眠冈。這說是這么說飞苇，W的L1范數(shù)是絕對值，|w|在w=0處是不可微蜗顽，但這還是不夠直觀布卡。這里因為我們需要和L2范數(shù)進行對比分析。

既然L0可以實現(xiàn)稀疏雇盖，為什么不用L0忿等，而要用L1呢？個人理解
一是因為L0范數(shù)很難優(yōu)化求解（NP難問題）崔挖，
二是L1范數(shù)是L0范數(shù)的最優(yōu)凸近似贸街，而且它比L0范數(shù)要容易優(yōu)化求解庵寞。
所以大家才把目光和萬千寵愛轉(zhuǎn)于L1范數(shù)。

OK薛匪，來個一句話總結：L1范數(shù)和L0范數(shù)可以實現(xiàn)稀疏捐川，L1因具有比L0更好的優(yōu)化求解特性而被廣泛應用。

參數(shù)稀疏有什么好處

1）特征選擇(Feature Selection)：
      大家對稀疏規(guī)則化趨之若鶩的一個關鍵原因在于它能實現(xiàn)特征的自動選擇逸尖。一般來說古沥，xi的大部分元素（也就是特征）都是和最終的輸出yi沒有關系或者不提供任何信息的，在最小化目標函數(shù)的時候考慮xi這些額外的特征娇跟，雖然可以獲得更小的訓練誤差渐白，但在預測新的樣本時，這些沒用的信息反而會被考慮逞频，從而干擾了對正確yi的預測纯衍。稀疏規(guī)則化算子的引入就是為了完成特征自動選擇的光榮使命，它會學習地去掉這些沒有信息的特征苗胀，也就是把這些特征對應的權重置為0襟诸。

2）可解釋性(Interpretability)：
       另一個青睞于稀疏的理由是，模型更容易解釋基协。例如患某種病的概率是y歌亲，然后我們收集到的數(shù)據(jù)x是1000維的，也就是我們需要尋找這1000種因素到底是怎么影響患上這種病的概率的澜驮。假設我們這個是個回歸模型：y=w1*x1+w2*x2+…+w1000*x1000+b（當然了陷揪，為了讓y限定在[0,1]的范圍，一般還得加個Logistic函數(shù)）杂穷。通過學習悍缠，如果最后學習到的w*就只有很少的非零元素，例如只有5個非零的wi耐量，那么我們就有理由相信飞蚓，這些對應的特征在患病分析上面提供的信息是巨大的，決策性的廊蜒。也就是說趴拧，患不患這種病只和這5個因素有關，那醫(yī)生就好分析多了山叮。但如果1000個wi都非0著榴，醫(yī)生面對這1000種因素，累覺不愛屁倔。

二脑又、L2范數(shù)
L2范數(shù): ||W||2也不遜于L1范數(shù)，它有兩個美稱，在回歸里面挂谍，有人把有它的回歸叫“嶺回歸”（Ridge Regression），有人也叫它“權值衰減weight decay”瞎饲。它的強大功效是改善機器學習里面一個非常重要的問題：過擬合口叙。至于過擬合是什么，就是模型訓練時候的誤差很小嗅战，但在測試的時候誤差很大妄田，也就是我們的模型復雜到可以擬合到我們的所有訓練樣本了，但在實際預測新的樣本的時候驮捍，糟糕的一塌糊涂疟呐。通俗的講就是應試能力很強，實際應用能力很差东且。擅長背誦知識启具，卻不懂得靈活利用知識。例如下圖所示（來自Ng的course）：

L2范數(shù)是指向量各元素的平方和然后求平方根菱皆。我們讓L2范數(shù)的規(guī)則項||W||2最小须误，可以使得W的每個元素都很小挨稿，都接近于0，但與L1范數(shù)不同京痢，它不會讓它等于0奶甘，而是接近于0，這里是有很大的區(qū)別的哦祭椰。而越小的參數(shù)說明模型越簡單臭家，越簡單的模型則越不容易產(chǎn)生過擬合現(xiàn)象。為什么越小的參數(shù)說明模型越簡單方淤？我也不懂钉赁，我的理解是：限制了參數(shù)很小，實際上就限制了多項式某些分量的影響很行（看上面線性回歸的模型的那個擬合的圖）你踩，這樣就相當于減少參數(shù)個數(shù)。
這里也一句話總結下：通過L2范數(shù)讳苦，我們可以實現(xiàn)了對模型空間的限制姓蜂，從而在一定程度上避免了過擬合。

L2范數(shù)的好處

1）學習理論的角度：

       從學習理論的角度來說医吊，L2范數(shù)可以防止過擬合钱慢，提升模型的泛化能力。

2）優(yōu)化計算的角度：

       從優(yōu)化或者數(shù)值計算的角度來說卿堂，L2范數(shù)有助于處理 condition number不好的情況下矩陣求逆很困難的問題束莫。

優(yōu)化有兩大難題，一是：局部最小值草描，二是：ill-condition病態(tài)問題穗慕。我們要找的是全局最小值逛绵，如果局部最小值太多怀各，那我們的優(yōu)化算法就很容易陷入局部最小而不能自拔，這很明顯不是觀眾愿意看到的劇情术浪。那下面我們來聊聊ill-condition瓢对。ill-condition對應的是well-condition。那他們分別代表什么胰苏？假設我們有個方程組AX=b硕蛹，我們需要求解X。如果A或者b稍微的改變，會使得X的解發(fā)生很大的改變法焰，那么這個方程組系統(tǒng)就是ill-condition的秧荆，反之就是well-condition的。我們具體舉個例子吧：

對于一個ill-condition的系統(tǒng)蔓搞，我的輸入稍微改變下胰丁，輸出就發(fā)生很大的改變，這不好啊喂分，這表明我們的系統(tǒng)不能實用啊锦庸。你想想看，例如對于一個回歸問題y=f(x)蒲祈，我們是用訓練樣本x去訓練模型f甘萧，使得y盡量輸出我們期待的值，例如0梆掸。那假如我們遇到一個樣本x’幔嗦，這個樣本和訓練樣本x差別很小，面對他沥潭，系統(tǒng)本應該輸出和上面的y差不多的值的邀泉，例如0.00001，最后卻給我輸出了一個0.9999，這很明顯不對呀汇恤。就好像庞钢，你很熟悉的一個人臉上長了個青春痘，你就不認識他了因谎，那你大腦就太差勁了基括，哈哈。所以如果一個系統(tǒng)是ill-conditioned病態(tài)的财岔，我們就會對它的結果產(chǎn)生懷疑风皿。那到底要相信它多少呢？我們得找個標準來衡量吧匠璧，因為有些系統(tǒng)的病沒那么重桐款，它的結果還是可以相信的，不能一刀切吧夷恍。終于回來了魔眨，上面的condition number就是拿來衡量ill-condition系統(tǒng)的可信度的。condition number衡量的是輸入發(fā)生微小變化的時候酿雪，輸出會發(fā)生多大的變化,也就是系統(tǒng)對微小變化的敏感度遏暴。****condition number值小的就是well-conditioned的，大的就是ill-conditioned的指黎。
如果方陣A是非奇異的朋凉，那么A的conditionnumber定義為：

但如果加上L2規(guī)則項，就變成了下面這種情況遗增，就可以直接求逆了：

這里面叫惊，專業(yè)點的描述是：要得到這個解，我們通常并不直接求矩陣的逆做修，而是通過解線性方程組的方式（例如高斯消元法）來計算霍狰÷詹荩考慮沒有規(guī)則項的時候，也就是λ=0的情況蚓耽，如果矩陣XTX的 condition number 很大的話渠牲，解線性方程組就會在數(shù)值上相當不穩(wěn)定，而這個規(guī)則項的引入則可以改善condition number步悠。
另外签杈，如果使用迭代優(yōu)化的算法，condition number 太大仍然會導致問題：它會拖慢迭代的收斂速度鼎兽，而規(guī)則項從優(yōu)化的角度來看答姥，實際上是將目標函數(shù)變成λ-strongly convex（λ強凸）的了。哎喲喲谚咬，這里又出現(xiàn)個λ強凸鹦付，啥叫λ強凸呢？
當f滿足：

直觀來講辑鲤，convex 性質(zhì)是指函數(shù)曲線位于該點處的切線，也就是線性近似之上杠茬，而 strongly convex 則進一步要求位于該處的一個二次函數(shù)上方月褥，也就是說要求函數(shù)不要太“平坦”而是可以保證有一定的“向上彎曲”的趨勢。專業(yè)點說瓢喉，就是convex 可以保證函數(shù)在任意一點都處于它的一階泰勒函數(shù)之上宁赤，而strongly convex可以保證函數(shù)在任意一點都存在一個非常漂亮的二次下界quadratic lower bound。當然這是一個很強的假設栓票，但是同時也是非常重要的假設决左。可能還不好理解逗载，那我們畫個圖來形象的理解下哆窿。

大家一看到上面這個圖就全明白了吧。我們?nèi)∥覀兊淖顑?yōu)解w的地方厉斟。如果我們的函數(shù)f(w)挚躯，見左圖，也就是紅色那個函數(shù)擦秽，都會位于藍色虛線的那根二次函數(shù)之上码荔，這樣就算wt和w離的比較近的時候漩勤，f(wt)和f(w)的值差別還是挺大的，也就是會保證在我們的最優(yōu)解w附近的時候缩搅，還存在較大的梯度值越败，這樣我們才可以在比較少的迭代次數(shù)內(nèi)達到w。但對于右圖硼瓣，紅色的函數(shù)f(w)只約束在一個線性的藍色虛線之上究飞，假設是如右圖的很不幸的情況（非常平坦），那在wt還離我們的最優(yōu)點w很遠的時候堂鲤，我們的近似梯度(f(wt)-f(w))/(wt-w)就已經(jīng)非常小了亿傅，在wt處的近似梯度?f/?w就更小了，這樣通過梯度下降wt+1=wt-α(?f/?w)瘟栖，我們得到的結果就是w的變化非常緩慢葵擎，像蝸牛一樣，非常緩慢的向我們的最優(yōu)點w爬動半哟，那在有限的迭代時間內(nèi)酬滤，它離我們的最優(yōu)點還是很遠。

所以僅僅靠convex 性質(zhì)并不能保證在梯度下降和有限的迭代次數(shù)的情況下得到的點w會是一個比較好的全局最小點w的近似點（插個話寓涨，有地方說盯串，實際上讓迭代在接近最優(yōu)的地方停止，也是一種規(guī)則化或者提高泛化性能的方法）缅茉。正如上面分析的那樣嘴脾，如果f(w)在全局最小點w周圍是非常平坦的情況的話男摧，我們有可能會找到一個很遠的點蔬墩。但如果我們有“強凸”的話，就能對情況做一些控制耗拓，我們就可以得到一個更好的近似解拇颅。至于有多好嘛，這里面有一個bound乔询，這個 bound 的好壞也要取決于strongly convex性質(zhì)中的常數(shù)α的大小樟插。看到這里竿刁，不知道大家學聰明了沒有黄锤。如果要獲得strongly convex怎么做？最簡單的就是往里面加入一項(α/2)||w||2食拜。
實際上鸵熟，在梯度下降中，目標函數(shù)收斂速率的上界實際上是和矩陣XTX的 condition number有關负甸，XTX的 condition number 越小流强，上界就越小痹届，也就是收斂速度會越快。這一個優(yōu)化說了那么多的東西打月。還是來個一句話總結吧：L2范數(shù)不但可以防止過擬合队腐，還可以讓我們的優(yōu)化求解變得穩(wěn)定和快速。*

好了奏篙，這里兌現(xiàn)上面的承諾柴淘，來直觀的聊聊L1和L2的差別，為什么一個讓絕對值最小秘通，一個讓平方最小悠就，會有那么大的差別呢？我看到的有兩種幾何上直觀的解析：

1）下降速度：
我們知道充易，L1和L2都是規(guī)則化的方式梗脾，我們將權值參數(shù)以L1或者L2的方式放到代價函數(shù)里面去。然后模型就會嘗試去最小化這些權值參數(shù)盹靴。而這個最小化就像一個下坡的過程炸茧，L1和L2的差別就在于這個“坡”不同，如下圖：L1就是按絕對值函數(shù)的“坡”下降的稿静，而L2是按二次函數(shù)的“坡”下降梭冠。所以實際上在0附近，L1的下降速度比L2的下降速度要快改备。所以會非晨啬快得降到0。不過我覺得這里解釋的不太中肯悬钳，當然了也不知道是不是自己理解的問題盐捷。

2）模型空間的限制：
實際上，對于L1和L2規(guī)則化的代價函數(shù)來說环疼，我們可以寫成以下形式：

可以看到，L1-ball 與L2-ball 的不同就在于L1在和每個坐標軸相交的地方都有“角”出現(xiàn)，而目標函數(shù)的測地線除非位置擺得非常好够傍，大部分時候都會在角的地方相交。注意到在角的位置就會產(chǎn)生稀疏性锰霜，例如圖中的相交點就有w1=0，而更高維的時候（想象一下三維的L1-ball 是什么樣的桐早？）除了角點以外癣缅，還有很多邊的輪廓也是既有很大的概率成為第一次相交的地方，又會產(chǎn)生稀疏性哄酝。

相比之下友存，L2-ball 就沒有這樣的性質(zhì)，因為沒有角陶衅，所以第一次相交的地方出現(xiàn)在具有稀疏性的位置的概率就變得非常小了屡立。這就從直觀上來解釋了為什么L1-regularization 能產(chǎn)生稀疏性，而L2-regularization 不行的原因了搀军。

因此膨俐，一句話總結就是：L1會趨向于產(chǎn)生少量的特征，而其他的特征都是0罩句，而L2會選擇更多的特征焚刺，這些特征都會接近于0。Lasso在特征選擇時候非常有用门烂，而Ridge就只是一種規(guī)則化而已乳愉。

三、核范數(shù)
核范數(shù) ||W||* 是指矩陣奇異值的和屯远，英文稱呼叫Nuclear Norm蔓姚。這個相對于上面火熱的L1和L2來說，可能大家就會陌生點氓润。那它是干嘛用的呢赂乐？霸氣登場：約束Low-Rank（低秩）薯鳍。OK咖气，OK，那我們得知道Low-Rank是啥挖滤？用來干啥的崩溪？
我們先來回憶下線性代數(shù)里面“秩”到底是啥？舉個簡單的例子吧：

既然秩可以度量相關性瓶埋，而矩陣的相關性實際上有帶有了矩陣的結構信息希柿。如果矩陣之間各行的相關性很強，那么就表示這個矩陣實際可以投影到更低維的線性子空間养筒，也就是用幾個向量就可以完全表達了曾撤，它就是低秩的。所以我們總結的一點就是：如果矩陣表達的是結構性信息晕粪，例如圖像挤悉、用戶-推薦表等等，那么這個矩陣各行之間存在這一定的相關性巫湘，那這個矩陣一般就是低秩的尖啡。

如果X是一個m行n列的數(shù)值矩陣，rank(X)是X的秩剩膘，假如rank (X)遠小于m和n衅斩，則我們稱X是低秩矩陣。低秩矩陣每行或每列都可以用其他的行或列線性表出怠褐，可見它包含大量的冗余信息畏梆。利用這種冗余信息，可以對缺失數(shù)據(jù)進行恢復奈懒，也可以對數(shù)據(jù)進行特征提取奠涌。

好了，低秩有了磷杏，那約束低秩只是約束rank(w)呀溜畅，和我們這節(jié)的核范數(shù)有什么關系呢？他們的關系和L0與L1的關系一樣极祸。因為rank()是非凸的慈格，在優(yōu)化問題里面很難求解，那么就需要尋找它的凸近似來近似它了遥金。對浴捆，你沒猜錯，rank(w)的凸近似就是核范數(shù)||W||*稿械。

四选泻、規(guī)則化參數(shù)的選擇

現(xiàn)在我們回過頭來看看我們的目標函數(shù)：

里面除了loss和規(guī)則項兩塊外，還有一個參數(shù)λ。它也有個霸氣的名字页眯，叫hyper-parameters（超參）梯捕。你不要看它勢單力薄的，它非常重要窝撵。它的取值很大時候會決定我們的模型的性能科阎，事關模型生死。它主要是平衡loss和規(guī)則項這兩項的忿族，λ越大锣笨，就表示規(guī)則項要比模型訓練誤差更重要，也就是相比于要模型擬合我們的數(shù)據(jù)道批，我們更希望我們的模型能滿足我們約束的Ω(w)的特性错英。反之亦然。舉個極端情況隆豹，例如λ=0時椭岩，就沒有后面那一項，代價函數(shù)的最小化全部取決于第一項璃赡，也就是集全力使得輸出和期待輸出差別最小判哥，那什么時候差別最小啊，當然是我們的函數(shù)或者曲線可以經(jīng)過所有的點了碉考，這時候誤差就接近0塌计，也就是過擬合了。它可以復雜的代表或者記憶所有這些樣本侯谁，但對于一個新來的樣本泛化能力就不行了锌仅。畢竟新的樣本會和訓練樣本有差別的嘛。

1.png

L1范數(shù)正則項使解稀疏的解釋
L2正則項使解收縮的解釋
如何讓神經(jīng)網(wǎng)絡收斂得更快.pdf
矩陣求導.pdf

L1正則化的另一個新意在于引入了稀疏性墙贱，從而給模型帶來了解釋性（Model interpretability）热芹，即根據(jù)非零系數(shù)所對應的基的實際意義來解釋模型的實際意義

稀疏表達的作用：

1. 稀疏表達的意義在于降維，且這個降維并不局限于節(jié)省空間惨撇，稀疏表達后的特征向量各維之間的依賴性變低伊脓，更為獨立。
2. 稀疏表達求取時所加的稀疏約束魁衙，使得計算后得到的各個“基”對于解釋數(shù)據(jù)具有相同的重要性报腔，其目的正是嘗試找出隱藏在數(shù)據(jù)背后的解釋因子。

在Machine Learning纺棺，Signal/Image Processing等眾多領域榄笙，很多反問題(Inverse Problem)都是不適定/病態(tài)的(under-determined, ill-posed)。如

y = Ax + \varepsilon, x \in \mathbb{R}^n, A:\mathbb{R}^n \to \mathbb{R}^m, y\in\mathbb{R}^m, m<n, \varepsilon \textrm{ is noise}

[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

梯度下降為什么不適合求解稀疏問題？
稀疏問題一般加一范數(shù)正則項棚蓄，而一范數(shù)不可導堕扶，所以就要用次梯度來替代。
L1雖然是convex但是不differentiable（不可導）梭依。所以無法直接按照常規(guī)的descent來做稍算。比如steepest descent，你需要gradient役拴。
解決L1的方法有很多糊探。比較popular的包括Lasso，把L1 constraint（或者sparse constraint）做成一個regularizer河闰。proximal descent是基于gradient descent但是又兼顧了L1 regularizer科平。

降維和稀疏表達的本質(zhì)區(qū)別
降維是將原space里的數(shù)據(jù)在某一個subspace里進行表達；而稀疏表達則relax了subspace這一條姜性，變成在a union of subspaces里進行表達瞪慧。

inverse problem方面，sparse presentation往往有更加優(yōu)異的表現(xiàn).
Sparse Model相對于Subspace Model（比如降維）而言部念，更加relaxed汞贸，因而具有更強的表達能力。再加上自然信號印机，天然具備可稀疏性矢腻，所以在很多問題中，Sparsity是一個更有效的regularizier射赛。

參考文獻
機器學習中引入L2范數(shù)的意義是什么多柑？
稀疏表達的意義在于？為什么稀疏表達得到廣泛的應用楣责？
為什么sparse representation比起其它成分分析方法（DFT竣灌，Wavelet）能得到更好的效果？
機器學習中的范數(shù)規(guī)則化之（一）L0秆麸、L1與L2范數(shù)
機器學習中的范數(shù)規(guī)則化之（二）核范數(shù)與規(guī)則項參數(shù)選擇
Gradient Descent, Wolfe's Condition and Logistic Regression