Processing math: 100%
Skip to yearly menu bar Skip to main content


Poster

Singular Subspace Perturbation Bounds via Rectangular Random Matrix Diffusions

Peiyao Lai · Oren Mangoubi

Hall 3 + Hall 2B #456
[ ]
Wed 23 Apr 7 p.m. PDT — 9:30 p.m. PDT

Abstract: Given a matrix ARm×d with singular values σ1σd, and a random matrix GRm×d with iid N(0,T) entries for some T>0, we derive new bounds on the Frobenius distance between subspaces spanned by the top-k (right) singular vectors of A and A+G. This problem arises in numerous applications in statistics where a data matrix may be corrupted by Gaussian noise, and in the analysis of the Gaussian mechanism in differential privacy, where Gaussian noise is added to data to preserve private information. We show that, for matrices A where the gaps in the top-k singular values are roughly Ω(σkσk+1) the expected Frobenius distance between the subspaces is ˜O(dσkσk+1×T), improving on previous bounds by a factor of md. To obtain our bounds we view the perturbation to the singular vectors as a diffusion process-- the Dyson-Bessel process-- and use tools from stochastic calculus to track the evolution of the subspace spanned by the top-k singular vectors, which may be of independent interest.

Live content is unavailable. Log in and register to view live content