AN UNBIASED APPROACH TO LOW RANK RECOVERY
(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)
- author
- Carlsson, Marcus LU ; Gerosa, Daniele LU and Olsson, Carl
- organization
- publishing date
- 2022
- 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}}, }