Singular Subspace Perturbation Bounds via Rectangular Random Matrix Diffusions

Given a matrix A ∈ R m×d with singular values σ 1 ≥ • • • ≥ σ d , and a random matrix G ∈ R m×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 Õ(

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.

. This in turn implies bounds on the Frobenius norm of

(3) O'Rourke et al. (2023) show that their spectral norm bounds are tight with respect to the subspace spanned by the top-k m-dimensional left singular vectors of A ∈ R m×d when m ≥ d. However, the bounds in equation 3 do not imply tight bounds on the perturbation Vk

k to the subspace spanned by the top-k d-dimensional right singular vectors. In particular, the bound on the peturbation

k to the subspace spanned by the top-k d-dimensional right singular vectors implied by equation 3 grows proportional to the (square root of) the larger of the matrix dimensions √ m.

This leads to the question of whether one can obtain improved bounds on the perturbation

k ∥ F to the subspace spanned by the top-k d-dimensional right singular vectors of an m × d matrix A with m > d perturbed by Gaussian noise, which do not grow with the larger dimension m. Subspace perturbation bounds have also been obtained in different settings where the input matrix, and random matrix perturbation, is a symmetric matrix (see e.g. Dwork et al. (2014); Eldridge et al. (2018); Fan et al. (2018)). For instance, Dwork et al. (2014) obtain perturbation bounds for covariance