Convex Envelopes for Low Rank Approximation

Summary, in English

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: Viktor Larsson; Carl Olsson
• Department/s: Mathematics (Faculty of Engineering); ELLIIT: the Linköping-Lund initiative on IT and mobile communication
• Publishing year: 2015
• Language: English
• Pages: 1-14
• Publication/Series: Energy Minimization Methods in Computer Vision and Pattern Recognition, EMMCVPR 2015
• Volume: 8932
• Links: http://link.springer.com/chapter/10.1007%2F978-3-319-14612-6_1
• Document type: Conference paper
• Publisher: Springer
• Topic: Mathematics
• Conference name: 10th International Conference on Energy Minimization Methods in Computer Vision and Pattern Recognition (EMMCVPR), 2015
• Conference date: 2015-01-13 - 2015-01-16
• Conference place: Hong Kong, China
• Status: Published
• ISBN/ISSN/Other: ISSN: 0302-9743; ISSN: 1611-3349