×

Restricted isometry property of principal component pursuit with reduced linear measurements. (English) Zbl 1268.90050

Summary: The principal component pursuit with reduced linear measurements (PCP_RLM) has gained great attention in applications, such as machine learning, video, and aligning multiple images. The recent research shows that strongly convex optimization for compressive principal component pursuit can guarantee the exact low-rank matrix recovery and sparse matrix recovery as well. In this paper, we prove that the operator of PCP_RLM satisfies restricted isometry property (RIP) with high probability. In addition, we derive the bound of parameters depending only on observed quantities based on RIP property, which will guide us how to choose suitable parameters in strongly convex programming.

MSC:

90C25 Convex programming
90C59 Approximation methods and heuristics in mathematical programming
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] J. Ellenberg, “Fill in the blanks: using math to turn lo-res datasets into hi-ressamples,” http://www.wired.com/magazine/2010/02/ff_algorithm/.
[2] A. Chambolle and P.-L. Lions, “Image recovery via total variation minimization and related problems,” Numerische Mathematik, vol. 76, no. 2, pp. 167-188, 1997. · Zbl 0874.68299
[3] J. F. Claerbout and F. Muir, “Robust modeling of erratic data,” Geophysics, vol. 38, pp. 826-844, 1973.
[4] B. Zeng and J. Fu, “Directional discrete cosine transforms-a new framework for image coding,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 18, no. 3, pp. 305-313, 2008. · Zbl 05516048
[5] M. Elad and M. Aharon, “Image denoising via sparse and redundant representations over learned dictionaries,” IEEE Transactions on Image Processing, vol. 15, no. 12, pp. 3736-3745, 2006. · Zbl 05453620
[6] H. Ji, C. Q. Liu, Z. W. Shen, and Y. Xu, “Robust video denoising using Low rank matrix completion,” in Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR ’10), pp. 1791-1798, June 2010.
[7] E. J. Candès and B. Recht, “Exact matrix completion via convex optimization,” Foundations of Computational Mathematics, vol. 9, no. 6, pp. 717-772, 2009. · Zbl 1219.90124
[8] E. J. Candès, X. Li, Y. Ma, and J. Wright, “Robust principal component analysis?” Journal of the ACM, vol. 58, no. 3, article 11, 2011. · Zbl 1327.62369
[9] Z. Zhou, X. Li, J. Wright, E. Candès, and Y. Ma, “Stable principal component pursuit,” in Proceedings of the IEEE International Symposium on Information Theory (ISIT ’10), pp. 1518-1522, June 2010.
[10] A. Ganesh, K. Min, J. Wright, and Y. Ma, “Principal component pursuit with reduced linear measurements,” IEEE International Symposium on Information Theory Proceedings, pp. 1281-1285, 2012.
[11] J. Wright, A. Ganesh, K. Min, and Y. Ma, “Compressive principal component pursuit,” IEEE International Symposium on Information Theory Proceedings, pp. 1276-1280, 2012. · Zbl 1354.94015
[12] H. Zhang, J.-F. Cai, L. Cheng, and J. Zhu, “Strongly convex programming for exact matrix completion and robust principal component analysis,” Inverse Problems and Imaging, vol. 6, no. 2, pp. 357-372, 2012. · Zbl 1252.15042
[13] B. Recht, M. Fazel, and P. A. Parrilo, “Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization,” SIAM Review, vol. 52, no. 3, pp. 471-501, 2010. · Zbl 1198.90321
[14] Q. S. You, Q. Wan, and Y. P. Liu, “A short note on strongly convex programming for exact matrix completion and robust principal component analysis,” Inverse Problems and Imaging, vol. 7, no. 1, pp. 305-306, 2013. · Zbl 1271.15025
[15] Q. S. You and Q. Wan, “Strongly convex programming for principal component pursuit,” http://arxiv.org/abs/1209.4405. · Zbl 1271.15025
[16] R. Meka, P. Jain Inderjit, and S. Dhillon, “Guaranteed rank minimization via singular value projection,” in Neural Information Processing Systems, 2010.
[17] L. Mackey, M. I. Jordan, R. Y. Chen, B. Farrell, and J. A. Tropp, “Matrix concentration inequalities via the method of exchangeable Pairs,” http://arxiv.org/abs/1201.6002. · Zbl 1294.60008
[18] B. Laurent and P. Massart, “Adaptive estimation of a quadratic functional by model selection,” The Annals of Statistics, vol. 28, no. 5, pp. 1302-1338, 2000. · Zbl 1105.62328
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.