April 21, Wednesday 14:15, Room 303, Jacobs

A deterministic algorithm for matrix completion

Lecturer : Adi Shraibman

Lecturer homepage : http://en.scientificcommons.org/adi_shraibman

Affiliation : Tel-Aviv University


Abstract:

We consider the problem of approximating a noisy or a 

partially observed target matrix Y, with a concept matrix X. 

A common approach for this problem is to choose a matrix X

that minimizes some combination of the rank of X and the distance

between X and Y. This approach is often used when analysing tabulated

data such as gene expression, word counts in a corpus of documents,

collections of images, etc.

 

Recently, the trace norm is considered in the above scheme

instead of the rank. That is, we choose a matrix X that minimizes 

some combination of the trace norm of X and the distance between X 

and Y. The choice of the trace norm as a complexity measure is

motivated as a convex surrogate to the rank (Fazel et al., 2001;

Candes and Tao, 2009), but there is also an independent motivation

(Srebro et al, 2005; Bach, 2008).

 

We describe a first deterministic algorithm for this problem. Our algorithm 

is similar to the former ones, but it uses no randomization for choosing the

initial sample of entries. The heart of our analysis is a structural property of real

matrices with small trace norm. 

 

Joint work with Eyal Heiman