Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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
Identifiers
URN: urn:nbn:se:kth:diva-164055DOI: 10.1109/TSP.2014.2340820ISI: 000341982900001OAI: oai:DiVA.org:kth-164055DiVA: diva2:802838
Funder
Swedish Research Council, 621-2011-5847
Note

QC 20150417

Available from: 2015-04-13 Created: 2015-04-13 Last updated: 2017-12-04Bibliographically approved

Open Access in DiVA

fulltext(1483 kB)82 downloads
File information
File name FULLTEXT01.pdfFile size 1483 kBChecksum SHA-512
2f85db03f3f118bfe12570eacfbb9eeeb02df3abdc34ea51e6d451f5002d269025581e1decd18c2e61980c4b7fed6a5fe239af3d74bbd698bb7f0c6b074c172e
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: 82 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

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 138 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf