Advanced

A Combinatorial Approach to $L_1$-Matrix Factorization

Jiang, Fangyuan LU ; Enqvist, Olof and Kahl, Fredrik LU (2015) In Journal of Mathematical Imaging and Vision 51(3). p.430-441
Abstract
Recent work on low-rank matrix factorization has focused on the missing data problem and robustness to outliers and therefore the problem has often been studied under the $L_1$-norm. However, due to the non-convexity of the problem, most algorithms are sensitive to initialization and tend to get stuck in a local optimum.



In this paper, we present a new theoretical framework aimed at achieving optimal solutions to the factorization problem. We define a set of stationary points to the problem that will normally contain the optimal solution. It may be too time-consuming to check all these points, but we demonstrate on several practical applications that even by just computing a random subset of these stationary points, one... (More)
Recent work on low-rank matrix factorization has focused on the missing data problem and robustness to outliers and therefore the problem has often been studied under the $L_1$-norm. However, due to the non-convexity of the problem, most algorithms are sensitive to initialization and tend to get stuck in a local optimum.



In this paper, we present a new theoretical framework aimed at achieving optimal solutions to the factorization problem. We define a set of stationary points to the problem that will normally contain the optimal solution. It may be too time-consuming to check all these points, but we demonstrate on several practical applications that even by just computing a random subset of these stationary points, one can achieve significantly better results than current state of the art. In fact, in our experimental results we empirically observe that our competitors rarely find the optimal solution and that our approach is less sensitive to the existence of multiple local minima. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
$L_1$-Matrix Factorization, Robust Estimation, Structure-from-Motion, Photometric Stereo
in
Journal of Mathematical Imaging and Vision
volume
51
issue
3
pages
430 - 441
publisher
Springer
external identifiers
  • wos:000351540200007
  • scopus:84925066132
ISSN
0924-9907
DOI
10.1007/s10851-014-0533-0
language
English
LU publication?
yes
id
50803edf-5042-4ce1-b2ea-0cc3802a1391 (old id 4730646)
date added to LUP
2014-10-27 13:00:16
date last changed
2017-08-27 03:16:41
@article{50803edf-5042-4ce1-b2ea-0cc3802a1391,
  abstract     = {Recent work on low-rank matrix factorization has focused on the missing data problem and robustness to outliers and therefore the problem has often been studied under the $L_1$-norm. However, due to the non-convexity of the problem, most algorithms are sensitive to initialization and tend to get stuck in a local optimum.<br/><br>
<br/><br>
In this paper, we present a new theoretical framework aimed at achieving optimal solutions to the factorization problem. We define a set of stationary points to the problem that will normally contain the optimal solution. It may be too time-consuming to check all these points, but we demonstrate on several practical applications that even by just computing a random subset of these stationary points, one can achieve significantly better results than current state of the art. In fact, in our experimental results we empirically observe that our competitors rarely find the optimal solution and that our approach is less sensitive to the existence of multiple local minima.},
  author       = {Jiang, Fangyuan and Enqvist, Olof and Kahl, Fredrik},
  issn         = {0924-9907},
  keyword      = {$L_1$-Matrix Factorization,Robust Estimation,Structure-from-Motion,Photometric Stereo},
  language     = {eng},
  number       = {3},
  pages        = {430--441},
  publisher    = {Springer},
  series       = {Journal of Mathematical Imaging and Vision},
  title        = {A Combinatorial Approach to $L_1$-Matrix Factorization},
  url          = {http://dx.doi.org/10.1007/s10851-014-0533-0},
  volume       = {51},
  year         = {2015},
}