Efficient Computation of Robust Low-Rank Matrix Approximations in the Presence of Missing Data using the L1 Norm, Anders Eriksson and Anton van den Hengel, 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR 2010), June 2010, San Francisco, USA, IEEE 2009
won the CVPR’10 best paper award. There were almost 1750 submissions to the conference, of which 78, including ours were given oral presentations.
The paper presents a method for calculating a low rank factorisation of a matrix with missing elements on the basis of the L1 norm. Our approach is a generalisation of the Wiberg algorithm for achieving the same result using the L2 norm, which has recently been shown to be highly effective. A key step in the generalisation to the L1 case is to calculate the derivative of the solution to a linear programming problem, which allows the Jacobian of the over-arching minimisation problem to be calculated directly. Results for the new method show a significant performance advantage over competing approaches.
The pdf is available here.
The bibtex is
author = “Anders Eriksson and Anton van den Hengel”,
title = “Efficient Computation of Robust Low-Rank Matrix Approximations in the Presence of Missing Data using the L1 Norm”,
booktitle = “The Twenty-Third IEEE Conference on Computer Vision and Pattern Recognition (CVPR’10)”,
year = “2010″,
month = “June”,
address = “San Francisco, CA”,