Georgia Institute of Technology College of Sciences

The goal in matrix recovery problems is to estimate an unknown rank-r matrix S of size m based on a set of n observations. It is easy to see that even in the case where the observations are not contaminated with noise, there exist low rank matrices that cannot be recovered based on n observations unless n is very large. In order to deal with these cases, Candes and Tao introduced the called low-coherence assumptions and a parameter \nu measuring how low-coherent the objective matrix S is. Using the low-coherence assumptions, Gross proved that S can be recovered with high probability if n>O(\nu r m \log^2(m)) by an estimator based on nuclear norm penalization. Let's consider the generalization of the matrix recovery problem where the matrix S is not only low-rank but also "smooth" with respect to the geometry given by a graph G. In this 40 minutes long talk, the speaker will present an approximation error bound for a proposed estimator in this generalization of the matrix recovery problem.