Robust low-rank matrix completion with adversarial noise

Felix Krahmer (TUM) will be giving a talk this Thursday Aug 17th at 2:30 pm in CMSE’s conference room (EGR 1502).  His abstract is below.  He is also visiting MSU and is available for meetings afterward, if anyone is interested.  His office is Wells Hall D223 while he is here.

 

Talk attendance online via zoom is also possible via the zoom link here:  https://sites.google.com/view/minds-seminar/home

 

===================================================

Robust low-rank matrix completion with adversarial noise

The problem of recovering a high-dimensional low-rank matrix from a limited set of random measurements has enjoyed various applications and gained a detailed theoretical foundation over the last 15 years. An instance of particular interest is the matrix completion problem where the measurements are entry observations. The first rirgorous recovery guarantees for this problem were derived for the nuclear norm minimization approach, a convex proxy for the NP-hard problem of constrained rank minimization. For matrices whose entries are ”spread out” well enough, this convex problem admits a unique solution which corresponds to the ground truth. In the presence of random measurement noise, the reconstruction performance is also well-studied, but the performance for adversarial noise remains less understood. While some error bounds have been derived for both convex and nonconvex approaches, these bounds exhibit a gap to information-theoretic lower bounds and provable performance for Gaussian measurements. However, a recent analysis of the problem suggests that under small-scale adversarsial noise, the reconstruction error can be significantly amplified. In this talk, we investigate this amplification quantitatively and provide new reconstruction bounds for both small and large noise levels that suggest a quadratic dependence between the reconstruction error and the noise level.

Joint work with Julia Kostin (ETH Zurich, Switzerland) and Dominik Stöger (KU Eichstätt-Ingolstadt, Germany)