Non-convex Matrix Sensing: Breaking the Quadratic Rank Barrier in Sample Complexity

Learn about groundbreaking research in matrix reconstruction through this USC Probability and Statistics seminar talk that explores efficient methods for reconstructing low-rank matrices from limited linear measurements. Dive into the comparison between traditional convex approaches using nuclear norm minimization and computationally less expensive non-convex methods employing factorized gradient descent. Discover how the speaker improves upon existing techniques by reducing the sample complexity of non-convex matrix factorization from quadratic to linear rank-dependence when reconstructing positive semidefinite matrices from Gaussian measurements. Follow along as the presentation introduces a novel probabilistic decoupling argument demonstrating that gradient descent iterates maintain only weak dependencies on individual measurement matrix entries. The research, conducted in collaboration with Dominik Stöger from KU Eichstätt-Ingolstadt, represents a significant advancement in matrix sensing theory and computational efficiency.