Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

A Non-convex Relaxation for Fixed-Rank Approximation

Olsson, Carl LU ; Carlsson, Marcus LU and Bylow, Erik LU (2018) 16th IEEE International Conference on Computer Vision Workshops, ICCVW 2017 2018-January. p.1809-1817
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... (More)

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.

(Less)
Please use this url to cite or link to this publication:
author
; and
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
host publication
Proceedings - 2017 IEEE International Conference on Computer Vision Workshops, ICCVW 2017
volume
2018-January
pages
9 pages
publisher
IEEE - Institute of Electrical and Electronics Engineers Inc.
conference name
16th IEEE International Conference on Computer Vision Workshops, ICCVW 2017
conference location
Venice, Italy
conference dates
2017-10-22 - 2017-10-29
external identifiers
  • scopus:85046272238
ISBN
9781538610343
DOI
10.1109/ICCVW.2017.214
language
English
LU publication?
yes
id
4743450f-006b-4c43-86b0-f52e38ba18dc
date added to LUP
2018-05-17 15:05:42
date last changed
2022-04-25 07:25:16
@inproceedings{4743450f-006b-4c43-86b0-f52e38ba18dc,
  abstract     = {{<p>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.</p>}},
  author       = {{Olsson, Carl and Carlsson, Marcus and Bylow, Erik}},
  booktitle    = {{Proceedings - 2017 IEEE International Conference on Computer Vision Workshops, ICCVW 2017}},
  isbn         = {{9781538610343}},
  language     = {{eng}},
  month        = {{01}},
  pages        = {{1809--1817}},
  publisher    = {{IEEE - Institute of Electrical and Electronics Engineers Inc.}},
  title        = {{A Non-convex Relaxation for Fixed-Rank Approximation}},
  url          = {{http://dx.doi.org/10.1109/ICCVW.2017.214}},
  doi          = {{10.1109/ICCVW.2017.214}},
  volume       = {{2018-January}},
  year         = {{2018}},
}