# Article

Full entry | PDF   (1.7 MB)
Keywords:
robust principal component analysis; sparse Bayesian learning; Markov random fields; matrix factorization; contiguity prior
Summary:
The research on the robust principal component analysis has been attracting much attention recently. Generally, the model assumes sparse noise and characterizes the error term by the $\ell _1$-norm. However, the sparse noise has clustering effect in practice so using a certain $\ell _p$-norm simply is not appropriate for modeling. In this paper, we propose a novel method based on sparse Bayesian learning principles and Markov random fields. The method is proved to be very effective for low-rank matrix recovery and contiguous outliers detection, by enforcing the low-rank constraint in a matrix factorization formulation and incorporating the contiguity prior as a sparsity constraint. The experiments on both synthetic data and some practical computer vision applications show that the novel method proposed in this paper is competitive when compared with other state-of-the-art methods.
References:
[1] Babacan, S. D., Luessi, M., Molina, R., Katsaggelos, A. K.: Sparse Bayesian methods for low-rank matrix estimation. IEEE Trans. Signal Process. 60 (2012), 3964-3977. DOI 10.1109/TSP.2012.2197748 | MR 2960472
[2] Bishop, C. M.: Pattern Recognition and Machine Learning. Information Science and Statistics Springer, New York (2006). MR 2247587 | Zbl 1107.68072
[3] Boykov, Y., Veksler, O., Zabih, R.: Fast approximate energy minimization via graph cuts. IEEE Trans. Pattern Anal. Mach. Intell. 23 (2010), 1222-1239. DOI 10.1109/34.969114
[4] Candès, E. J., Li, X., Ma, Y., Wright, J.: Robust principal component analysis? J. ACM 58 (2011), Article No. 11, 37 pages. DOI 10.1145/1970392.1970395 | MR 2811000
[5] Candès, E. J., Recht, B.: Exact matrix completion via convex optimization. Found. Comput. Math. 9 (2009), 717-772. DOI 10.1007/s10208-009-9045-5 | MR 2565240 | Zbl 1219.90124
[6] Candès, E. J., Tao, T.: The power of convex relaxation: near-optimal matrix completion. IEEE Trans. Inf. Theory 56 (2010), 2053-2080. DOI 10.1109/TIT.2010.2044061 | MR 2723472 | Zbl 1366.15021
[7] Torre, F. De la, Black, M. J.: A framework for robust subspace learning. Int. J. Comput. Vis. 54 (2003), 117-142. DOI 10.1023/A:1023709501986 | Zbl 1076.68058
[8] Ding, X., He, L., Carin, L.: Bayesian robust principal component analysis. IEEE Trans. Image Process. 20 (2011), 3419-3430. DOI 10.1109/TIP.2011.2156801 | MR 2867882
[9] Ding, C., Zhou, D., He, X., Zha, H.: $R_1$-PCA: rotational invariant $L_1$-norm principal component analysis for robust subspace factorization. Proc. 23rd Int. Conf. on Machine Learning. Pittsburgh ACM, New York (2006), 281-288.
[10] Hansen, P. C.: Rank-Deficient and Discrete Ill-Posed Problems. Numerical Aspects of Linear Inversion. SIAM Monographs on Mathematical Modeling and Computation 4 Society for Industrial and Applied Mathematics, Philadelphia (1998). MR 1486577
[11] Jolliffe, I. T.: Principal Component Analysis. Springer Series in Statistics Springer, New York (2002). MR 2036084 | Zbl 1011.62064
[12] Kolmogorov, V., Zabin, R.: What energy functions can be minimized via graph cuts? IEEE Trans. Pattern Anal. Mach. Intell. 26 (2004), 147-159. DOI 10.1109/TPAMI.2004.1262177
[13] Kwak, N.: Principal component analysis based on L1-norm maximization. IEEE Trans. Pattern Anal. Mach. Intell. 30 (2008), 1672-1680. DOI 10.1109/TPAMI.2008.114
[14] Li, S. Z.: Markov Random Field Modeling in Image Analysis. Advances in Pattern Recognition Springer, London (2009). MR 2493908 | Zbl 1183.68691
[15] Lin, Z., Chen, M., Ma, Y.: The augmented Lagrange multiplier method for exact recovery of corrupted low-rank matrices. ArXiv preprint arXiv:1009.5055, 2010.
[16] Lin, Z., Ganesh, A., Wright, J., Wu, L., Chen, M., Ma, Y.: Fast convex optimization algorithms for exact recovery of a corrupted low-rank matrix. Computational Advances in Multi-Sensor Adaptive Processing Aruba, Dutch Antilles, Proceedings. IEEE (2009).
[17] Liu, G., Lin, Z., Yu, Y.: Robust subspace segmentation by low-rank representation. Proc. 27th Int. Conf. on Machine Learning, Haifa Proceedings Omni Press. (2010), 663-670.
[18] Mazumder, R., Hastie, T., Tibshirani, R.: Spectral regularization algorithms for learning large incomplete matrices. J. Mach. Learn. Res. 11 (2010), 2287-2322. MR 2719857 | Zbl 1242.68237
[19] Peng, Y., Ganesh, A., Wright, J., Xu, W., Ma, Y.: RASL: Robust alignment by sparse and low-rank decomposition for linearly correlated images. IEEE Trans. Pattern Anal. Mach. Intell. 34 (2012), 2233-2246. DOI 10.1109/TPAMI.2011.282
[20] Recht, B., Fazel, M., Parrilo, P. A.: Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM Rev. 52 (2010), 471-501. DOI 10.1137/070697835 | MR 2680543 | Zbl 1198.90321
[21] Wang, N., Yeung, D. Y.: Bayesian robust matrix factorization for image and video processing. Computer Vision, 2013 IEEE International Conference, Sydney Proceedings. IEEE (2013), 1785-1792.
[22] Wright, J., Ganesh, A., Rao, S., Peng, Y., Ma, Y.: Robust principal component analysis: Exact recovery of corrupted low-rank matrices via convex optimization. Advances in Neural Information Processing Systems 22, Vancouver Proceedings. Curran Associates (2009), 2080-2088.
[23] Xu, H., Caramanis, C., Sanghavi, S.: Robust PCA via outlier pursuit. IEEE Trans. Inform. Theory 58 (2012), 3047-3064. DOI 10.1109/TIT.2011.2173156 | MR 2952532 | Zbl 1365.62228
[24] Zhao, Q., Meng, D., Xu, Z., Zuo, W., Zhang, L.: Robust principal component analysis with complex noise. Proc. 31st Int. Conf. on Machine Learning, Beijing Proceedings. J. Mach. Learn Res. (2014), 55-63.
[25] Zhou, Z., Li, X., Wright, J., Candès, E. J., Ma, Y.: Stable principal component pursuit. 2010 IEEE International Symposium on Information Theory Proceedings, Austin Proceedings. IEEE (2010), 1518-1522.
[26] Zhou, X., Yang, C., Yu, W.: Moving object detection by detecting contiguous outliers in the low-rank representation. IEEE Trans. Pattern Anal. Mach. Intell. 35 (2013), 597-610. DOI 10.1109/TPAMI.2012.132

Partner of