从压缩传感到低秩矩阵恢复:理论与应用  

From Compressed Sensing to Low-rank Matrix Recovery:Theory and Applications

作　　者：彭义刚[1,2] 索津莉[1] 戴琼海[1] 徐文立[1] 

机构地区：[1]清华大学清华国家信息实验室,清华大学自动化系,北京100084 [2]国家计算机网络应急技术处理协调中心,北京100029

出　　处：《自动化学报》2013年第7期981-994,共14页Acta Automatica Sinica

基　　金：国家重点基础研究发展计划(973计划)(2010CB731800);国家自然科学基金(61035002;61171119)资助~~

摘　　要：综述了压缩传感、矩阵秩最小化和低秩矩阵恢复等方面的基础理论及典型应用.基于凸优化的压缩传感及由其衍生的矩阵秩最小化和低秩矩阵恢复是近年来的研究热点,在信号处理、推荐系统、高维数据分析、图像处理、计算机视觉等很多研究领域具有重要和成功的应用.在这些实际的应用中,往往涉及到对高维数据的分析与处理,需要充分和合理利用数据中的如稀疏性或其所构成矩阵的低秩性等性质.尽管在最坏情况下,最小化诸如稀疏性或矩阵秩这样的目标函数是NP难的,但是在某些合理的假设条件下,通过优化目标函数的凸松弛替代函数,采用凸优化的方法,能够精确地给出原问题的最优解.有很多高效的凸优化算法对之进行求解且适用于大规模问题.本文首先分别综述了压缩传感、矩阵秩最小化和低秩矩阵恢复的相关基础理论,然后对其在图像处理、计算机视觉和计算摄像学等领域的典型应用予以举例介绍,并展望了相关领域未来的研究工作.This paper reviews the basic theory and typical applications of compressed sensing,matrix rank minimization,and low-rank matrix recovery.Compressed sensing based on convex optimization and related matrix rank minimization and low-rank matrix recovery are hot research topics in recent years.They find many important and successful applications in different research fields,including signal processing,recommending system,high-dimensional data analysis,image processing,computer vision and many others.In these real applications,analysis and processing of high-dimensional data are often involved,which needs to utilize the structure of data,such as sparsity or low rank property of the data matrix,sufficiently and reasonably.Although minimization of objective functions like sparsity or matrix rank is NP-hard in the worst case,by optimizing the convex relaxation of the original objective function under certain reasonable assumptions,convex optimization could give the optimal solution of the original problem.Moreover,many efficient convex optimization algorithms could be used for solving the problem and are also applicable to large-scale problems.In this paper,we first review the fundamental theories about compressed sensing,matrix rank minimization,and low-rank matrix recovery.Then,we introduce the typical applications of these theories in image processing,computer vision,and computational photography.We also look into the future work in related research areas.

关 键 词：压缩传感 矩阵秩最小化 低秩矩阵恢复 凸优化 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]