英语原文共 12 页，剩余内容已隐藏，支付完成后下载完整资料
噪声环境下的矩阵补全
可以通过相对少量的示例准确地做出关于可能参与选择的项目的选择性预测，例如电影租借。
摘要
最近一个新的领域随着压缩感知出现了。该领域解决了大量有实际意义的问题，即从看起来不完整的，甚至可能是损坏的信息中恢复数据矩阵。其最简单的形式是从一个小样本的元素中恢复矩阵。它出现在许多科学和工程的领域，例如协同过滤，机器学习，控制，遥感和计算机视觉等。本文研究了关于矩阵补全的最新文献，其表明在一些适当的条件下，通过求解简单的凸优化问题，即核范数最小化，可以从近似最小的元素集合中恢复一个未知的低秩矩阵以满足数据约束。此外，本文介绍了一些新的研究结果，即当少量的观察元素被少量噪声破坏时，矩阵补全也可证明是准确的。典型的结果是，人们可以从具有与噪声电平成比例的有误差的大约nr个噪声样本中恢复未知的秩为r的n * n低秩矩阵。我们得出的数值结果补充我们的定量分析，并表明，在实践中，核范数最小化准确地填充了来自只有几个噪声样本的大型低秩矩阵的许多缺失元素。在本论文中也讨论了一些矩阵补全和压缩感知之间的对比。
关键词：压缩感知；二元性优化；低秩矩阵；矩阵补全；核范数最小化；oracle不等式；半正定规划
一、介绍
想象一下，我们只观察一个信号的几个样本。那么是否有可能精确或准确地重建此信号呢？例如，假设我们观察到一个数字信号或图像的向量的几个元素。我们可以恢复像素的大部分元素，是否你会说，不可能得到？一般来说，每个人都会认为这是不可能的。然而，如果已知信号在傅里叶域中是稀疏的，并且通过扩展，在非相干域中，则可以通过最小化进行准确，甚至精确地恢复[11];其他算法参见[22]，其他类型的测量参见[17]和[18]，不同想法参见[34]。这个理论是快速发展的压缩感知领域的根本，并且已经改变了工程师思考数据采集的方式;因此本特刊和其他（例如见[2]）。具体地说，如果一个信号具有稀疏的频谱，并且我们仅有几个关于时间或空间样本的信息，则可以调用线性规划以实现信号精确内插。当然交换时间（或空间）和频率，也可以从它们的几个傅立叶系数中恢复稀疏信号。
假设我们现在只观察数据矩阵的几个元素。那么是否可以准确地地猜测我们没有看到的元素？例如，假设我们从大数据矩阵中观察到一些电影评分，其中行是用户，列是电影（我们只能观察到几个评分，因为每个用户通常只会评价几部电影，而不是有数以万计的电影信息可用）。我们可以预测用户给他/她没有看过的电影的评分吗？一般来说，每个人都认为从其元素的子集恢复数据矩阵是不可能的。然而，如果已知未知矩阵是低秩或近似低秩的，则通过核范数最小化可以进行准确地恢复[10]，[14]。这一理论就是本文的主题，在某种程度上它是基于压缩感知的大量工作的基础之上得到的。
从现在起，我们将把许多缺失的元素推断的问题转换为矩阵补全问题。通过扩展，从仅仅几个线性函数推断矩阵问题将被称为低秩矩阵恢复问题。现在对于稀疏信号的恢复可以说是最重要的，但一般来说，我们确信，矩阵补全，低秩矩阵恢复同样重要，并将在未来几年会有越来越多的研究。现在，我们给出一些出现了这些问题的应用程序的例子。
协同过滤。简而言之，协同过滤是通过从许多用户收集品味信息来做出关于用户兴趣的自动预测的任务[23]。也许协同过滤最著名的实例是前面提到的Netflix推荐系统，其试图对不可见的电影进行评级预测。这是一个矩阵补全的问题，其中所述未知全矩阵具有近似低秩特性，因为只有少数因素有助于判断个人的喜好或偏好。在新经济中，公司对预测音乐喜好（苹果公司），文学偏好（亚马逊，巴恩斯和来宝）和许多其他这样的事情感兴趣。
系统识别。在控制应用中，人们想要将离散时间线性时不变状态空间模型拟合到输入序列中并输出。
向量是系统在时间t的状态，n是系统模型的阶数。从输入/输出对中，人们想要恢复状态向量n（模型阶数）的维度和系统的动态，即矩阵A，B，C，D和初始状态。这个问题可以转换为低秩矩阵的补全问题;见[26]及其中的参考文献。
全球定位。从局部或部分成对距离集中找到欧几里得空间中的点的全局定位是在传感器网络中经常出现的几何问题[7]，[31]，[32]。例如，由于功率约束，传感器可能仅能够从其邻近点构建可靠的距离估计。从这些估计中，我们可以得到部分的观察距离矩阵，而问题是仅仅从几个观察到的距离的所有的距离做出推断，使得其可靠地估计传感器的位置。将其还原到矩阵补全问题中，如果传感器位于平面中，则未知矩阵秩为2，如果传感器位于空间中，则秩为3。
遥感。MUSIC算法[30]经常用于确定相干射频环境中入射信号的到达方向。在典型的应用中，输入信号被用于记录各种传感器位置，并且该算法通过计算所有传感器对接收信号的相关性，从而获得的协方差矩阵中提取波到达的方向来完成操作。在遥感应用中，由于功率约束，可能无法估计或传输所有相关性[35]。在这种情况下，我们希望能够从几个观察到的部分相关性推断出完整的协方差矩阵。这也可以作为一个矩阵补全问题，其中未知信号协方差矩阵是低秩的，因为它等于入射波的数量，其通常远小于传感器的数量。
当然还有许多其他例子，包括计算机视觉中的运动结构问题[15]，[33]，数据分析中的多类学习[3]，[4]等等。
本文研究是否可以从较少的元素恢复低秩矩阵，如果可以，应该如何做，并且怎样做好。在第二部分中，我们将在无噪声环境下研究，其中观察到的元素正是未知矩阵的。第三部分检验了较少见的元素被噪声破坏的一般情况。我们用几个数值实验来补充我们的研究，证明我们的方法在第四节中的可行性，并做一个简短的结束讨论（第五节）。
在开始之前，以下是本文中使用的符号的摘要。我们将使用具有奇异值的矩阵的三个范数。频谱范数由表示，并且是最大奇异值。两个矩阵之间的欧几里德内积由公式定义，相应的欧几里得范数称为Frobenius范数，用表示（注意，这是奇异值向量的范数）。核范数由表示，并且是奇异值的总和（向量的范数）。定义表示是正半定子。
此外，我们还将处理作用于空间的线性变换，将使用书法字母作为这些运算符，如。特别地，该空间上的同一性运算符将由表示。我们使用与上面相同的约定，表示（被视为一个大矩阵）是正半定的矩阵。
我们使用一般的渐近符号，例如写入O（M）以表示对于一些CM绝对常数Cgt; 0的幅度限制量。
二、矩阵的精准补全
此后，是我们希望尽可能精确地知道的矩阵。然而，唯一可用的关于M的信息是元素的采样集合，其中是元素的完整集合的子集。(在这里和在后续中，表示列表{1,...,n}。)通过来总结可用的信息，其中采样算子由下式定义
因此，问题是是否有可能仅从信息中恢复我们的矩阵。假设在没有替换的情况下随机选择元素，以避免行或列出现未采样的情况，因为在这种情况下矩阵补全显然是不可能的。（如果我们没有特定用户的数据，应该如何猜测他/她的偏好？如果我们没有关于特定传感器的距离估计，应该如何猜测它到所有传感器的距离？）
即便使用的未知矩阵M是低秩的，但这种情况也可能存在很大的问题。有一个示例可以解释：让x是中的一个向量，并考虑秩为1的矩阵
其中是规范基中的第一个向量。显然，该矩阵不能从其元素的子集中恢复。即使可以看到随机抽样的95％的元素，但是错过第一行中的元素的概率也非常高，这就使得矢量x的恢复和M的扩展变得不可能了。类比压缩传感，显然不能通过在时域中进行子采样来恢复在时域中假定为稀疏的信号。
这个示例表明如果矩阵的奇异向量的一些奇异向量极端稀疏，则不能补全矩阵，也不能在不对第一行中的所有元素进行采样的情况下恢复M;其他相关实例见[10]。更普遍地情况，如果行（或列）在其近似正交的意义上与其他行（或列）没有关系，则基本上需要看到该行中的所有元素以恢复矩阵M。这样的非正式考虑导致[10]的作者提出了几何不相干假设，但目前，我们将讨论一个更简单的概念，强迫M的奇异向量扩散到所有坐标。为了阐述这种情况，回想秩为r的矩阵的奇异值分解（SVD），其中是奇异值，是奇异向量。
(Ⅱ.1)
我们作如下假设：
(Ⅱ.2)
对于，其中范数由定义。我们可以认为mu;B是小的，例如O（1），这使得奇异向量不是如上所述的太尖锐。
如果M的奇异向量被充分地展开，我们期望存在与观察到的元素一致的唯一的低秩矩阵。如果是这种情况，理论上可以通过求解
(Ⅱ.3)
来恢复未知矩阵，其中是决策变量。然而不幸的是，这个问题不仅是NP-hard问题，而且所有已知的算法在理论和实践中都是双指数的[16]。这类似于最小化在稀疏信号恢复中的难处理性。
一种通用的替代方案是凸松弛[10]，[14]，[19]，[21]，[29]（参见早先相关的[6]和[28]）。
(Ⅱ.4)
正如最小化是在的个球单位归一的稀疏向量（具有至多一个非零项的向量）的凸包的意义上的组合，最小化问题的最紧密的凸松弛，核范数最小化是NP-hard秩最小化问题的最紧密的凸放松。可以肯定的是，核球是具有由上述限定的光谱范围的一组矩阵的凸包。此外，在压缩感知中，受到线性等式约束的最小化可以被转换为用于范数的线性规划（LP）表征：实际上，对于每个，是具有决策变量的
的最优值。同样，的核规范具有SDP特征
(Ⅱ.5)
其具有决策变量。这说明光谱规范对核准则具有双重性。对W的频谱范数的约束是SDP约束，因为它等价于
其中是单位矩阵。因此，（II.4）是SDP约束，其可以通过将写为SDP的最优值对（II.5）来表达。我们可以看到，利用问题结构的专门算法已经被证明比内点方法优于几个数量级（见[8]和[27]）。在文献[14]中，证明核范数最小化可能通过任何方法恢复成功。
定理1 [14]：令为的固定矩阵服从（II.2）并设置。假设我们观察到随机抽样均匀的矩阵M的m项。然后存在正数值常数C，使得如果
(Ⅱ.6)
则M是具有至少为的概率的（II.4）的唯一解。换句话说，以高概率，核范数最小化恢复M的所有元素是可行的。
从侧面来看，通过对于一些通用常数取形式的（II.6）中的C，可以针对给定的获得至少的成功概率。该结果的概率性质源自以下假设：显示M的元素从均匀分布中采样。另一个解释是矩阵补全是精确的“大多数”采样集服从式（II.6）。
秩为r的矩阵取决于自由度。当r很小时，自由度的数目远小于，这就是为什么可以进行子采样的原因。（在压缩传感中，自由度的数目对应于信号的稀疏度，即非零项的数目）。应当注意的是，一旦样本大小超过自由度的数量，通过几对对数因子，就会发生核范数最小化的精确恢复。此外，观察到，如果完全错过其中一行（例如，一个没有关于用户的评级）或一个列（例如，一个没有关于电影的评级），则人们不可能希望恢复形式为秩为1的矩阵。因此，需要对矩阵的每一行（以及每一列）进行采样。当随机抽样时，可以肯定的是，至少有个发生这种情况，这是著名的优惠券收集器的问题。因此，（II.6）最多丢失了信息理论上极限是一个对数因子。
为了使所有秩的值获得相似的结果，[14]引入了具有下面所述的参数的强不相干属性。
- 使（分别地，）是奇异向量（分别地，）上的正交投影。对于所有对和。
B)设E是由（II.7）定义的“符号矩阵”
(Ⅱ.7)
对于所有的
上述情况中没有作任何关于奇异值的假设。正如我们将看到的，具有较小值的强不相干参数的不相干矩阵可以从最小的元素集合中恢复。在得出上述结果之前，我们要注意许多模型矩阵服从具有小值的强不相干属性。
假设单数向量遵守（II.2）与（奇异向量不尖锐）。并且除了很少的特殊矩阵外，M遵守与的强不相干属性。
假设存在列矩阵和是独立的随机正交矩阵。然后在高概率和条件下，M服从与的强不相干属性，以避免小样本效果。
下面的抽样是在一般的，非渐近的，和最佳的几个对数因子的情况下得到的。
定理2 [14]：令是具有强不相干参数的固定秩为r的矩阵，并且设置。假设我们观察到M的随机均匀抽样的位置的m项。然后存在数值常数C，使得如果
则M是（II.4）的唯一解的概率至少为。
换句话说，如果矩阵是强非相干的，并且采样集的基数大约是自由度的数量乘以几个对数因子，则核范数最小化是精确的。这改进了Candegrave;s和Recht [10]的早期结果，他们在有很小差别的假设下证明了，在个样本的阶数上，至少对于符合的秩的值是足够的。
我们想得出一个相似性质的结果，但是具有完全不同的恢复算法和稍微不同的适用范围，这是由Keshavan等人建立的[24]。它们的条件与在[10]中引入的不相干属性相关，并且也有许多合理的随机矩阵模型满足。然而，存在另一个条件，其表示未知矩阵的奇异值不能太大或太小（顶值和最小值之间的比率必须是有界的）。该算法1）修剪了每个具有太多元素的行和列;即将那些行和列中的元素替换为零;2）计算修剪矩阵的SVD，将其截断以仅保持顶部r个奇异值（
全文共11721字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[142690]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
