Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Relaxations for Non-Separable Cardinality/Rank Penalties

Olsson, Carl LU ; Gerosa, Daniele LU and Carlsson, Marcus LU (2021) In IEEE International Conference on Computer Vision Workshops p.162-171
Abstract
Rank and cardinality penalties are hard to handle in optimization frameworks due to non-convexity and discontinuity. Strong approximations have been a subject of intense study and numerous formulations have been proposed. Most of these can be described as separable, meaning that they apply a penalty to each element (or singular value) based on size, without considering the joint distribution. In this paper we present a class of non-separable penalties and give a recipe for computing strong relaxations suitable for optimization. In our analysis of this formulation we first give conditions that ensure that the global ly optimal solution of the relaxation is the same as that of the original (unrelaxed) objective. We then show how a stationary... (More)
Rank and cardinality penalties are hard to handle in optimization frameworks due to non-convexity and discontinuity. Strong approximations have been a subject of intense study and numerous formulations have been proposed. Most of these can be described as separable, meaning that they apply a penalty to each element (or singular value) based on size, without considering the joint distribution. In this paper we present a class of non-separable penalties and give a recipe for computing strong relaxations suitable for optimization. In our analysis of this formulation we first give conditions that ensure that the global ly optimal solution of the relaxation is the same as that of the original (unrelaxed) objective. We then show how a stationary point can be guaranteed to be unique under the restricted isometry property (RIP) assumption. (Less)
Please use this url to cite or link to this publication:
author
; and
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
host publication
2021 IEEE/CVF International Conference on Computer Vision Workshops (ICCVW)
series title
IEEE International Conference on Computer Vision Workshops
pages
10 pages
publisher
IEEE - Institute of Electrical and Electronics Engineers Inc.
external identifiers
  • scopus:85123050515
ISSN
2473-9936
2473-9944
ISBN
978-1-6654-0192-0
978-1-6654-0191-3
DOI
10.1109/ICCVW54120.2021.00023
language
English
LU publication?
yes
id
b6215171-7744-4eb7-97ea-2686c6843ad6
alternative location
https://openaccess.thecvf.com/content/ICCV2021W/RSLCV/papers/Olsson_Relaxations_for_Non-Separable_CardinalityRank_Penalties_ICCVW_2021_paper.pdf
date added to LUP
2021-11-17 13:05:37
date last changed
2024-03-27 22:02:15
@inproceedings{b6215171-7744-4eb7-97ea-2686c6843ad6,
  abstract     = {{Rank and cardinality penalties are hard to handle in optimization frameworks due to non-convexity and discontinuity. Strong approximations have been a subject of intense study and numerous formulations have been proposed. Most of these can be described as separable, meaning that they apply a penalty to each element (or singular value) based on size, without considering the joint distribution. In this paper we present a class of non-separable penalties and give a recipe for computing strong relaxations suitable for optimization. In our analysis of this formulation we first give conditions that ensure that the global ly optimal solution of the relaxation is the same as that of the original (unrelaxed) objective. We then show how a stationary point can be guaranteed to be unique under the restricted isometry property (RIP) assumption.}},
  author       = {{Olsson, Carl and Gerosa, Daniele and Carlsson, Marcus}},
  booktitle    = {{2021 IEEE/CVF International Conference on Computer Vision Workshops (ICCVW)}},
  isbn         = {{978-1-6654-0192-0}},
  issn         = {{2473-9936}},
  language     = {{eng}},
  pages        = {{162--171}},
  publisher    = {{IEEE - Institute of Electrical and Electronics Engineers Inc.}},
  series       = {{IEEE International Conference on Computer Vision Workshops}},
  title        = {{Relaxations for Non-Separable Cardinality/Rank Penalties}},
  url          = {{http://dx.doi.org/10.1109/ICCVW54120.2021.00023}},
  doi          = {{10.1109/ICCVW54120.2021.00023}},
  year         = {{2021}},
}