基于矩陣RIP條件的低秩矩陣恢復(fù)算法

蔡云 石瑩

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

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

中圖分類號(hào)：O29文獻(xiàn)標(biāo)識(shí)碼：A

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

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

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

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

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

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

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

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

ε，

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

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

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

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

rSymbolcB@

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

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

‖A（X）‖22SymbolcB@

（1+δr）‖X‖2F

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

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

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

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

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

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

ε，

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

四、最新RIP研究進(jìn)展

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

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

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

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

參考文獻(xiàn)：

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

[2]蔡云.稀疏逼近中幾個(gè)經(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.