Convex Low Rank Approximation
(2016) In International Journal of Computer Vision 120(2). p.194-214- 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)
- author
- Larsson, Viktor LU and Olsson, Carl LU
- organization
- publishing date
- 2016
- type
- Contribution to journal
- publication status
- published
- subject
- keywords
- Convex envelope, Convex relaxation, Low rank approximation, Structure from motion
- in
- International Journal of Computer Vision
- volume
- 120
- issue
- 2
- pages
- 21 pages
- publisher
- Springer
- external identifiers
-
- scopus:84964330213
- wos:000382092900005
- 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
- 2024-04-19 05:21:01
@article{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}},
keywords = {{Convex envelope; Convex relaxation; Low rank approximation; Structure from motion}},
language = {{eng}},
number = {{2}},
pages = {{194--214}},
publisher = {{Springer}},
series = {{International Journal of Computer Vision}},
title = {{Convex Low Rank Approximation}},
url = {{http://dx.doi.org/10.1007/s11263-016-0904-7}},
doi = {{10.1007/s11263-016-0904-7}},
volume = {{120}},
year = {{2016}},
}