1,596
Views
174
CrossRef citations to date
0
Altmetric
Original Articles

Augmented Lagrangian alternating direction method for matrix separation based on low-rank factorization

, &
Pages 239-263 | Received 25 Nov 2011, Accepted 03 Jun 2012, Published online: 13 Jul 2012
 

Abstract

The matrix separation problem aims to separate a low-rank matrix and a sparse matrix from their sum. This problem has recently attracted considerable research attention due to its wide range of potential applications. Nuclear-norm minimization models have been proposed for matrix separation and proved to yield exact separations under suitable conditions. These models, however, typically require the calculation of a full or partial singular value decomposition at every iteration that can become increasingly costly as matrix dimensions and rank grow. To improve scalability, in this paper, we propose and investigate an alternative approach based on solving a non-convex, low-rank factorization model by an augmented Lagrangian alternating direction method. Numerical studies indicate that the effectiveness of the proposed model is limited to problems where the sparse matrix does not dominate the low-rank one in magnitude, though this limitation can be alleviated by certain data pre-processing techniques. On the other hand, extensive numerical results show that, within its applicability range, the proposed method in general has a much faster solution speed than nuclear-norm minimization algorithms and often provides better recoverability.

This article is part of the following collections:
Charles Broyden Prize

Acknowledgements

The work of Yuan Shen was supported by the Chinese Scholarship Council during his visit to Rice University. The work of Zaiwen Wen was supported in part by NSF DMS-0439872 through UCLA IPAM. The work of Yin Zhang was supported in part by NSF Grant DMS-0811188 and ONR Grant N00014-08-1-1101.

Notes

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.