A Non-convex Relaxation for Fixed-Rank Approximation

Research output: Chapter in Book/Report/Conference proceedingPaper in conference proceedingpeer-review

Abstract

This paper considers the problem of finding a low rank matrix from observations of linear combinations of its elements. It is well known that if the problem fulfills a restricted isometry property (RIP), convex relaxations using the nuclear norm typically work well and come with theoretical performance guarantees. On the other hand these formulations suffer from a shrinking bias that can severely degrade the solution in the presence of noise. In this theoretical paper we study an alternative non-convex relaxation that in contrast to the nuclear norm does not penalize the leading singular values and thereby avoids this bias. We show that despite its non-convexity the proposed formulation will in many cases have a single stationary point if a RIP holds. Our numerical tests show that our approach typically converges to a better solution than nuclear norm based alternatives even in cases when the RIP does not hold.

Original languageEnglish
Title of host publicationProceedings - 2017 IEEE International Conference on Computer Vision Workshops, ICCVW 2017
PublisherIEEE - Institute of Electrical and Electronics Engineers Inc.
Pages1809-1817
Number of pages9
Volume2018-January
ISBN (Electronic)9781538610343
DOIs
Publication statusPublished - 2018 Jan 19
Event16th IEEE International Conference on Computer Vision Workshops, ICCVW 2017 - Venice, Italy
Duration: 2017 Oct 222017 Oct 29

Conference

Conference16th IEEE International Conference on Computer Vision Workshops, ICCVW 2017
Country/TerritoryItaly
CityVenice
Period2017/10/222017/10/29

Subject classification (UKÄ)

  • Computational Mathematics

Fingerprint

Dive into the research topics of 'A Non-convex Relaxation for Fixed-Rank Approximation'. Together they form a unique fingerprint.

Cite this