信号和数据处理中低秩模型——理论、算法和应用.PDF

信号与数据处理中的低秩模型——理论、算法与应用* 林宙辰1 马毅2 1 北京大学机器感知与智能教育部重点实验室，北京100871 2 上海科技大学信息学院，上海201210 1. 引言 我们正处于大数据时代。大数据的特点，除了大家津津乐道的4 个V （Volume, Variety, Velocity, 和Value ）外也经常是高维的。例如，用千万像素相机拍一张照片，就是在千万维空间里采了一个样 本。因此，如何鲁棒高效地处理高维数据是一个重大的挑战。幸运的是，高维数据并不是毫无结构 的。一个显著的特点是它们经常分布在低维流形附近，这事实上就是流形学习的基本假设。这个特 点也经常被事实所验证，比如对数据做主成分分析（Principal Component Analysis, PCA ）时，往往 95% 以上的能量都集中在少数几个主方向上，这就说明数据是分布在低维子空间附近的。因此，充 分利用数据分布的低维特性来鲁棒高效地处理高维数据是一个重要的途径。传统的流形学习属于这 个范畴，但是传统的流形学习对方法的正确性缺乏深入的理论分析，因此其性能没有保障，尤其是 当数据带强噪声、有损毁或缺失时甚至可能失效，而这样的数据是现实中大量存在的。 基于低秩的模型是近年涌现出来的鲁棒高效地处理高维数据的新工具。虽然秩在统计学中早已 被用作矩阵的正则化子，如减秩回归（Reduced Rank Regression, RRR ）；在三维立体视觉里，秩约束 更是随处可见，但是近年低秩模型的兴起却是受取得了巨大成功的稀疏表示（Sparse Representation ） 和压缩传感（Compressed Sensing ）理论的推动，由此系统地发展出了新的理论与应用。在此背景下， 1 秩被阐释为二阶 （即矩阵）稀疏性 的度量，而不仅仅是一个数学概念。为了说明这一点，我们举图 像或视频压缩为例，要实现有效地压缩，必须充分利用图像或视频的时间或空间相关性；又如Netflix 2 挑战 （图1），要推断未知的用户评价，需要充分考虑用户喜好的相关性和视频类别的相关性。矩阵 行列间的相关性天然地和矩阵的秩关联在一起。因此，把秩定义为二阶稀疏性度量是很自然的。 下面以我们的工作为基础，简要介绍这方面的进展。我们先介绍线性模型，再介绍非线性模型， 然后是常用求解算法，接下来是代表性应用，最后总结；其中线性模型分单子空间模型和多子空间 模型，优化算法分凸优化和非凸优化。 * 本文得到国家自然科学基金资助。 1一阶稀疏性就是向量的稀疏性，其度量为非零元的个数，即l0 范数 . 0 2 Netflix 是一家视频租赁公司，拥有很多用户对视频的评价，但这个用户/视频评价矩阵非常稀疏。该公司提供 100 万美元奖金希望能够把预测用户对视频的评价的准确率提高10%，以便有针对性地推荐，从而提高营收。见 / 1 图1 Netflix 挑战。需要预测用户对其未评价过的视频的喜好程度。 2. 线性模型 近年低秩模型的兴起大致开始于E. Candès 2008 年提出的矩阵填充（Matrix Completion, MC ）问 题[CR2009] 。我们先介绍线性模型。虽然看上去比较简单，但是理论分析表明线性模型对强噪声和 缺失数据非常鲁棒，在应用中其实也具有足够的数据表达能力。 a) 单子空间模型 E. Candès 2008 年提出的MC 问题[CR2009]是：已知某矩阵 在某些位置的值，可否恢复出该 D 矩阵？这是一个广泛的数学模型，如上面提到的Netflix 挑战、基因微阵列测量等。显然这个问题的 答案是不确定的，鉴于上面提到的需要考虑矩阵行列间的相关性，他建议选秩最小的那个解 ：