A New Analysis of the Iterative Threshold Algorithm for RPCA by Primal-Dual Method

Ru Ya Fan; Hong Xia Wang; Hui Zhang

doi:10.4028/www.scientific.net/AMR.989-994.2462

Paper Titles

Coupling Sentiment Dictionary and SVM Classification for Text Orientation Analysis
p.2444

Research on the Optimization of the Storage Strategy of HDFS
p.2450

Research on Packet Encryption Algorithm in the Cloud Storage
p.2454

ZFDV: Zoom Financial Data Visualization in the Era of Big Data
p.2457

A New Analysis of the Iterative Threshold Algorithm for RPCA by Primal-Dual Method
p.2462

Robot Path Planning Based on Artificial Fish Swarm Algorithm under a Known Environment
p.2467

A Study of the Keep-Right-Except-to-Pass Traffic Rule on Cellular Automata
p.2470

Probabilistic Model Checking by Model Equivalent Reduction and Abstraction
p.2474

Computing Volumes Surrounded by a Quadric Surface and a Plane with MATLAB
p.2480

HomeAdvanced Materials ResearchAdvanced Materials Research Vols. 989-994A New Analysis of the Iterative Threshold...

A New Analysis of the Iterative Threshold Algorithm for RPCA by Primal-Dual Method

Abstract:

This paper studies the iterative threshold algorithm (ITA) for solving the Robust Principal Component Analysis (RPCA) problems, which is to recover a low-rank matrix with a fraction of its entries being arbitrarily corrupted. By utilizing the primal-dual method, we analyze the ITA in a new way and prove that the ITA is essentially equivalent to gradient method applying to a dual problem. In the original ITA, it is hard to choose the parameters and hence it converges very slowly. Now, based on the new insight, existing techniques of the gradient method can be used to accelerate the ITA. We combine the theoretical derivation with the numerical simulation experiments to give an empirical guidance to set the parameters. As illustration, background modeling problem is solved by the ITA with optimal parameters.

You might also be interested in these eBooks

View Preview

Info:

Periodical:

Advanced Materials Research (Volumes 989-994)

Pages:

2462-2466

DOI:

https://doi.org/10.4028/www.scientific.net/AMR.989-994.2462

Citation:

Cite this paper

Online since:

July 2014

Authors:

Ru Ya Fan*, Hong Xia Wang, Hui Zhang

Keywords:

Background Modeling, Iterative Threshold Algorithm, Low Rank Matrix Recovery, Primal-Dual Method, Robust Principal Component Analysis

Export:

RIS, BibTeX

Price:

Permissions:

Request Permissions

* - Corresponding Author

References

[1] J. Wright, A. Ganesh, S. Rao, Y. Peng, and Y. Ma, Robust principal component analysis: Exact recovery of corrupted low-rank matrices via convex optimization, Proc. of Neural Information Processing Systems, Vol. 3( 2009), p. (2080).

Google Scholar

[2] E. J. Candes, X. Li, Y. Ma, and J. Wright, Robust principal component analysis? Journal of the ACM, Vol. 58(2011)No. 3, p.233.

Google Scholar

[3] V. Chandrasekaran, S. Sanghavi, and P.A. Parrilo, Rank-sparsity incoherence for matrix decomposition, SIAM Journal on Optimization, Vol. 21 (2011)No. 2, p.572.

DOI: 10.1137/090761793

Google Scholar

[4] J. F. Cai, E. J. Candes and Z. W. Shen, A singular value thresholding algorithm for matrix completion, SIAM Journal on Optimization, Vol. 20(2010)No. 4, p. (1956).

DOI: 10.1137/080738970

Google Scholar

[5] A. Beck, M.A. Teboulle, Fast iterative shrinkage-thresholding algorithm for linear inverse problem, SIAM Journal on Imaging Sciences, Vol. 2(2008)No. 1, p.183.

DOI: 10.1137/080716542

Google Scholar

[6] Z. Lin, A. Ganesh, J. Wright, L. Wu, Chen, M, and Y. Ma, Fast convex optimization algorithms for exact recovery of a corrupted low-rank matrix, CAMSAP, 2009, p.61.

DOI: 10.1109/camsap.2009.5413299

Google Scholar

[7] Z. Lin, M. Chen and Y. Ma, The augmented Lagrange multiplier method for exact recovery of corrupted low-rank matrices, Optimization and Control, 2013, http: /arXiv. org: 1009. 5055.

Google Scholar

[8] H. Zhang, L.Z. Cheng, W.T. Yin, A dual algorithm for a class of augmented convex models, submitted to Communication of Mathematic Science, 2014, http: /arXiv: 1308. 6337.

Google Scholar

[9] M.J. Lai, W.T. Yin, Augmented L1 and nuclear-norm models with a globally linearly convergent algorithm, Imaging Sciences, Vol. 6(2013)No. 2, p.1059.

DOI: 10.21236/ada580580

Google Scholar

[10] 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(2013)No. 1, p.305.

DOI: 10.3934/ipi.2013.7.305

Google Scholar

[11] W. Yin, E. Hale,Y. Zhang, Fixed-point continuation for L1-minimization: methodology and convergence, SIAM Journal on Optimization, Vol. 19(2008)No. 3, p.1107.

DOI: 10.1137/070698920

Google Scholar

[12] L. Li, W. Huang, I. Gu, and Q. Tian, Statistical modeling of complex backgrounds for foreground object detection, IEEE Transactions on Image Processing, Vol. 13(2004)No. 11, p.1459.

DOI: 10.1109/tip.2004.836169

Google Scholar