[Colloquium] Algebraic Combinatorial Solution Strategies for Matrix Completion

[Ryota Tomioka]

Those who you are interested, the talk is starting NOW!

On Mon, Nov 25, 2013 at 1:55 PM, Jinbo Xu <jinbo.xu at gmail.com> wrote:
> 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/



-- 
Ryota Tomioka, PhD
Research Assistant Professor
Toyota Technological Institute at Chicago