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

彭义刚; 索津莉; 戴琼海; 徐文立

doi:10.3724/SP.J.1004.2013.00981

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

doi: 10.3724/SP.J.1004.2013.00981

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

基金项目:

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

详细信息

通讯作者:
彭义刚

计量
- 文章访问数: 4363
- HTML全文浏览量: 130
- PDF下载量: 3849
- 被引次数: 0
出版历程
- 收稿日期: 2012-02-20
- 修回日期: 2012-10-31
- 刊出日期: 2013-07-20

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

1.
Tsinghua National Laboratory for Information Science and Technology (TNLIST) and Department of Automation, Tsinghua University, Beijing 100084;
2.
National Computer Network Emergency Response Technical Team Coordination Center of China (CNCERT or CNCERT/CC), Beijing 100029

Funds:

Supported by National Basic Research Program of China (973 Program) (2010CB731800) and National Natural Science Foundation of China (61035002, 61171119)

摘要

摘要: 综述了压缩传感、矩阵秩最小化和低秩矩阵恢复等方面的基础理论及典型应用. 基于凸优化的压缩传感及由其衍生的矩阵秩最小化和低秩矩阵恢复是近年来的研究热点,在信号处理、推荐系统、高维数据分析、图像处理、计算机视觉等很多研究领域具有重要和成功的应用. 在这些实际的应用中,往往涉及到对高维数据的分析与处理,需要充分和合理利用数据中的如稀疏性或其所构成矩阵的低秩性等性质. 尽管在最坏情况下,最小化诸如稀疏性或矩阵秩这样的目标函数是 NP 难的,但是在某些合理的假设条件下,通过优化目标函数的凸松弛替代函数, 采用凸优化的方法,能够精确地给出原问题的最优解. 有很多高效的凸优化算法对之进行求解且适用于大规模问题.本文首先分别综述了压缩传感、矩阵秩最小化和低秩矩阵恢复的相关基础理论,然后对其在图像处理、计算机视觉和计算摄像学等领域的典型应用予以举例介绍,并展望了相关领域未来的研究工作.
- 压缩传感 /
- 矩阵秩最小化 /
- 低秩矩阵恢复 /
- 凸优化
Abstract: 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.
- Compressed sensing /
- matrix rank minimization /
- low-rank matrix recovery /
- convex optimization

HTML全文

参考文献(82)

[1]	Natarajan B K. Sparse approximate solutions to linear systems. SIAM Journal of Computing, 1995, 24(2): 227-234
[2]	Recht B, Fazel M, Parrilo P A. Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM Review, 2010, 52(3): 471-501
[3]	Donoho D L. High-dimensional data analysis: the curses and blessings of dimensionality. American Mathematical Society Math Challenges Lecture, 2000. 1-32
[4]	Candès E J, Romberg J, Tao T. Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Transactions on Information Theory, 2006, 52(2): 489-509
[5]	Candès E J, Tao T. Decoding by linear programming. IEEE Transactions on Information Theory, 2004, 51(12): 4203- 4215
[6]	Special section compressive sampling. IEEE Signal Processing Magazine, 2008, 25(2): 12-101
[7]	Li Shu-Tao, Wei Dan. A survey on compressive sensing. Acta Automatica Sinica, 2009, 35(11): 1369-1377 (李树涛, 魏丹. 压缩传感综述. 自动化学报, 2009, 35(11): 1369- 1377)
[8]	Yang J Y, Peng Y G, Xu W L, Dai Q H. Ways to sparse representation: an overview. Science in China Series F: Information Sciences, 2009, 52(4): 695-703
[9]	Elad M. Sparse and Redundant Representations: from Theory to Applications in Signal and Image Processing. New York: Springer, 2010
[10]	Dai Qiong-Hai, Fu Chang-Jun, Ji Xiang-Yang. Research on compressed sensing. Chinese Journal of Computers, 2011, 34(3): 425-434 (戴琼海, 付长军, 季向阳. 压缩感知研究. 计算机学报, 2011, 34(3): 425-434)
[11]	Eldar Y C, Kutyniok G. Compressed Sensing: Theory and Applications. Cambridge: Cambridge University Press, 2012
[12]	Ma Jian-Wei, Xu Jie, Bao Yue-Quan, Yu Si-Wei. Compressive sensing and its application: from sparse to low-rank regularized optimization. Signal Processing, 2012, 28(5): 609- 623 (马坚伟, 徐杰, 鲍跃全, 于四伟. 压缩感知及其应用: 从稀疏约束到低秩约束优化. 信号处理, 2012, 28(5): 609-623)
[13]	Donoho D L. Compressed sensing. IEEE Transactions on Information Theory, 2006, 52(4): 1289-1306
[14]	Taubman D S, Marcellin M W. JPEG 2000: Image Compression Fundamentals, Standards and Practice. The International Series in Engineering and Computer Science. New Yoik: Springer, 2002
[15]	Candès E J, Tao T. The power of convex relaxation: near-optimal matrix completion. IEEE Transactions on Information Theory, 2009, 56(5): 2053-2080
[16]	Candès E J, Li X D, Ma Y, Wright J. Robust principal component analysis? Journal of the ACM, 2011, 58(3): 1-37
[17]	Chandrasekaran V, Sanghavi S, Parrilo P A, Willsky A S. Rank-sparsity incoherence for matrix decomposition. SIAM Journal on Optimization, 2011, 21(2): 572-596
[18]	Valiant L G. Graph-theoretic arguments in low-level complexity. In: Proceedings of the 6th Symposium on Mathematical Foundations of Computer Science. New York: Springer, 1977. 162-176
[19]	Chen Min-Ming. Algorithms and Implementation of Matrix Reconstruction [Master dissertation], Institute of Computing Technology of Chinese Academy of Science, China, 2010 (陈敏铭. 矩阵重建的算法与实现 [硕士学位论文], 中国科学院计算机技术研究所, 中国, 2010)
[20]	Zhou Z H, Li X D, Wright J, Candès E J, Ma Y. Stable principal component pursuit. In: Proceedings of the 2010 IEEE International Symposium on Information Theory. Austin, TX: IEEE, 2010. 1518-1522
[21]	Ganesh A, Wright J, Li X D, Candès E J, Ma Y. Dense error correction for low-rank matrices via principal component pursuit. In: Proceedings of the 2010 IEEE International Symposium on Information Theory. Austin, TX: IEEE, 2010. 1513-1517
[22]	Combettes P L, Wajs V R. Signal recovery by proximal forward-backward splitting. SIAM Multiscale Modeling and Simulation, 2005, 4(4): 1168-1200
[23]	Cai J F, Candès E J, Shen Z W. A singular value thresholding algorithm for matrix completion. SIAM Journal on Optimization, 2010, 20(4): 1956-1982
[24]	Beck A, Teboulle M. A fast iterative shrinkage-thresholding algorithm for linear inverse problem. SIAM Journal on Imaging Sciences, 2008, 2(1) 183-202
[25]	Toh K C, Yun S. An accelerated proximal gradient algorithm for nuclear norm regularized least squares problems. Pacific Journal of Optimization, 2010, 6(3): 615-640
[26]	Lin Z C, Chen M M, Wu L Q, Ma Y. The Augmented Lagrange Multiplier Method for Exact Recovery of Corrupted Low-rank Matrices. UIUC Technical Report UILU-ENG-09-2215, arXiv preprint arXiv: 1009.5055, 2010
[27]	Yang A, Ganesh A, Sastry S, Ma Y. Fast l_1-minimization algorithms and an application in robust face recognition: a review. In: Proceedings of the 2010 IEEE International Conference on Image Processing, 2010. 1849-1852
[28]	Yin W, Osher S, Goldfarb D, Darbon J. Bregman iterative algorithms for l_1-minimization with applications to compressed sensing. SIAM Journal on Imaging Sciences, 2008, 1(1): 143-168
[29]	Rockafellar R T. Convex Analysis. Princeton: Princeton University Press, 1970
[30]	Daubechies I, Defrise M, de Mol C. An iterative thresholding algorithm for linear inverse problems with a sparsity constraint. Communications in Pure and Applied Mathematics, 2004, 57(11): 1413-1457
[31]	Daubechies I, DeVore R, Fornasier M, Güntürk S. Iteratively reweighted least squares minimization for sparse recovery. Communications on Pure and Applied Mathematics, 2010, 63(1): 1-38
[32]	Fornasier M, Rauhut H, Ward R. Low-rank matrix recovery via iteratively reweighted least squares minimization. SIAM Journal on Optimization, 2011, 21(4): 1614-1640
[33]	He R, Sun Z N, Tan T N, Zheng W S. Recovery of corrupted low-rank matrices via half-quadratic based nonconvex minimization. In: Proceedings of the 2011 IEEE International Conference on Computer Vision and Pattern Recognition. Providence, RI: IEEE, 2011. 2889-2896
[34]	Lustig M, Donoho D, Pauly J M. Sparse MRI: the application of compressed sensing for rapid MR imaging. Magnetic Resonance in Medicine, 2007, 58(6): 1182-1195
[35]	Lustig M, Donoho D L, Santos J M, Pauly J M. Compressed sensing MRI. IEEE Signal Processing Magazine, 2008, 25(2): 72-82
[36]	Duarte M F, Davenport M A, Takhar D, Laska J N, Sun T, Kelly K F, Baraniuk R G. Single-pixel imaging via compressive sampling. IEEE Signal Processing Magazine, 2008, 25(2): 83-91
[37]	Studer V, Bobin J, Chahid M, Mousavi S H S, Candès E, Dahan M. Compressive fluorescence microscopy for biological and hyperspectral imaging. Proceedings of the National Academy of Sciences of the United States of America, 2011, 109(26): E1679-E1687
[38]	Wright J, Yang A Y, Ganesh A, Sastry S S, Ma Y. Robust face recognition via sparse representation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2009, 31(2): 210-227
[39]	Wagner A, Wright J, Ganesh A, Zhou Z H, Ma Y. Towards a practical face recognition system: robust registration and illumination by sparse representation. In: Proceedings of the 2009 IEEE International Conference on Computer Vision and Pattern Recognition. Miami, FL: IEEE, 2009. 597-604
[40]	Wagner A, Wright J, Ganesh A, Zhou Z, Mobahi H, Ma Y. Toward a practical face recognition system: robust alignment and illumination by sparse representation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2012, 34(2): 372-386
[41]	Zhou Z, Wagner A, Mobahi H, Wright J, Ma Y. Face recognition with contiguous occlusion using Markov random fields. In: Proceedings of the 12th IEEE International Conference on Computer Vision. Kyoto: IEEE, 2009. 1050-1057
[42]	Kroeker K L. Face recognition breakthrough. ACM Communication, 2009, 52(8): 18-19
[43]	Yang M, Zhang L. Gabor feature based sparse representation for face recognition with gabor occlusion dictionary. In: Proceedings of the 11th European Conference on Computer Vision. Berlin, Heidelberg: Springer-Verlag, 2010. 448-461
[44]	Ma L, Wang C C, Xiao B H, Zhou W. Sparse representation for face recognition based on discriminative low-rank dictionary learning. In: Proceedings of the 2012 IEEE Conference on Computer Vision and Pattern Recognition. Providence, RI: IEEE, 2012. 2586-2593
[45]	Chen C F, Wei C P, Wang Y C F. Low-rank matrix recovery with structural incoherence for robust face recognition. In: Proceedings of the 2012 IEEE Conference on Computer Vision and Pattern Recognition. Providence, RI: IEEE, 2012. 2618-2625
[46]	Yang J C, Wright J, Huang T S, Ma Y. Image super-resolution as sparse representation of raw image patches. In: Proceedings of the 2008 IEEE Conference on Computer Vision and Pattern Recognition. Anchorage, AK: IEEE, 2008. 1-8
[47]	Yang J C, Wright J, Huang T S, Ma Y. Image super-resolution via sparse representation. IEEE Transactions on Image Processing, 2010, 19(11): 2861-2873
[48]	Veeraraghavan A, Reddy D, Raskar R. Coded strobing photography: compressive sensing of high speed periodic events. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011, 33(4): 671-686
[49]	Debevec P, Hawkins T, Tchou C, Duiker H P, Sarokin W, Sagar M. Acquiring the reflectance field of a human face. In: Proceedings of the 27th annual conference on Computer graphics and interactive techniques. New York, USA: ACM, 2000. 146-156
[50]	Peers P, Mahajan D K, Lamond B, Ghosh A, Matusik W, Ramamoorthi R, Debevec P. Compressive light transport sensing. ACM Transactions on Graphics, 2009, 28(1): 1-18
[51]	Wang J P, Dong Y, Tong X, Lin Z C, Guo B N. Kernel Nyström method for light transport. Proceedings of ACM SIGGRAPH, 2009, 28(3): 1-10
[52]	Huang F C, Ramamoorthi R. Sparsely precomputing the light transport matrix for real-time rendering. Computer Graphics Forum, 2010, 29(4): 1335-1345
[53]	Ji H, Liu C Q, Shen Z W, Xu Y H. Robust video denoising using low rank matrix completion. In: Proceedings of the 2010 IEEE International Conference on Computer Vision and Pattern Recognition. San Francisco, CA: IEEE, 2010. 1791-1798
[54]	Ji H, Huang S B, Shen Z W, Xu Y H. Robust video restoration by joint sparse and low rank matrix approximation. SIAM Journal on Imaging Sciences, 2011, 4(4): 1122-1142
[55]	Karbasi A, Oh S, Parhizkar R, Vetterli M. Ultrasound tomography calibration using structured matrix completion. In: Proceedings of the 20th International Congress on Acoustics. Sydney, Australia, 2010
[56]	Parhizkar R, Karbasi A, Vetterli M. Calibration in circular ultrasound tomography devices. In: Proceedings of the 36th International Conference on Acoustics, Speech and Signal Processing. Prague: IEEE, 2011. 549-552
[57]	Keshavan R H, Montanari A, Oh S. Matrix completion from a few entries. IEEE Transactions on Information Theory, 2010, 56(6): 2980-2998
[58]	Wu L, Ganesh A, Shi B, Matsushita Y, Wang Y T, Ma Y. Robust photometric stereo via low-rank matrix completion and recovery. In: Proceedings of the 10th Asian Conference on Computer Vision. Berlin, Heidelberg: Springer-Verlag, 2010. 703-717
[59]	Peng Y G, Ganesh A, Wright J, Xu W L, Ma Y. RASL: robust alignment by sparse and low-rank decomposition for linearly correlated images. In: Proceedings of the 2010 IEEE International Conference on Computer Vision and Pattern Recognition (CVPR). San Francisco, CA: IEEE, 2010. 763-770
[60]	Peng Y G, Ganesh A, Wright J, Xu W L, Ma Y. RASL: robust alignment by sparse and low-rank decomposition for linearly correlated images. IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), 2012, 34(11). 2233-2246
[61]	Wu K K, Wang L J, Soong F K, Yam Y. A sparse and low-rank approach to efficient face alignment for photo-real talking head synthesis. In: Proceedings of the 2011 IEEE International Conference on Acoustics, Speech and Signal Processing. Prague: IEEE, 2011. 1397-1400
[62]	Tan W T, Cheung G, Ma Y. Face recovery in conference video streaming using robust principal component analysis. In: Proceedings of the 18th IEEE International Conference on Image Processing. Brussels, Belgium: IEEE, 2011. 3225- 3228
[63]	Zhang Z D, Liang X, Ganesh A, Ma Y. TILT: transform invariant low-rank textures. In: Proceedings of the 2011 Computer Vision -- ACCV, Springer Berlin Heidelberg, 2011. 314 -328
[64]	Zhang Z D, Ganesh A, Liang X, Ma Y. TILT: transform invariant low-rank textures. International Journal of Computer Vision, 99(1): 1-24
[65]	Zhang Z D, Liang X, Ma Y. Unwrapping low-rank textures on generalized cylindrical surfaces. In: Proceedings of the 2011 International Conference on Computer Vision (ICCV). Barcelona, Spain: IEEE, 2011. 1347-1354
[66]	Mobahi H, Zhou Z H, Yang A Y, Ma Y. Holistic 3D reconstruction of urban structures from low-rank textures. In: Proceedings of the 2011 International Conference on Computer Vision Workshops. Barcelona: IEEE, 2011. 593-600
[67]	Zhang Z D, Matsushita Y, Ma Y. Camera calibration with lens distortion from low-rank textures. In: Proceedings of the 2011 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). Providence, RI: IEEE, 2011. 2321- 2328
[68]	Zhang X, Lin Z, Sun F, Ma Y. Rectification of Optical Characters as Transform Invariant Low-rank Textures. International Conference on Document Analysis and Recognition (ICDAR), 2013
[69]	Ren J, Vlachos T. Detection of dirt impairments from archived film sequences: survey and evaluations. SPIE Journal of Optical Engineering, 2010, 49(6): 067005
[70]	Garg K, Nayar S K. Detection and removal of rain from videos. In: Proceedings of the 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR). Washington, DC, USA: IEEE, 2004. I-528-I-535
[71]	Angst R, Zach C, Pollefeys M. The generalized trace-norm and its application to structure-from-motion problems. In: Proceedings of the 2011 IEEE International Conference on Computer Vision. Barcelona, Spain: IEEE, 2011. 1-8
[72]	Baraniuk R G, Cevher V, Duarte M F, Hegde C. Model-based compressive sensing. IEEE Transactions on Information Theory, 2010, 56(4): 1982-2001
[73]	Eldar Y C, Mishali M. Robust recovery of signals from a structured union of subspaces. IEEE Transactions on Information Theory, 2009, 55(11): 5302-5316
[74]	Bach F. Structured sparsity-inducing norms through submodular functions. In: Proceedings of the 2010 in Advances in Neural Information Processing Systems, 2010. 118-126
[75]	Mackey L W, Talwalkar A, Jordan M I. Divide-and-conquer matrix factorization. In: Proceedings of the 2011 Neural Information Processing Systems, 2011. 1134-1142
[76]	Drineas P, Kannan R, Mahoney M W. Fast Monte Carlo algorithms for matrices II: computing a low-rank approximation to a matrix. SIAM Journal on Optimization, 2006, 36(1): 158-183
[77]	Zhou T Y, Tao D. GoDec: randomized low-rank and sparse matrix decomposition in noisy case. In: Proceedings of the 2011 International Conference on Machine Learning, 2011. 33-40
[78]	Zhuang L S, Gao H Y, Lin Z C, Ma Y, Zhang X, Yu N H. Non-negative low rank and sparse graph for semi-supervised learning. In: Proceedings of the 2012 Conference on Computer Vision and Pattern Recognition. Providence, RI: IEEE, 2012. 2328-2335
[79]	Jhuo I, Liu D, Lee D T, Chang S F. Robust visual domain adaptation with low-rank reconstruction. In: Proceedings of the 2012 Computer Vision and Pattern Recognition, 2012. 2168-2175
[80]	Shen X, Wu Y. A unified approach to salient object detection via low rank matrix recovery. In: Proceedings of the 2012 Computer Vision and Pattern Recognition, 2012. 853-860
[81]	Ye G N, Liu D, Jhuo I H, Chang S F. Robust late fusion with rank minimization. In: Proceedings of the 2012 Conference on Computer Vision and Pattern Recognition. Providence, RI: IEEE, 2012. 3021-3028
[82]	Zhou X W, Yang C, Yu W C. Automatic mitral leaflet tracking in echocardiography by outlier detection in the low-rank representation. In: Proceedings of the 2012 Conference on Computer Vision and Pattern Recognition. Providence, RI: IEEE, 2012. 972-979