Session II.7 - Computational Harmonic Analysis and Data Science
Thursday, June 15, 16:30 ~ 17:00
Robust low-rank matrix completion with adversarial noise
Felix Krahmer
Technical University of Munich & Munich Center for Machine Learning, Germany - This email address is being protected from spambots. You need JavaScript enabled to view it.
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)..