research-article

Robust bilinear factorization with missing and grossly corrupted observations

Authors:

Hong ChengAuthors Info & Claims

Information Sciences—Informatics and Computer Science, Intelligent Systems, Applications: An International Journal, Volume 307, Issue C

Pages 53 - 72

https://doi.org/10.1016/j.ins.2015.02.026

Published: 20 June 2015 Publication History

Abstract

Recovering low-rank and sparse matrices from incomplete or corrupted observations is an important problem in statistics, machine learning, computer vision, as well as signal and image processing. In theory, this problem can be solved by the natural convex joint/mixed relaxations (i.e., l 1 -norm and trace norm) under certain conditions. However, all current provable algorithms suffer from superlinear per-iteration cost, which severely limits their applicability to large-scale problems. In this paper, we propose a scalable, provable and structured robust bilinear factorization (RBF) method to recover low-rank and sparse matrices from missing and grossly corrupted data, i.e., robust matrix completion (RMC), or incomplete and grossly corrupted measurements, i.e., compressive principal component pursuit (CPCP). Specifically, we first present two small-scale matrix trace norm regularized bilinear factorization models for RMC and CPCP problems, in which repetitively calculating SVD of a large-scale matrix is replaced by updating two much smaller factor matrices. Then, we apply the alternating direction method of multipliers (ADMM) to efficiently solve the RMC problems. Finally, we provide the convergence analysis of our algorithm, and extend it to address general CPCP problems. Experimental results verified both the efficiency and effectiveness of our method compared with the state-of-the-art methods.

References

[1]

A. Agarwal, S. Negahban, M. Wainwright, Noisy matrix decomposition via convex relaxation: optimal rates in high dimensions, Ann. Stat., 40 (2012) 1171-1197.

[2]

H. Avron, S. Kale, S. Kasiviswanathan, V. Sindhwani, Efficient and practical stochastic subgradient descent for nuclear norm regularization, in: ICML, 2012.

[3]

N. Boumal, P.A. Absil, RTRMC: a Riemannian trust-region method for low-rank matrix completion, in: NIPS, 2011, pp. 406-414.

Digital Library

[4]

S. Boyd, N. Parikh, E. Chu, B. Peleato, J. Eckstein, Distributed optimization and statistical learning via the alternating direction method of multipliers, Found. Trends Mach. Learn., 3 (2011) 1-122.

Digital Library

[5]

S. Burer, R. Monteiro, Local minima and convergence in low-rank semidefinite programming, Math. Program., 103 (2005) 427-444.

Digital Library

[6]

R. Cabral, F. Torre, J. Costeira, A. Bernardino, Unifying nuclear norm and bilinear factorization approaches for low-rank matrix decomposition, in: ICCV, 2013, pp. 2488-2495.

[7]

J. Cai, E. Candès, Z. Shen, A singular value thresholding algorithm for matrix completion, SIAM J. Optim., 20 (2010) 1956-1982.

Digital Library

[8]

E. Candès, X. Li, Y. Ma, J. Wright, Robust principal component analysis?, J. ACM, 58 (2011) 1-37.

Digital Library

[9]

E. Candès, B. Recht, Exact matrix completion via convex optimization, Found. Comput. Math., 9 (2009) 717-772.

Digital Library

[10]

Y. Chen, A. Jalali, S. Sanghavi, C. Caramanis, Low-rank matrix recovery from errors and erasures, IEEE Trans. Inform. Theory, 59 (2013) 4324-4337.

Digital Library

[11]

A. Eriksson, A. van den Hengel, Efficient computation of robust low-rank matrix approximations in the presence of missing data using the l1 norm, in: CVPR, 2010, pp. 771-778.

[12]

P. Favaro, R. Vidal, A. Ravichandran, A closed form solution to robust subspace estimation and clustering, in: CVPR, 2011, pp. 1801-1807.

[13]

M. Fazel, Matrix Rank Minimization with Applications, PhD Thesis, Stanford University, 2002.

[14]

Y. Feng, J. Xiao, Y. Zhuang, X. Yang, J. Zhang, R. Song, Exploiting temporal stability and low-rank structure for motion capture data refinement, Inform. Sci., 277 (2014) 777-793.

[15]

J. He, L. Balzano, A. Szlam, Incremental gradient on the Grassmannian for online foreground and background separation in subsampled video, in: CVPR, 2012, pp. 1568-1575.

[16]

R. Keshavan, A. Montanari, S. Oh, Matrix completion from a few entries, IEEE Trans. Inform. Theory, 56 (2010) 2980-2998.

Digital Library

[17]

K. Lee, J. Ho, D. Kriegman, Acquiring linear subspaces for face recognition under variable lighting, IEEE Trans. Pattern Anal. Mach. Intell., 27 (2005) 684-698.

Digital Library

[18]

S. Lee, Y. Cho, S. Kim, Collaborative filtering with ordinal scale-based implicit ratings for mobile music recommendations, Inform. Sci., 180 (2010) 2142-2155.

Digital Library

[19]

X. Li, Compressed sensing and matrix completion with constant proportion of corruptions, Constr. Approx., 37 (2013) 73-99.

[20]

Z. Li, J. Liu, Y. Jiang, J. Tang, H. Lu, Low rank metric learning for social image retrieval, in: ACM Multimedia, 2012, pp. 853-856.

[21]

Z. Li, J. Liu, X. Zhu, T. Liu, H. Lu, Image annotation using multi-correlation probabilistic matrix factorization, in: ACM Multimedia, 2010, pp. 1187-1190.

[22]

Z. Lin, M. Chen, L. Wu, The Augmented Lagrange Multiplier Method for Exact Recovery of Corrupted Low-rank Matrices, Univ. Illinois, Urbana-Champaign, 2009.

[23]

D.R. Liu, C.H. Lai, W.J. Lee, A hybrid of sequential rules and collaborative filtering for product recommendation, Inform. Sci., 179 (2009) 3505-3519.

Digital Library

[24]

G. Liu, Z. Lin, S. Yan, J. Sun, Y. Yu, Y. Ma, Robust recovery of subspace structures by low-rank representation, IEEE Trans. Pattern Anal. Mach. Intell., 35 (2013) 171-184.

Digital Library

[25]

G. Liu, S. Yan, Active subspace: toward scalable low-rank learning, Neural Comput., 24 (2012) 3371-3394.

Digital Library

[26]

Y. Liu, L. Jiao, F. Shang, F. Yin, F. Liu, An efficient matrix bi-factorization alternative optimization method for low-rank matrix recovery and completion, Neural Netwoks, 48 (2013) 8-18.

Digital Library

[27]

Y. Liu, F. Shang, H. Cheng, J. Cheng, A Grassmannian manifold algorithm for nuclear norm regularized least squares problems, in: UAI, 2014.

[28]

R. Ma, N. Barzigar, A. Roozgard, S. Cheng, Decomposition approach for low-rank matrix completion and its applications, IEEE Trans. Signal Proc., 62 (2014) 1671-1683.

Digital Library

[29]

S. Ma, D. Goldfarb, L. Chen, Fixed point and Bregman iterative methods for matrix rank minimization, Math. Prog., 128 (2011) 321-353.

Digital Library

[30]

R. Mazumder, T. Hastie, R. Tibshirani, Spectral regularization algorithms for learning large incomplete matrices, J. Mach. Learn. Res., 11 (2010) 2287-2322.

Digital Library

[31]

D. Meng, Z. Xu, L. Zhang, J. Zhao, A cyclic weighted median method for L1 low-rank matrix factorization with missing entries, in: AAAI, 2013, pp. 704-710.

[32]

K. Min, Z. Zhang, J. Wright, Y. Ma, Decomposition background topics from keywords by principal component pursuit, in: CIKM, 2010, pp. 269-278.

[33]

T. Ngo, Y. Saad, Scaled gradients on Grassmann manifolds for matrix completion, in: NIPS, 2012, pp. 1421-1429.

[34]

H. Nick, Matrix Procrustes Problems, University of Manchester, 1995.

[35]

R. Otazo, E. Candes, D. Sodickson, Low-rank and sparse matrix decomposition for accelerated dynamic MRI with separation of background and dynamic components, Magn. Reson. Med., 73 (2015) 1125-1136.

[36]

Y. Peng, A. Ganesh, J. Wright, W. Xu, Y. Ma, RASL: robust alignment by sparse and low-rank decomposition for linearly correlated images, IEEE Trans. Pattern Anal. Mach. Intell., 34 (2012) 2233-2246.

Digital Library

[37]

F. Shang, L. Jiao, F. Wang, Graph dual regularization non-negative matrix factorization for co-clustering, Pattern Recogn., 45 (2012) 2237-2250.

Digital Library

[38]

F. Shang, L. Jiao, F. Wang, Semi-supervised learning with mixed knowledge information, in: KDD, 2012b, pp. 732-740.

[39]

F. Shang, Y. Liu, H. Cheng, J. Cheng, Recovering low-rank and sparse matrices via robust bilateral factorization, in: ICDM, 2014a, pp. 965-970.

[40]

F. Shang, Y. Liu, J. Cheng, Generalized higher-order tensor decomposition via parallel ADMM, in: AAAI, 2014b, pp. 1279-1285.

[41]

F. Shang, Y. Liu, J. Cheng, H. Cheng, Robust principal component analysis with missing data, in: CIKM, 2014c, pp. 1149-1158.

[42]

Y. Shen, Z. Wen, Y. Zhang, Augmented Lagrangian alternating direction method for matrix separation based on low-rank factorization, Optim. Method Softw., 29 (2014) 239-263.

Digital Library

[43]

M. Tao, X. Yuan, Recovering low-rank and sparse components of matrices from incomplete and noisy observations, SIAM J. Optim., 21 (2011) 57-81.

Digital Library

[44]

K.C. Toh, S. Yun, An accelerated proximal gradient algorithm for nuclear norm regularized least squares problems, Pac. J. Optim., 6 (2010) 615-640.

[45]

R. Tomioka, T. Suzuki, Convex tensor decomposition via structured Schatten norm regularization, in: NIPS, 2013, pp. 1331-1339.

[46]

M. Wang, R. Hong, G. Li, Z.J. Zha, S. Yan, T.S. Chua, Event driven web video summarization by tag localization and key-shot identification, IEEE Trans. Multimedia, 14 (2012) 975-985.

Digital Library

[47]

M. Wang, B. Ni, X.S. Hua, T.S. Chua, Assistive tagging: a survey of multimedia tagging with human-computer joint exploration, ACM Comput. Surv. (2012) 44.

[48]

A. Waters, A. Sankaranarayanan, R. Baraniuk, SpaRCS: recovering low-rank and sparse matrices from compressive measurements, in: NIPS, 2011, pp. 1089-1097.

[49]

Z. Wen, W. Yin, Y. Zhang, Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm, Math. Prog. Comput., 4 (2012) 333-361.

[50]

J. Wright, A. Ganesh, K. Min, Y. Ma, Compressive principal component pursuit, Inform. Infer., 2 (2013) 32-68.

[51]

J. Wright, A. Ganesh, S. Rao, Y. Peng, Y. Ma, Robust principal component analysis: exact recovery of corrupted low-rank matrices by convex optimization, in: NIPS, 2009, pp. 2080-2088.

[52]

H. Xu, C. Caramanis, S. Sanghavi, Robust PCA via outlier pursuit, in: NIPS, 2010, pp. 2496-2504.

[53]

J. Yang, X. Yuan, Linearized augmented Lagrangian and alternating direction methods for nuclear norm minimization, Math. Comput., 82 (2013) 301-329.

[54]

J. Yu, Y. Rui, D. Tao, Click prediction for web image reranking using multimodal sparse coding, IEEE Trans. Image Process., 23 (2014) 2019-2032.

[55]

J. Yu, D. Tao, M. Wang, Adaptive hypergraph learning and its application in image classification, IEEE Trans. Image Process., 21 (2012) 3262-3272.

Digital Library

[56]

X. Yuan, J. Yang, Sparse and low-rank matrix decomposition via alternating direction methods, Pac. J. Optim., 9 (2013) 167-180.

[57]

Y. Zheng, G. Liu, S. Sugimoto, S. Yan, M. Okutomi, Practical low-rank matrix approximation under robust L1-norm, in: CVPR, 2012, pp. 1410-1417.

[58]

T. Zhou, D. Tao, Greedy bilateral sketch, completion & smoothing, in: AISTATS, 2013, pp. 650-658.

Cited By

Zhang HWen BZha ZZhang BTang YYu GDu W(2023)Accelerated PALM for Nonconvex Low-Rank Matrix Recovery With Theoretical AnalysisIEEE Transactions on Circuits and Systems for Video Technology10.1109/TCSVT.2023.330681134:4(2304-2317)Online publication date: 21-Aug-2023
https://dl.acm.org/doi/10.1109/TCSVT.2023.3306811
Zhang HQian JZhang BYang JGong CWei Y(2020)Low-Rank Matrix Recovery via Modified Schatten- $p$ Norm Minimization With Convergence GuaranteesIEEE Transactions on Image Processing10.1109/TIP.2019.295792529(3132-3142)Online publication date: 28-Jan-2020
https://dl.acm.org/doi/10.1109/TIP.2019.2957925
Tang LGuan W(2019)Robust matrix completion with complex noiseMultimedia Tools and Applications10.1007/s11042-019-08430-279:3-4(2703-2717)Online publication date: 30-Nov-2019
https://dl.acm.org/doi/10.1007/s11042-019-08430-2

Recommendations

Recovering Low-Rank and Sparse Matrices via Robust Bilateral Factorization
ICDM '14: Proceedings of the 2014 IEEE International Conference on Data Mining

Recovering low-rank and sparse matrices from partial, incomplete or corrupted observations is an important problem in many areas of science and engineering. In this paper, we propose a scalable robust bilateral factorization (RBF) method to recover both ...
Robust Lasso with missing and grossly corrupted observations
NIPS'11: Proceedings of the 24th International Conference on Neural Information Processing Systems

This paper studies the problem of accurately recovering a sparse vector β* from highly corrupted linear measurements y = X β* + e* + w where e* is a sparse error vector whose nonzero entries may be unbounded and w is a bounded noise. We propose a so-...
Visual data denoising with a unified Schatten-p norm and ℓq norm regularized principal component pursuit

To address the visual processing problem with corrupted data, in this paper, we propose a non-convex formulation to recover the authentic structure from the corrupted data. Typically, the specific structure is assumed to be low rank, which holds for a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Information Sciences: an International Journal

Information Sciences: an International Journal Volume 307, Issue C

June 2015

127 pages

ISSN:0020-0255

Issue’s Table of Contents

Copyright © Elsevier Inc.

Publisher

Elsevier Science Inc.

United States

Publication History

Published: 20 June 2015

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 23 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhang HWen BZha ZZhang BTang YYu GDu W(2023)Accelerated PALM for Nonconvex Low-Rank Matrix Recovery With Theoretical AnalysisIEEE Transactions on Circuits and Systems for Video Technology10.1109/TCSVT.2023.330681134:4(2304-2317)Online publication date: 21-Aug-2023
https://dl.acm.org/doi/10.1109/TCSVT.2023.3306811
Zhang HQian JZhang BYang JGong CWei Y(2020)Low-Rank Matrix Recovery via Modified Schatten- $p$ Norm Minimization With Convergence GuaranteesIEEE Transactions on Image Processing10.1109/TIP.2019.295792529(3132-3142)Online publication date: 28-Jan-2020
https://dl.acm.org/doi/10.1109/TIP.2019.2957925
Tang LGuan W(2019)Robust matrix completion with complex noiseMultimedia Tools and Applications10.1007/s11042-019-08430-279:3-4(2703-2717)Online publication date: 30-Nov-2019
https://dl.acm.org/doi/10.1007/s11042-019-08430-2
Ma THuang TZhao X(2016)Group-based image decomposition using 3-D cartoon and texture priorsInformation Sciences: an International Journal10.1016/j.ins.2015.08.039328:C(510-527)Online publication date: 20-Jan-2016
https://dl.acm.org/doi/10.1016/j.ins.2015.08.039

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents