Advanced

Rank Minimization with Structured Data Patterns

Larsson, Viktor LU ; Olsson, Carl LU ; Bylow, Erik LU and Kahl, Fredrik LU (2014) 13th European Conference on Computer Vision (ECCV) In Computer Vision - ECCV 2014, PT III 8691. p.250-265
Abstract
The problem of finding a low rank approximation of a given measurement matrix is of key interest in computer vision. If all the elements of the measurement matrix are available, the problem can be solved using factorization. However, in the case of missing data no satisfactory solution exists. Recent approaches replace the rank term with the weaker (but convex) nuclear norm. In this paper we show that this heuristic works poorly on problems where the locations of the missing entries are highly correlated and structured which is a common situation in many applications. Our main contribution is the derivation of a much stronger convex relaxation that takes into account not only the rank function but also the data. We propose an algorithm... (More)
The problem of finding a low rank approximation of a given measurement matrix is of key interest in computer vision. If all the elements of the measurement matrix are available, the problem can be solved using factorization. However, in the case of missing data no satisfactory solution exists. Recent approaches replace the rank term with the weaker (but convex) nuclear norm. In this paper we show that this heuristic works poorly on problems where the locations of the missing entries are highly correlated and structured which is a common situation in many applications. Our main contribution is the derivation of a much stronger convex relaxation that takes into account not only the rank function but also the data. We propose an algorithm which uses this relaxation to solve the rank approximation problem on matrices where the given measurements can be organized into overlapping blocks without missing data. The algorithm is computationally efficient and we have applied it to several classical problems including structure from motion and linear shape basis estimation. We demonstrate on both real and synthetic data that it outperforms state-of-the-art alternatives. (1) (Less)
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
Computer Vision - ECCV 2014, PT III
volume
8691
pages
250 - 265
publisher
Springer
conference name
13th European Conference on Computer Vision (ECCV)
external identifiers
  • wos:000345527000017
  • scopus:84906506674
ISSN
1611-3349
0302-9743
language
English
LU publication?
yes
id
d6885d0e-0318-4f05-8262-5cde5e54e6cd (old id 4982568)
date added to LUP
2015-01-27 12:49:02
date last changed
2017-05-28 03:15:27
@inproceedings{d6885d0e-0318-4f05-8262-5cde5e54e6cd,
  abstract     = {The problem of finding a low rank approximation of a given measurement matrix is of key interest in computer vision. If all the elements of the measurement matrix are available, the problem can be solved using factorization. However, in the case of missing data no satisfactory solution exists. Recent approaches replace the rank term with the weaker (but convex) nuclear norm. In this paper we show that this heuristic works poorly on problems where the locations of the missing entries are highly correlated and structured which is a common situation in many applications. Our main contribution is the derivation of a much stronger convex relaxation that takes into account not only the rank function but also the data. We propose an algorithm which uses this relaxation to solve the rank approximation problem on matrices where the given measurements can be organized into overlapping blocks without missing data. The algorithm is computationally efficient and we have applied it to several classical problems including structure from motion and linear shape basis estimation. We demonstrate on both real and synthetic data that it outperforms state-of-the-art alternatives. (1)},
  author       = {Larsson, Viktor and Olsson, Carl and Bylow, Erik and Kahl, Fredrik},
  booktitle    = {Computer Vision - ECCV 2014, PT III},
  issn         = {1611-3349},
  language     = {eng},
  pages        = {250--265},
  publisher    = {Springer},
  title        = {Rank Minimization with Structured Data Patterns},
  volume       = {8691},
  year         = {2014},
}