Improved very sparse matrix completing using an intentionally randomized “asymmetric SVD”

Abstract: We consider the matrix completion problem in the very sparse regime where, on average, a constant number of entries of the matrix are observed per row (or column). In this very sparse regime, we cannot expect to have perfect recovery and the celebrated nuclear norm based matrix completion fails because the singular value decomposition (SVD) of the underlying very sparse matrix completely breaks down.
We demonstrate that it is indeed possible to reliably recover the matrix. The key idea is the use of a randomized asymmetric SVD to find informative singular vectors in this regime in a way that the SVD cannot. We provide sharp theoretical analysis of the phenomenon, the lower limits of statistical recovery and demonstrate the effiacy of the new method using simulations.

Bio: I am an associate professor in the Department of Electrical Engineering and Computer Science at the University of Michigan. I received my Masters and PhD in Electrical Engineering and Computer Science as part of the MIT/WHOI Joint Program in Ocean Science and Engineering at MIT. I work at the interface of statistical signal processing and random matrix theory with applications such as sonar, radar, wireless communications and machine learning in mind. I particularly enjoy using random matrix theory to address problems that arise in statistical signal processing. An important component of my work is applying it in real-world settings to tease out low-level signals from sensor, oceanographic, financial and econometric time/frequency measurements/time series. In addition to the satisfaction derived from transforming the theory into practice, real-world settings give us insight into how the underlying techniques can be refined and/or made more robust.

*** This Event will take place in a hybrid format. The location for in-person attendance will be room 1311 EECS. Attendance will also be available via Zoom.

Join Zoom Meeting: https://umich.zoom.us/j/93679028340

Meeting ID: 936 7902 8340

Passcode: XXXXXX (Will be sent via e-mail to attendees)

Zoom Passcode information is also available upon request to Kristi Rieger([email protected])