Efficient and Guaranteed Rank Minimization by Atomic Decomposition

Details Efficient and Guaranteed Rank Minimization by Atomic Decomposition Efficient and Guaranteed Rank Minimization by Atomic Decomposition

2009-01-13

arxiv.org/abs/0901.1898v2

Mathematics

Numerical Analysis

submitted to ISIT 2009

Scientific paper

Recht, Fazel, and Parrilo provided an analogy between rank minimization and $\ell_0$-norm minimization. Subject to the rank-restricted isometry property, nuclear norm minimization is a guaranteed algorithm for rank minimization. The resulting semidefinite formulation is a convex problem but in practice the algorithms for it do not scale well to large instances. Instead, we explore missing terms in the analogy and propose a new algorithm which is computationally efficient and also has a performance guarantee. The algorithm is based on the atomic decomposition of the matrix variable and extends the idea in the CoSaMP algorithm for $\ell_0$-norm minimization. Combined with the recent fast low rank approximation of matrices based on randomization, the proposed algorithm can efficiently handle large scale rank minimization problems.

Affiliated with

Also associated with

No associations

Rating

Efficient and Guaranteed Rank Minimization by Atomic Decomposition does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Efficient and Guaranteed Rank Minimization by Atomic Decomposition, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient and Guaranteed Rank Minimization by Atomic Decomposition will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-374594