Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Efficient Proximal Mapping Computation for Low-Rank Inducing Norms

Grussler, Christian LU and Giselsson, Pontus LU orcid (2022) In Journal of Optimization Theory and Applications 192(1). p.168-194
Abstract

Low-rank inducing unitarily invariant norms have been introduced to convexify problems with a low-rank/sparsity constraint. The most well-known member of this family is the so-called nuclear norm. To solve optimization problems involving such norms with proximal splitting methods, efficient ways of evaluating the proximal mapping of the low-rank inducing norms are needed. This is known for the nuclear norm, but not for most other members of the low-rank inducing family. This work supplies a framework that reduces the proximal mapping evaluation into a nested binary search, in which each iteration requires the solution of a much simpler problem. The simpler problem can often be solved analytically as demonstrated for the so-called... (More)

Low-rank inducing unitarily invariant norms have been introduced to convexify problems with a low-rank/sparsity constraint. The most well-known member of this family is the so-called nuclear norm. To solve optimization problems involving such norms with proximal splitting methods, efficient ways of evaluating the proximal mapping of the low-rank inducing norms are needed. This is known for the nuclear norm, but not for most other members of the low-rank inducing family. This work supplies a framework that reduces the proximal mapping evaluation into a nested binary search, in which each iteration requires the solution of a much simpler problem. The simpler problem can often be solved analytically as demonstrated for the so-called low-rank inducing Frobenius and spectral norms. The framework also allows to compute the proximal mapping of increasing convex functions composed with these norms as well as projections onto their epigraphs.

(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 inducing norms, Low-rank optimization, Matrix completion, Proximal splitting, Regularization
in
Journal of Optimization Theory and Applications
volume
192
issue
1
pages
168 - 194
publisher
Springer
external identifiers
  • scopus:85120325770
ISSN
0022-3239
DOI
10.1007/s10957-021-01956-2
language
English
LU publication?
yes
id
b381723f-f11d-412f-95c3-a2e1114aa2d4
date added to LUP
2021-12-14 11:43:19
date last changed
2023-11-23 14:26:21
@article{b381723f-f11d-412f-95c3-a2e1114aa2d4,
  abstract     = {{<p>Low-rank inducing unitarily invariant norms have been introduced to convexify problems with a low-rank/sparsity constraint. The most well-known member of this family is the so-called nuclear norm. To solve optimization problems involving such norms with proximal splitting methods, efficient ways of evaluating the proximal mapping of the low-rank inducing norms are needed. This is known for the nuclear norm, but not for most other members of the low-rank inducing family. This work supplies a framework that reduces the proximal mapping evaluation into a nested binary search, in which each iteration requires the solution of a much simpler problem. The simpler problem can often be solved analytically as demonstrated for the so-called low-rank inducing Frobenius and spectral norms. The framework also allows to compute the proximal mapping of increasing convex functions composed with these norms as well as projections onto their epigraphs.</p>}},
  author       = {{Grussler, Christian and Giselsson, Pontus}},
  issn         = {{0022-3239}},
  keywords     = {{Low-rank inducing norms; Low-rank optimization; Matrix completion; Proximal splitting; Regularization}},
  language     = {{eng}},
  number       = {{1}},
  pages        = {{168--194}},
  publisher    = {{Springer}},
  series       = {{Journal of Optimization Theory and Applications}},
  title        = {{Efficient Proximal Mapping Computation for Low-Rank Inducing Norms}},
  url          = {{http://dx.doi.org/10.1007/s10957-021-01956-2}},
  doi          = {{10.1007/s10957-021-01956-2}},
  volume       = {{192}},
  year         = {{2022}},
}