矩陣重建的算法與實(shí)現(xiàn)

1、 矩陣重建是信號處理、人工智能和優(yōu)化領(lǐng)域最近研究的熱點(diǎn)?；谕箖?yōu)化的矩陣重建問題衍生于近幾年非常流行的壓縮感知技術(shù)，主要分為矩陣填充和矩陣恢復(fù)問題，是一種重要的數(shù)據(jù)分析工具，在圖像處理、計(jì)算機(jī)視覺、文本分析、推薦系統(tǒng)等方面已經(jīng)找到重要的應(yīng)用。 人工智能分為強(qiáng)人工智能與弱人工智能。強(qiáng)人工智能觀點(diǎn)認(rèn)為有可能制造出真正能推理和解決問題的智能機(jī)器，并且這些機(jī)器將被認(rèn)為是有知覺的、有自我意識的。弱人工智能觀點(diǎn)認(rèn)為不可能制造出能真正地推理和解決問題的智能機(jī)器，這些機(jī)器只不過是智能的，但是并不真正擁有智能，也不會有自主意識。 壓縮感知的概念： 將未知的要獲得的信號記為AK，它是一個波形。我們希望它越不連續(xù)越

2、好，越擴(kuò)散越好，而我所要做的是按照 一定的順序獲得圖像信號的信息。我們按照高斯分布來收集數(shù)據(jù)，而不是線性的，所以我們只會有少量的感測次數(shù)，而這些數(shù)據(jù) 的相關(guān)性非常低。 壓縮的意思，是指比較先前及當(dāng)前數(shù)據(jù)的差異，并記錄下這些差異而減少 需儲存的資料量。對于壓縮感知的問題比壓縮難多了，像是我們要收集怎樣分布的數(shù)據(jù)、如何收集、保留一些什 么系數(shù)，從而得到最佳的結(jié)果。我們會得到一些機(jī)變，保留最大的，最有意義的系數(shù)在里頭。我們可以做一些抽樣，把最重要的保留下來。一個信號，我們知道它是非常好的，但這個信號完全是稀疏的，可能并不是我們要損失掉的。 當(dāng)感興趣的信號是可壓縮的或者可稀疏表示的，那么我們可以通過極

3、少的采樣精確地獲得該信號。壓縮感知中，信號的獲取并不是直接測量信號本身，而是采樣測量信號一個感知矩陣相乘后的信號。 矩陣重建分為矩陣填充（Matrix Completion）和矩陣恢復(fù)（Matrix Recovery）兩大類。前者主要研究如何在數(shù)據(jù)不完整的情況下將缺失數(shù)據(jù)進(jìn)行填充，后者主要研究在某些數(shù)據(jù)受到嚴(yán)重?fù)p壞的情況下恢復(fù)出準(zhǔn)確的矩陣。 研究主要集中在矩陣重建在何種情況下可以準(zhǔn)確地實(shí)現(xiàn)、有沒有快速的算法解決矩陣重建問題和矩陣重建的應(yīng)用。 矩陣填充 對于某個矩陣，我們只能采樣得到矩陣的一部分元素，其它一部分或者大部分元素由于各種原因丟失了或無法得到，假設(shè)這個矩陣是有信息冗余的，比如是低秩的，

4、也就是說其數(shù)據(jù)分布在一個低維的線性子空間上。 可以通過如下優(yōu)化問題來實(shí)現(xiàn)矩陣填充： min rank(X); subject to Xij = Mij ; (i， j) ; 其中是已知元素下標(biāo)的集合。將空缺的元素填充之后使得矩陣的結(jié)構(gòu)盡可能好，即秩盡可能低。 一個矩陣的秩r與它的非零奇異值的個數(shù)相同。于是有一個選擇是用矩陣的奇異值的和，即核范數(shù)，來近似地替代矩陣的秩： min X*; subject to Xij = Mij ; (i，j) ; 矩陣填充的應(yīng)用舉例 矩陣填充的一個著名應(yīng)用是Netflix推薦系統(tǒng)。比賽要求參賽者預(yù)測Netfix客戶分別喜歡什么影片，要把預(yù)測的效率相對原推薦系統(tǒng)C

5、inematch提高10%以上。這是一個典型的矩陣填充問題，即矩陣的每一行對應(yīng)某個用戶對電影的評級，每一列表示某電影在所有用戶中的評級，但是每個用戶只可能對一部分電影進(jìn)行評價，所以我們可以通過矩陣填充得出用戶對每部電影的喜好程度。 矩陣恢復(fù) 當(dāng)矩陣的某些元素被嚴(yán)重破壞后，自動識別出被破壞的元素，恢復(fù)出原矩陣。假定原矩陣有非常良好的結(jié)構(gòu)，即是低秩的；另外，假定只有很少一部分元素被嚴(yán)重破壞，即噪聲是稀疏的但大小可以任意。 min rank(A) + E0; subject to A + E = D; 其中目標(biāo)函數(shù)為矩陣A的秩以及噪聲矩陣E的零范數(shù)，即E的非零元素的個數(shù)，表明噪聲所占的權(quán)重。 矩陣恢

6、復(fù)在背景建模、人臉圖像處理等問題中的應(yīng)用。其中，背景建模利用圖片幀與幀之間的相似性，將每幀作為一列排列成一個矩陣，該矩陣?yán)響?yīng)具備相對較低的秩。于是利用稀疏與低秩矩陣分解技術(shù)可以將每幀中間相似的部分和特有的部分分開，即將背景與前景分離。 一、矩陣填充理論研究主要考慮的是矩陣填充的可行性，即究竟在什么情況下可以精確無誤地把缺失數(shù)據(jù)填充完整。首先，我們需要理解的是，一個雜亂無章的矩陣是不可能進(jìn)行重建的，所以我們假定矩陣結(jié)構(gòu)良好，如低秩。我們不能指望通過采樣可以重建出所有的低秩矩陣，而應(yīng)當(dāng)考慮有多大的概率可以重建。 二、并不是用所有的采樣方式采樣得到的矩陣均能夠重建。例如，當(dāng)矩陣的某一列完全沒有被采樣

7、時，任何方法都不可能將這一列的元素準(zhǔn)確地填充。于是，一般都假定矩陣的采樣方式也是均勻采樣，在這樣的情況下來考慮矩陣精確重建的概率。 三、采樣的矩陣元素?cái)?shù)目必須大于一定范圍時，才有可能將矩陣進(jìn)行精確填充。 一種簡單的一階方法，奇異值閾值（Singular ValueThresholding，簡稱SVT）算法，來求解矩陣填充問題。矩陣填充問題可以寫為： min X*; subject to P(X) = P（M); 其中表示所有的采樣元素的坐標(biāo)(i; j)的集合，P(X) 表示一種投影算子，它將矩陣在以外的元素置0，內(nèi)部元素保持不變。 SVT算法可以理解為一種拉格朗日乘子法。首先，它求解的是原問題的一個近似問題： Algorithm 1 (矩陣填充的SVT算法) 序列Xk始終低秩，可以表示成兩個瘦矩陣Uk與V kT之積，而Yk始終是稀疏的，由于這些性質(zhì)，該算法執(zhí)行過程內(nèi)存需求大大降低，因此適合大規(guī)模矩陣的計(jì)算。 APG（Accelerated Proximal Gradient）算法是一種利用Nesterov技巧的一階算法，其收斂速度很有競爭力。將矩陣填充問題轉(zhuǎn)化為一個與原問題近似的無約束優(yōu)化問題： 矩陣恢復(fù)的可行性 橫坐標(biāo)為r/n，縱坐標(biāo)為損壞元素所占比率。白色表示精確恢復(fù)，黑色表示不能恢復(fù)，灰色表示一定概率恢復(fù)。從圖中可以看出，當(dāng)矩陣的秩越低，被損壞的元素?cái)?shù)目越