A Non-convex Relaxation for Fixed-Rank Approximation

Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceeding

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.

Detaljer

Författare
Enheter & grupper
Externa organisationer
  • Chalmers University of Technology
Forskningsområden

Ämnesklassifikation (UKÄ) – OBLIGATORISK

  • Beräkningsmatematik
Originalspråkengelska
Titel på värdpublikationProceedings - 2017 IEEE International Conference on Computer Vision Workshops, ICCVW 2017
FörlagInstitute of Electrical and Electronics Engineers Inc.
Sidor1809-1817
Antal sidor9
Volym2018-January
ISBN (elektroniskt)9781538610343
StatusPublished - 2018 jan 19
PublikationskategoriForskning
Peer review utfördJa
Evenemang16th IEEE International Conference on Computer Vision Workshops, ICCVW 2017 - Venice, Italien
Varaktighet: 2017 okt 222017 okt 29

Konferens

Konferens16th IEEE International Conference on Computer Vision Workshops, ICCVW 2017
LandItalien
OrtVenice
Period2017/10/222017/10/29