2024 FFT

Algorithmic approaches to recovering sparse and low-rank matrices

Johannes Maly (LMU)

Abstract: In this talk, we consider the problem of recovering an unknown sparse and low-rank matrix X from observations gathered in a linear measurement process A. We discuss the challenges that come with leveraging several structures simultaneously and discuss two algorithmic strategies to efficiently approach the problem. First, we propose a non-convex variational formulation that lends itself to alternating minimization and whose global minimizers provably approximate X up to noise level. Working with a form of robust injectivity, we derive reconstruction guarantees for various choices of A including sub-gaussian, Gaussian rank-1, and heavy-tailed measurements. Second, under stronger restricted isometry assumptions, we show locally quadratic convergence of an IRLS-type algorithm.