蔡云 石瑩

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

關(guān)鍵詞：低秩矩陣恢復(fù);矩陣RIP條件;恢復(fù)算法

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

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

一、低秩矩陣恢復(fù)

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

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

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

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

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

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

ε，

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

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

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

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

rSymbolcB@

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

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

‖A（X）‖22SymbolcB@

（1+δr）‖X‖2F

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

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

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

三、其它恢復(fù)方法

類似于壓縮感知問題，除了凸優(yōu)化方法外，研究者們也?？紤]使用非凸優(yōu)化的方法來替代秩最小化方法，即考慮使用矩陣的非凸奇異值范數(shù)‖X‖pp代替矩陣的最小秩：

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

ε，

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

四、最新RIP研究進展

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

定理1：考慮恢復(fù)模型（1），當0

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

Cε，其中C為常數(shù)。

參考文獻：

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

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

[3]章瑞.壓縮感知中最優(yōu)限制等距常數(shù)界[M].浙江大學(xué)博士學(xué)位論文，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.