Efficient Proximal Mapping Computation for Low-Rank Inducing Norms
(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)
- author
- Grussler, Christian LU and Giselsson, Pontus LU
- organization
- publishing date
- 2022
- 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}}, }