Applications of Matrix completion theory to image processing

Matrix completion is the problem of recovering a low rank matrix from partially observed entries. It has
been widely used in collaborative filtering and recommender systems, dimension reduction and multiclass
learning. This area is a recently emerged field of study following the track of what has been explored in
fields related to compressed sensing. Like in compressed sensing, matrix completion algorithms, therefore,
involve reconstruction of the data matrix from a small subset of its noise corrupted entries. The missing
entries can be recovered under certain conditions when the data matrix has a low rank. The conditions
mainly stipulate that the number of available entries fall below a certain limit; and that some of the rows
and columns of the matrix are completely unknown. There has been extensive work on designing efficient
algorithms for matrix completion with guarantees. Earlier works on matrix completion were based on
convex relaxations. These algorithms achieve strong statistical guarantees, but are quite computationally
expensive in practice. More recently, there has been growing interest in analyzing non-convex algorithms
for matrix completion. These algorithms are much faster than the convex relaxation algorithms, which is
crucial for their empirical success in large-scale collaborative filtering applications. We compare both
convex and non convex approaches for Matrix Completion. The results are generalized to the setting when
the observed entries contain noise.

MPhil CS 2018-2019 INT Dr Joseph Suresh Paul