[Colloquium] Tomorrow's colloquium talk at TTIC

[Jinbo Xu]

When:     Tuesday, November 26th at 11am
Where:    TTIC, 6045 S Kenwood Avenue, 5th Floor, Room #526
Who:       Dr. Dr. Franz Király (University College London)
host:        Ryota Tomioka <tomioka at ttic.edu>
Title:       Algebraic Combinatorial Solution Strategies for Matrix Completion

Abstract:
Matrix completion is the inverse problem of reconstructing missing
entries in a potentially noisy low-rank matrix. We give a short
introduction to the most common application scenarios (recommender
systems, compressed sensing), and overview some existing solution
strategies.

We explain how matrix completion is algebraic - through the low-rank
assumption - and combinatorial - through the pattern of observations.
We show how the algebraic combinatorial properties of the true matrix
and the observation pattern can be encoded in a bipartite graph whose
combinatorics determine the solvability of the problem, and
demonstrate how some previously known results, e.g., the sufficient
and necessary O(n log n) bound for the random sampling density in
order to achieve reconstruction, can be completely explained in terms
of the combinatorial properties of the graph.

 Furthermore, we show how the knowledge on algebraic and combinatorial
features of the problem can be used to obtain a noise-consistent
estimator for the reconstruction of single missing entries, or the
denoising of single observed entries, and a noise-consistent estimator
for the reconstruction accuracy which is independent of the
reconstruction method.

-- 
_________________________________________
Associate Professor
Toyota Technological Institute at Chicago
6045 S. Kenwood Ave.
Chicago, IL 60637
fax: 773 834 2557, Google Voice: 773 359 3721
http://ttic.uchicago.edu/~jinbo/