Matrix Perturbation Bounds and Private Low-Rank Approximation via Dyson Brownian Motion

Abstract: We consider the problem of approximating a matrix $M$ with a rank-$k$ matrix, when given access to a “noisy’’ version of $M$ perturbed by Gaussian noise. This problem arises in numerous applications, including statistics and differentially private low-rank approximation. When applied to the problems of private rank-$k$ covariance matrix approximation and subspace recovery, our bounds yield improvements over previous utility bounds.  Our bounds are obtained by viewing the addition of Gaussian noise as a continuous-time matrix Brownian motion.  This viewpoint allows us to track the evolution of eigenvalues and eigenvectors of the matrix, which are governed by stochastic differential equations discovered by Dyson.  These equations allow us to bound the Frobenius distance utility as the square-root of a sum-of-squares of perturbations to the eigenvectors, as opposed to a sum of perturbation bounds obtained via deterministic Davis-Kahan-type perturbation theorems.

Bio: Oren Mangoubi is an assistant professor in Mathematical Sciences and Data Science at Worcester Polytechnic Institute.  His research is focused on the design and analysis of fast algorithms for optimization and Bayesian sampling, and on the application of these algorithms to problems in machine learning, data science, and differential privacy. He advises three PhD students in Data Science and Mathematical Sciences, and his research has been recognized by an NSF CISE-CRII grant as well as a Google Research Scholar grant. Before joining WPI, Oren completed his PhD at MIT, and was a postdoctoral researcher at EPFL in Switzerland and at the University of Ottawa.