FoCM 2014 conference
Workshop C3 - Learning Theory
December 19, 17:00 ~ 17:30 - Room B23
Algebraic Combinatorial Single-Entry Low-Rank Matrix Completion
Franz Kiraly
University College London, UK - f.kiraly@ucl.ac.uk
In recent years, the low-rank matrix completion model has enjoyed quite some success for recommendation and prediction learning. Many standard algorithms in the field are designed for completing the whole matrix (or derivates) - which also means that achieving scalability on huge data sets is a challenging task. The algebraic combinatorial approach aims for scalability in a canonical and non-heuristic way: instead of considering "global" properties of the matrix - e.g. low nuclear norm, sparse factorization - the underlying theory describes low-rankness "locally", in terms of algebraic relations between small numbers of entries and combinatorial properties of the observation pattern, both closely interrelated. Algorithmically, this allows to obtain estimates for single entries and error bounds while looking only at a small part of the observation data in the "combinatorial neighbourhood", described by the bipartite graph of observations. The algebraic combinatorial approach therefore allows, for the first time, a systematic treatment of single-entry estimates including single-entry error bounds, and it yields, for the first time, a closed approach to the low-rank model that is intrinsically local. In the talk, I will give a brief introduction to the matrix completion problem and its algebraic combinatorial formulation; I will demonstrate how this allows to derive simple reconstruction algorithms, and review some recent empirical results.
Joint work with Duncan Blythe (TU Berlin), Louis Theran (Aalto University, Helsinki) and Ryota Tomioka (TTI Chicago).