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 :
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