■ Matrix Completion under Interval Uncertainty

Abstract. Matrix completion under interval uncertainty can be cast as a matrix completion problem with element-wise box constraints. We present an efficient alternating-direction parallel coordinate-descent method for the problem. We show that the method outperforms any other known method on a benchmark in image in-painting in terms of signal-to-noise ratio, and that it provides high-quality solutions for an instance of collaborative filtering with 100,198,805 recommendations within 5 minutes on a single personal computer.

@article{Marecek2016,
title = "Matrix Completion under Interval Uncertainty ",
journal = "European Journal of Operational Research ",
pages = "to appear",
year = "2017",
issn = "0377-2217",
doi = "http://dx.doi.org/10.1016/j.ejor.2016.07.014",
url = "http://www.sciencedirect.com/science/article/pii/S0377221716305513",
author = "Jakub Marecek and Peter Richtarik and Martin Takac",
keywords = "Matrix Completion",
keywords = "Robust Optimization",
keywords = "Collaborative Filtering",
keywords = "Coordinate Descent",
keywords = "Large-Scale Optimization",
}