A Non-convex Relaxation for Fixed-Rank Approximation
(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)
- author
- Olsson, Carl LU ; Carlsson, Marcus LU and Bylow, Erik LU
- organization
- publishing date
- 2018-01-19
- 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}}, }