Change search
ReferencesLink to record
Permanent link

Direct link
Iterative Concave Rank Approximation for Recovering Low-Rank Matrices
KTH, School of Electrical Engineering (EES), Automatic Control.
Sharif University of Technology, Iran.
KTH, School of Electrical Engineering (EES), Communication Theory.ORCID iD: 0000-0002-7926-5081
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
Abstract [en]

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.
National Category
Signal Processing
URN: urn:nbn:se:kth:diva-164055DOI: 10.1109/TSP.2014.2340820ISI: 000341982900001OAI: diva2:802838
Swedish Research Council, 621-2011-5847

QC 20150417

Available from: 2015-04-13 Created: 2015-04-13 Last updated: 2015-06-16Bibliographically approved

Open Access in DiVA

fulltext(1483 kB)39 downloads
File information
File name FULLTEXT01.pdfFile size 1483 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Other links

Publisher's full textIEEEXplore

Search in DiVA

By author/editor
Malek Mohammadi, MohammarezaSkoglund, Mikael
By organisation
Automatic ControlCommunication Theory
In the same journal
IEEE Transactions on Signal Processing
Signal Processing

Search outside of DiVA

GoogleGoogle Scholar
Total: 39 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 99 hits
ReferencesLink to record
Permanent link

Direct link