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 noiseThe 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)
