Advanced

Optimality interpretations for atomic norms

Grussler, Christian LU and Giselsson, Pontus LU (2019) 18th European Control Conference, ECC 2019 p.1473-1477
Abstract

Atomic norms occur frequently in data science and engineering problems such as matrix completion, sparse linear regression, system identification and many more. These norms are often used to convexify non-convex optimization problems, which are convex apart from the solution lying in a non-convex set of so-called atoms. For the convex part being a linear constraint, the ability of several atomic norms to solve the original non-convex problem has been analyzed by means of tangent cones. This paper presents an alternative route for this analysis by showing that atomic norm convexifcations always provide an optimal convex relaxation for some related non-convex problems. As a result, we obtain the following benefits: (i) treatment of... (More)

Atomic norms occur frequently in data science and engineering problems such as matrix completion, sparse linear regression, system identification and many more. These norms are often used to convexify non-convex optimization problems, which are convex apart from the solution lying in a non-convex set of so-called atoms. For the convex part being a linear constraint, the ability of several atomic norms to solve the original non-convex problem has been analyzed by means of tangent cones. This paper presents an alternative route for this analysis by showing that atomic norm convexifcations always provide an optimal convex relaxation for some related non-convex problems. As a result, we obtain the following benefits: (i) treatment of arbitrary convex constraints, (ii) potentially obtaining solutions to the non-convex problem with a posteriori success certificates, (iii) utilization of additional prior knowledge through the design or learning of the non-convex problem.

(Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
host publication
2019 18th European Control Conference, ECC 2019
pages
5 pages
publisher
Institute of Electrical and Electronics Engineers Inc.
conference name
18th European Control Conference, ECC 2019
conference location
Naples, Italy
conference dates
2019-06-25 - 2019-06-28
external identifiers
  • scopus:85071594501
ISBN
9783907144008
DOI
10.23919/ECC.2019.8795721
language
English
LU publication?
yes
id
43c9b01a-7bbd-4611-bf26-e2c5d97f3277
date added to LUP
2019-09-20 08:19:36
date last changed
2019-10-08 03:58:52
@inproceedings{43c9b01a-7bbd-4611-bf26-e2c5d97f3277,
  abstract     = {<p>Atomic norms occur frequently in data science and engineering problems such as matrix completion, sparse linear regression, system identification and many more. These norms are often used to convexify non-convex optimization problems, which are convex apart from the solution lying in a non-convex set of so-called atoms. For the convex part being a linear constraint, the ability of several atomic norms to solve the original non-convex problem has been analyzed by means of tangent cones. This paper presents an alternative route for this analysis by showing that atomic norm convexifcations always provide an optimal convex relaxation for some related non-convex problems. As a result, we obtain the following benefits: (i) treatment of arbitrary convex constraints, (ii) potentially obtaining solutions to the non-convex problem with a posteriori success certificates, (iii) utilization of additional prior knowledge through the design or learning of the non-convex problem.</p>},
  author       = {Grussler, Christian and Giselsson, Pontus},
  isbn         = {9783907144008},
  language     = {eng},
  location     = {Naples, Italy},
  pages        = {1473--1477},
  publisher    = {Institute of Electrical and Electronics Engineers Inc.},
  title        = {Optimality interpretations for atomic norms},
  url          = {http://dx.doi.org/10.23919/ECC.2019.8795721},
  year         = {2019},
}