Advanced

Convex Envelopes for Low Rank Approximation

Larsson, Viktor LU and Olsson, Carl LU (2015) 10th International Conference on Energy Minimization Methods in Computer Vision and Pattern Recognition (EMMCVPR), 2015 In Energy Minimization Methods in Computer Vision and Pattern Recognition, EMMCVPR 2015 8932. p.1-14
Abstract
In this paper we consider the classical problem of finding a low rank approximation of a given matrix. In a least squares sense a closed form solution is available via factorization. However, with additional constraints, or in the presence of missing data, the problem becomes much more difficult. In this paper we show how to efficiently compute the convex envelopes of a class of rank minimization formulations. This opens up the possibility of adding additional convex constraints and functions to the minimization problem resulting in strong convex relaxations. We evaluate the framework on both real and synthetic data sets and demonstrate state-of-the-art performance.
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
in
Energy Minimization Methods in Computer Vision and Pattern Recognition, EMMCVPR 2015
volume
8932
pages
1 - 14
publisher
Springer
conference name
10th International Conference on Energy Minimization Methods in Computer Vision and Pattern Recognition (EMMCVPR), 2015
external identifiers
  • wos:000357502000001
  • scopus:84921849025
ISSN
1611-3349
0302-9743
language
English
LU publication?
yes
id
b1b09423-fea4-4528-aa22-3e1f67c1f643 (old id 7790959)
alternative location
http://link.springer.com/chapter/10.1007%2F978-3-319-14612-6_1
date added to LUP
2015-09-02 16:08:54
date last changed
2017-05-28 03:11:02
@inproceedings{b1b09423-fea4-4528-aa22-3e1f67c1f643,
  abstract     = {In this paper we consider the classical problem of finding a low rank approximation of a given matrix. In a least squares sense a closed form solution is available via factorization. However, with additional constraints, or in the presence of missing data, the problem becomes much more difficult. In this paper we show how to efficiently compute the convex envelopes of a class of rank minimization formulations. This opens up the possibility of adding additional convex constraints and functions to the minimization problem resulting in strong convex relaxations. We evaluate the framework on both real and synthetic data sets and demonstrate state-of-the-art performance.},
  author       = {Larsson, Viktor and Olsson, Carl},
  booktitle    = {Energy Minimization Methods in Computer Vision and Pattern Recognition, EMMCVPR 2015},
  issn         = {1611-3349},
  language     = {eng},
  pages        = {1--14},
  publisher    = {Springer},
  title        = {Convex Envelopes for Low Rank Approximation},
  volume       = {8932},
  year         = {2015},
}