Convex Low Rank Approximation

Research output: Contribution to journalArticlepeer-review

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 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.

Original languageEnglish
Pages (from-to)194-214
Number of pages21
JournalInternational Journal of Computer Vision
Volume120
Issue number2
DOIs
Publication statusPublished - 2016

Subject classification (UKÄ)

  • Computer Vision and Robotics (Autonomous Systems)
  • Mathematics

Free keywords

  • Convex envelope
  • Convex relaxation
  • Low rank approximation
  • Structure from motion

Fingerprint

Dive into the research topics of 'Convex Low Rank Approximation'. Together they form a unique fingerprint.

Cite this