了解機器學習的人應該都知道，在優(yōu)化非凸函數(shù)的時候，希望用一個凸函數(shù)來代替這個非凸函數(shù)，以獲取凸函數(shù)在優(yōu)化過程中良好的性質(zhì)。比如RPCA里，sparse部分的L0 norm用L1 norm來代替，low-rank部分的rank用nuclear norm（核范數(shù)）來代替。L0和rank是非凸的，L1和nuclear norm是凸函數(shù)，但為什么這樣的approximation（在某種意義下）是最佳的呢？
之前在網(wǎng)上搜了蠻久沒有得到一個完整的答案，前幾天課后跟老板談?wù)撈疬@個問題，給我發(fā)了點reference，算是徹底解決了這個問題。簡書不太熟（改天查一下怎么在簡書上使用markdown or latex），所以先直接貼圖吧，最后把reference附上，以便查閱。
首先簡單說一下convex function的knowledge和這里的notation。
然后是Convex conjugate的概念：
看到這里就應該明白了為什么the biconjugate of F是F的“最佳凸估計”（convex relaxation）。
也就是說：biconjugate是小于原函數(shù)且epi為閉集（lower semicontinuous等價于epi close）的最大的凸函數(shù)。實際上就是把原函數(shù)的epi 做convex hull+closure（變成閉集），這個性質(zhì)跟dual cone很像，二次對偶后變成了以前cone做convex hull+closure。
其實L1 norm是L0 norm的biconjugate，nuclear norm是rank的biconjugate，所以很容易理解為什么我們要用L1 norm來代替L0 norm，為什么用nuclear norm來代替rank了。
L1為什么是L0的biconjugate：
在x的L_inf不大于1的情況下（重要?。?/p>
nuclear norm是rank的biconjugate其實可以看作是上面的推論。簡單說一下idea，任給一個m*n的矩陣M，對M做奇異值分解（其實就是實對稱矩陣譜分解的推廣），奇異值的個數(shù)就是矩陣的rank（是不是很像L0 norm，非0就是1），類似做biconjugate就是所有奇異值絕對值的和，而奇異值本身就是非負的，所以就是奇異值的和（這貨就是nuclear norm嘛?。?。
Reference:
1. Foucart S, Rauhut H. A mathematical introduction to compressive sensing[M]. Basel: Birkh?user, 2013.
2. https://www.quora.com/Why-is-L1-norm-the-tightest-convex-relaxation-of-L0-norm-in-convex-optimazation
有興趣的可以看看:
3. Rockafellar R T. Convex analysis[M]. Princeton university press, 2015. （重點推薦?。?！）
4. Boyd S, Vandenberghe L. Convex optimization[M]. Cambridge university press, 2004.
