Recovering Low-Rank Matrices From Few Coef?cients In Any Basis-David Gross
引
依舊是一個重構(gòu)矩陣的問題，這篇論文的符號有些奇怪，注意一下。假設(shè)有一個矩陣,其秩為
。有一組基
，是已知的。假設(shè)我們觀測到的是，一組內(nèi)積
，其中
，
表示
的共軛轉(zhuǎn)置。在這些條件下，我們是否能夠從
中恢復(fù)出
。
一些符號說明：
為
的奇異值之和，即此為矩陣核范數(shù)。
為
的F范數(shù)，而非一般符號代表的譜范數(shù)。
為
的譜范數(shù)。
作者強(qiáng)調(diào)，這個問題，是可以辦到的，不過其基需要滿足一個coherence條件：
在這里插入圖片描述
且，即為酉矩陣（不過作者提到，似乎即便不滿足此條件，也可以通過一種轉(zhuǎn)化來求解）。
主要結(jié)果
作者通過求解下述問題來恢復(fù)矩陣:
在這里插入圖片描述
需要指明的一點是，如果中大部分為0，那么想要恢復(fù)出是非常困難的（因為這意味著我們可用的信息非常少）。
定理2，3
下為定理2，其中的標(biāo)準(zhǔn)基為：，即僅有
行
列元素為1，其余均為0的
矩陣所構(gòu)成的基。
在這里插入圖片描述
作者的結(jié)論更為一般，可以拓展到任意的基：
在這里插入圖片描述
定理4
接下來還有定理4：
在這里插入圖片描述
定理4針對的是一種特殊的基——Fourier-type基，介紹此的原因是，作者先證明此定理，再通過一些轉(zhuǎn)換來證明定理3的。
直觀解釋
作者通過倆幅圖，給出了一些直觀的解釋。
在這里插入圖片描述
先來看(a)。我們可以將整個線性空間分成和。因為我們已有的信息是，問題(1)中滿足約束的矩陣在空間中形成一個超平面，即圖中的，而我們所期望的是其中的一點。
再來看(b)，因為我們希望的是是問題(1)的最優(yōu)解，最好還是唯一的。如果真的如此，那么
這個集合只能在平面
的上方或者下方，實際上，就是平面A是
的支撐超平面，其支撐點為
。
當(dāng)然，這個性質(zhì)并沒有這么容易達(dá)成，其等價于要滿足：
對于中任意的點
成立。但是呢，直接證明是困難的，所以作者尋求一個對偶條件即下式：
關(guān)于某個成立，而且
必須與超平面
垂直。這個
能否找到，就是
能否恢復(fù)的關(guān)鍵。
