Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

AN UNBIASED APPROACH TO LOW RANK RECOVERY

Carlsson, Marcus LU ; Gerosa, Daniele LU and Olsson, Carl (2022) In SIAM Journal on Optimization 32(4). p.2969-2996
Abstract

Low rank recovery problems have been a subject of intense study in recent years. While the rank function is useful for regularization it is difficult to optimize due to its nonconvexity and discontinuity. The standard remedy for this is to exchange the rank function for the convex nuclear norm, which is known to favor low rank solutions under certain conditions. On the downside the nuclear norm exhibits a shrinking bias that can severely distort the solution in the presence of noise, which motivates the use of stronger nonconvex alternatives. In this paper we study two such formulations. We characterize the critical points and give sufficient conditions for a low rank stationary point to be unique. Moreover, we derive conditions that... (More)

Low rank recovery problems have been a subject of intense study in recent years. While the rank function is useful for regularization it is difficult to optimize due to its nonconvexity and discontinuity. The standard remedy for this is to exchange the rank function for the convex nuclear norm, which is known to favor low rank solutions under certain conditions. On the downside the nuclear norm exhibits a shrinking bias that can severely distort the solution in the presence of noise, which motivates the use of stronger nonconvex alternatives. In this paper we study two such formulations. We characterize the critical points and give sufficient conditions for a low rank stationary point to be unique. Moreover, we derive conditions that ensure global optimality of the low rank stationary point and show that these hold under moderate noise levels.

(Less)
Please use this url to cite or link to this publication:
author
; and
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
low rank completion, nonconvex optimization, quadratic envelope regularization
in
SIAM Journal on Optimization
volume
32
issue
4
pages
28 pages
publisher
Society for Industrial and Applied Mathematics
external identifiers
  • scopus:85146370284
ISSN
1052-6234
DOI
10.1137/19M1294800
language
English
LU publication?
yes
id
98a6ed33-4818-4b40-995b-40fdcceb8be4
date added to LUP
2023-02-16 08:24:40
date last changed
2023-02-16 08:29:07
@article{98a6ed33-4818-4b40-995b-40fdcceb8be4,
  abstract     = {{<p>Low rank recovery problems have been a subject of intense study in recent years. While the rank function is useful for regularization it is difficult to optimize due to its nonconvexity and discontinuity. The standard remedy for this is to exchange the rank function for the convex nuclear norm, which is known to favor low rank solutions under certain conditions. On the downside the nuclear norm exhibits a shrinking bias that can severely distort the solution in the presence of noise, which motivates the use of stronger nonconvex alternatives. In this paper we study two such formulations. We characterize the critical points and give sufficient conditions for a low rank stationary point to be unique. Moreover, we derive conditions that ensure global optimality of the low rank stationary point and show that these hold under moderate noise levels.</p>}},
  author       = {{Carlsson, Marcus and Gerosa, Daniele and Olsson, Carl}},
  issn         = {{1052-6234}},
  keywords     = {{low rank completion; nonconvex optimization; quadratic envelope regularization}},
  language     = {{eng}},
  number       = {{4}},
  pages        = {{2969--2996}},
  publisher    = {{Society for Industrial and Applied Mathematics}},
  series       = {{SIAM Journal on Optimization}},
  title        = {{AN UNBIASED APPROACH TO LOW RANK RECOVERY}},
  url          = {{http://dx.doi.org/10.1137/19M1294800}},
  doi          = {{10.1137/19M1294800}},
  volume       = {{32}},
  year         = {{2022}},
}