蔡云 石莹

摘 要：低秩矩阵恢复问题考虑从较少的线性测量信号中来恢复一个未知的低秩的矩阵，该问题在高维图像处理等有着广泛的应用。本文主要介绍低秩矩阵恢复的一些数学背景以及常用的恢复算法，最后给出基于矩阵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.