Change search
ReferencesLink to record
Permanent link

Direct link
Recovery of Low-Rank Matrices Under Affine Constraints via a Smoothed Rank Function
KTH, School of Electrical Engineering (EES), Automatic Control.
2014 (English)In: IEEE Transactions on Signal Processing, ISSN 1053-587X, E-ISSN 1941-0476, Vol. 62, no 4, 981-992 p.Article in journal (Refereed) Published
Abstract [en]

In this paper, the problem of matrix rank minimization under affine constraints is addressed. The state-of-the-art algorithms can recover matrices with a rank much less than what is sufficient for the uniqueness of the solution of this optimization problem. We propose an algorithm based on a smooth approximation of the rank function, which practically improves recovery limits on the rank of the solution. This approximation leads to a non-convex program; thus, to avoid getting trapped in local solutions, we use the following scheme. Initially, a rough approximation of the rank function subject to the affine constraints is optimized. As the algorithm proceeds, finer approximations of the rank are optimized and the solver is initialized with the solution of the previous approximation until reaching the desired accuracy. On the theoretical side, benefiting from the spherical section property, we will show that the sequence of the solutions of the approximating programs converges to the minimum rank solution. On the experimental side, it will be shown that the proposed algorithm, termed SRF standing for smoothed rank function, can recover matrices, which are unique solutions of the rank minimization problem and yet not recoverable by nuclear norm minimization. Furthermore, it will be demonstrated that, in completing partially observed matrices, the accuracy of SRF is considerably and consistently better than some famous algorithms when the number of revealed entries is close to the minimum number of parameters that uniquely represent a low-rank matrix.

Place, publisher, year, edition, pages
IEEE Signal Processing Society, 2014. Vol. 62, no 4, 981-992 p.
Keyword [en]
affine rank minimization, compressive sensing, matrix completion, nuclear norm minimization, rank approximation, spherical section property
National Category
Signal Processing
URN: urn:nbn:se:kth:diva-164058DOI: 10.1109/TSP.2013.2295557ISI: 000332033600016OAI: diva2:802841

QC 20150413

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

Open Access in DiVA

No full text

Other links

Publisher's full textIEEEXplore
By organisation
Automatic Control
In the same journal
IEEE Transactions on Signal Processing
Signal Processing

Search outside of DiVA

GoogleGoogle Scholar
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: 21 hits
ReferencesLink to record
Permanent link

Direct link