Iterative Concave Rank Approximation for Recovering Low-Rank Matrices
2014 (English)In: IEEE Transactions on Signal Processing, ISSN 1053-587X, E-ISSN 1941-0476, Vol. 62, no 60, 5213-5226 p.Article in journal (Refereed) Published
In this paper, we propose a new algorithm for recovery of low-rank matrices from compressed linear measurements. The underlying idea of this algorithm is to closely approximate the rank function with a smooth function of singular values, and then minimize the resulting approximation subject to the linear constraints. The accuracy of the approximation is controlled via a scaling parameter δ, where a smaller δ corresponds to a more accurate fitting. The consequent optimization problem for any finite δ is nonconvex. Therefore, to decrease the risk of ending up in local minima, a series of optimizations is performed, starting with optimizing a rough approximation (a large δ) and followed by successively optimizing finer approximations of the rank with smaller δ's. To solve the optimization problem for any δ > 0, it is converted to a new program in which the cost is a function of two auxiliary positive semidefinite variables. The paper shows that this new program is concave and applies a majorize-minimize technique to solve it which, in turn, leads to a few convex optimization iterations. This optimization scheme is also equivalent to a reweighted Nuclear Norm Minimization (NNM). For any δ > 0, we derive a necessary and sufficient condition for the exact recovery which are weaker than those corresponding to NNM. On the numerical side, the proposed algorithm is compared to NNM and a reweighted NNM in solving affine rank minimization and matrix completion problems showing its considerable and consistent superiority in terms of success rate.
Place, publisher, year, edition, pages
IEEE Signal Processing Society, 2014. Vol. 62, no 60, 5213-5226 p.
IdentifiersURN: urn:nbn:se:kth:diva-164055DOI: 10.1109/TSP.2014.2340820ISI: 000341982900001OAI: oai:DiVA.org:kth-164055DiVA: diva2:802838
FunderSwedish Research Council, 621-2011-5847
QC 201504172015-04-132015-04-132015-06-16Bibliographically approved