CUED Publications database

Low-rank inducing norms with optimality interpretations <sup>∗</sup>

Grussler, C and Giselsson, P (2018) Low-rank inducing norms with optimality interpretations <sup>∗</sup>. SIAM Journal on Optimization, 28. pp. 3057-3078. ISSN 1052-6234

Full text not available from this repository.


Optimization problems with rank constraints appear in many diverse fields such as control, machine learning, and image analysis. Since the rank constraint is nonconvex, these problems are often approximately solved via convex relaxations. Nuclear norm regularization is the prevailing convexifying technique for dealing with these types of problem. This paper introduces a family of low-rank inducing norms and regularizers which include the nuclear norm as a special case. A posteriori guarantees on solving an underlying rank constrained optimization problem with these convex relaxations are provided. We evaluate the performance of the low-rank inducing norms on three matrix completion problems. In all examples, the nuclear norm heuristic is outperformed by convex relaxations based on other low-rank inducing norms. For two of the problems there exist low-rank inducing norms that succeed in recovering the partially unknown matrix, while the nuclear norm fails. These low-rank inducing norms are shown to be representable as semidefinite programs. Moreover, these norms have cheaply computable proximal mappings, which make it possible to also solve problems of large size using first-order methods.

Item Type: Article
Uncontrolled Keywords: low-rank optimization low-rank inducing norms regularization matrix completion semidefinite programming
Divisions: Div F > Control
Depositing User: Cron Job
Date Deposited: 13 Nov 2018 01:53
Last Modified: 09 Sep 2021 01:18
DOI: 10.1137/17M1115770