Room 327

Credit Seminar

Yogesh Dahiya

IMSc

Work on the following two problems will be presented
1. Given a data matrix $A\in R^{n\times d}$, containing a set of $n$
points in $R^d$ with $k$ outliers, we study the problem of learning
the outliers such that the remaining set of points best fit into some
unknown $r$-dimensional subspace. We obtain a randomized approximation
algorithm running in time n^{\log n r^2/\epsilon^2} providing
(1+\epsilon)OPT guarantee w.h.p. This is joint work with Kirill,
Fahad, and Fedor Fomin
2. We study the problem of matrix completion that is given a matrix
$A$ (over some field) with missing entries, the goal is to complete
the entries of $A$ so as to minimize its rank. We obtain following
results
a) $p^{O(k.r)} poly(n,m)$ fpt algorithm where $p$ is the size of the
field, $k$ is the number of rows with missing entries and $r$ is the
desired rank of the output matrix.
b) $2^k poly(k+r)$ kernel
c) $f(k,r)poly(n,m)$ FPT algorithm on real field where $f$ is some funciton.