Advanced

Convex Low Rank Approximation

Larsson, Viktor LU and Olsson, Carl LU (2016) In International Journal of Computer Vision
Abstract

Low rank approximation is an important tool in many applications. Given an observed matrix with elements corrupted by Gaussian noise it is possible to find the best approximating matrix of a given rank through singular value decomposition. However, due to the non-convexity of the formulation it is not possible to incorporate any additional knowledge of the sought matrix without resorting to heuristic optimization techniques. In this paper we propose a convex formulation that is more flexible in that it can be combined with any other convex constraints and penalty functions. The formulation uses the so called convex envelope, which is the provably best possible convex relaxation. We show that for a general class of problems the envelope... (More)

Low rank approximation is an important tool in many applications. Given an observed matrix with elements corrupted by Gaussian noise it is possible to find the best approximating matrix of a given rank through singular value decomposition. However, due to the non-convexity of the formulation it is not possible to incorporate any additional knowledge of the sought matrix without resorting to heuristic optimization techniques. In this paper we propose a convex formulation that is more flexible in that it can be combined with any other convex constraints and penalty functions. The formulation uses the so called convex envelope, which is the provably best possible convex relaxation. We show that for a general class of problems the envelope can be efficiently computed and may in some cases even have a closed form expression. We test the algorithm on a number of real and synthetic data sets and show state-of-the-art results.

(Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
epub
subject
keywords
Convex envelope, Convex relaxation, Low rank approximation, Structure from motion
in
International Journal of Computer Vision
pages
21 pages
publisher
Springer
external identifiers
  • Scopus:84964330213
ISSN
0920-5691
DOI
10.1007/s11263-016-0904-7
language
English
LU publication?
yes
id
0143be4f-909b-4f07-ae42-fbf6fa9b492a
date added to LUP
2016-06-30 12:11:36
date last changed
2016-06-30 12:11:36
@misc{0143be4f-909b-4f07-ae42-fbf6fa9b492a,
  abstract     = {<p>Low rank approximation is an important tool in many applications. Given an observed matrix with elements corrupted by Gaussian noise it is possible to find the best approximating matrix of a given rank through singular value decomposition. However, due to the non-convexity of the formulation it is not possible to incorporate any additional knowledge of the sought matrix without resorting to heuristic optimization techniques. In this paper we propose a convex formulation that is more flexible in that it can be combined with any other convex constraints and penalty functions. The formulation uses the so called convex envelope, which is the provably best possible convex relaxation. We show that for a general class of problems the envelope can be efficiently computed and may in some cases even have a closed form expression. We test the algorithm on a number of real and synthetic data sets and show state-of-the-art results.</p>},
  author       = {Larsson, Viktor and Olsson, Carl},
  issn         = {0920-5691},
  keyword      = {Convex envelope,Convex relaxation,Low rank approximation,Structure from motion},
  language     = {eng},
  month        = {04},
  pages        = {21},
  publisher    = {ARRAY(0xb3038c8)},
  series       = {International Journal of Computer Vision},
  title        = {Convex Low Rank Approximation},
  url          = {http://dx.doi.org/10.1007/s11263-016-0904-7},
  year         = {2016},
}