基于矩陣RIP條件的低秩矩陣恢復算法

蔡云 石瑩

摘?要：低秩矩陣恢復問題考慮從較少的線性測量信號中來恢復一個未知的低秩的矩陣，該問題在高維圖像處理等有著廣泛的應用。本文主要介紹低秩矩陣恢復的一些數學背景以及常用的恢復算法，最后給出基于矩陣RIP條件的恢復結果。

關鍵詞：低秩矩陣恢復;矩陣RIP條件;恢復算法

中圖分類號：O29文獻標識碼：A

近年來，考慮從較少的線性測量信號中恢復未知的高維稀疏信號的問題即壓縮感知問題已經成為了熱點研究問題，并引起了國內外研究者們的高度關注，已經在許多領域產生了重要的應用，并取得了許多重要的研究成果，谷歌學術上有關壓縮感知的學術論文數以千計，并激發了包括應用數學、統計、計算機科學、工程等領域研究者們的極大的興趣，成為近十余年來最熱門的研究方向。低秩矩陣恢復問題是壓縮感知的推廣問題，此時要恢復的是一個矩陣，即考慮從線性觀測向量中來恢復一個未知的矩陣。這樣的問題中在實際應用中普遍存在，例如圖像處理、音頻和視頻處理、文本及語義分析等，最特別的例子就是Netflix百萬大獎問題等。因此，低秩矩陣恢復問題也得到了研究者門的高度關注，在信號處理、模式識別、在線推薦系統等方面已經有了廣泛的應用。[1-2]

一、低秩矩陣恢復

在低秩矩陣恢復問題中，我們有觀測模型y=A（X）+z，其中y∈Rm是測量向量，A∈R?n1×n2→Rm（mSymbolcB@

n1n2）是線性測量算子，z∈Rm是測量噪聲。研究目標是從已知的觀測向量y和測量算子A中來恢復未知的矩陣X。一個特別情況是矩陣填充問題，在矩陣填充中我們得到的觀測值是矩陣X的部分已知元素構成的矩陣，矩陣填充問題是矩陣恢復的一個特例，而且矩陣填充最著名的例子是美國的Netflix百萬大獎問題，該問題實際上也是一個在線推薦系統問題，在現實生活中廣泛存在，對人們的購物消費等習慣具有較好的指引作用。

注意到低秩矩陣恢復問題實際上是壓縮感知問題在高維上的推廣問題，當矩陣X是一個對角矩陣時，低秩矩陣恢復問題就變成壓縮感知問題y=Ax+z，但實際上無論低秩矩陣恢復問題還是壓縮感知問題都是病態的反問題。只有當對未知數據賦以某種特殊結構如假定未知矩陣X是低秩的、未知向量x是稀疏時，這兩個問題才有研究意義。我們稱矩陣X是秩r矩陣即矩陣X的非零奇異值的個數最多為r個。

低秩矩陣恢復問題最直接的解決方法是求解如下的秩最小化問題：

其中ε是噪聲界。類似于壓縮感知中的零范數最小化問題，上述的秩最小化問題也是NP-難問題且在計算上是不可行。很自然的，研究者們開始使用秩最小化問題的凸松弛問題即核范數最小化問題來求解：

min‖X‖*，s.t.‖A（X）-y‖2SymbolcB@

ε，

其中‖X‖*表示矩陣X的奇異值之和。上述的核范數最小化問題是一個凸優化問題因此可以使用許多凸優化的算法來求解。

二、矩陣約束等距條件（M-RIP條件）

類似于壓縮感知問題，秩最小化問題與核范數最小化問題的解在什么條件下一致是研究者們所關心的問題。文獻中常見的有三個條件：不相干性假設、矩陣零空間條件及矩陣約束等距條件。在這三個條件中最常用的是矩陣RIP條件，最早由M.Fazel提出，是信號約束等距條件在高維空間中的推廣條件。定義如下：

定義1：對于線性測量影射A∈R?n1×n2→Rm和正整數1SymbolcB@

rSymbolcB@

minn1，n2，對于所有的秩r矩陣X∈R?n1×n2，測量影射A的r階矩陣約束等距常數（M-RIC）δr定義為滿足下面不等式的最小常數：

（1-δr）‖X‖2FSymbolcB@

‖A（X）‖22SymbolcB@

（1+δr）‖X‖2F

如果有上述不等式成立，則稱線性測量影射A滿足r階矩陣RIP條件。

E.Candes等學者證明了當線性測量影射A滿足如下的集中不等式：對于任意給定的X∈R?n1×n2和固定0<δ<1和常數c，t>0，P（‖A（X）‖22-‖X‖2F）ce?-tmδ2，那么當測量次數mcδ2nr，線性測量影射A以極大概率滿足矩陣RIP條件且矩陣RIC常數滿足δrSymbolcB@

δ。因此，許多隨機測量影射例如高斯、次高斯以及部分隨機傅立葉等隨機測量影射都以大概率滿足矩陣RIP條件。[2]

三、其它恢復方法

類似于壓縮感知問題，除了凸優化方法外，研究者們也常考慮使用非凸優化的方法來替代秩最小化方法，即考慮使用矩陣的非凸奇異值范數‖X‖pp代替矩陣的最小秩：

min‖X‖pp，s.t.‖A（X）-y‖2SymbolcB@

ε，

其中‖X‖pp表示矩陣奇異值向量的非凸lp（0

四、最新RIP研究進展

有許多學者對問題（1）進行了研究，特別地針對基于矩陣RIP條件的恢復，M.Fazel等指出當測量映射A滿足矩陣RIPδ5r<110時，核范數最小化問題（1）與秩最小化問題等價。之后又有許多學者對這個界進行了改進，例如 Cai和Zhang給出δ2r<0.5，之后他們又給出δ2r<22是最優界。[4]對于高階RIP恢復條件的研究，最近Zhang和Li給出了一個公認的最優結果，為了完整起見，我們簡要列出定理內容，具體可參見文獻[3]。

定理1：考慮恢復模型（1），當0

ε時，對于秩r矩陣X那么（1）的最優解X*滿足‖X*-X‖2SymbolcB@

Cε，其中C為常數。

參考文獻：

[1]M.Fazel.Matrix rank minimization with applications[M].PHD thesis，Stanford niversity，2002.

[2]蔡云.稀疏逼近中幾個經典算法的理論分析[M].浙江大學博士學位論文，2015.

[3]章瑞.壓縮感知中最優限制等距常數界[M].浙江大學博士學位論文，2017.

[4]T.Cai，A.Zhang，Sparse representation of a polytope and recovery of sparse signals and low rank matrices[J].IEEE Transactions on information theory，2014，60（1）：122-132.