Singular Subspace Perturbation Bounds via Rectangular Random Matrix Diffusions

The paper studies a very interesting problem, namely that of bounding the Frobenius norm of the subspaces spanned by the top-k singular vectors of any fixed matrix A and A+G. The paper is well structured and reads well, but has very few thematic overlaps with the ICLR.

I am rejecting this paper for two reasons. First, the authors used the wrong template with significantly wider margins than the standard ICLR template. While this is nitpicking, choosing the right template comes with no overhead but is critical to maintain fair standards on the length of the paper among all submissions.

The second reason is that the paper targets a problem in random matrix theory, which would fit well to a conference like ALT or COLT or a mathematical journal. In order to submit this paper to ICLR, I would expect at least one longer section highlighting the connections to machine learning and demonstrate how these bounds help us to arrive at non-trivial novel insights directly relevant for machine learning.

This paper considers estimation of the right singular subspace of a matrix $A\in\mathbb{R}^{m\times d}$ when the matrix is perturbed by a Gaussian random matrix. The authors focused on the case $d>m$ and derived a perturbation Frobenius bound independent of $m$.

This paper studies the Frobenius norm distance between the projection matrix to the top rank-k row space of A and the projection matrix to the top rank-k row space of A + G where G is a random Gaussian matrix and A is a tall n x d matrix, i.e., n >> d. The previous result by O’Rourke et al. (2023) shows that if one considers both distances between the projection matrices corresponding to column space and row space, then they can get a tight result. In this work, authors gave an improved bound when considering the projection matrices to row spaces only.

This paper presents new bounds on the Frobenius norm of the perturbation to the singular subspace spanned by the top-k right singular vectors of a matrix $A \in \mathbb{R}^{m \times d}$, when $A$ is perturbed by a matrix $G \in \mathbb{R}^{m \times d}$ with Gaussian $\mathcal{N}(0,T)$ random entries. More specifically, assuming $A$ has a top-k singular value gap of at least $\Omega(\sqrt{mT})$ (i.e. $\sigma_i-\sigma_{i+1} \geq \Omega(\sqrt{mT})$ for all $i \in [k]$), the paper bounds the expected Frobenius norm distance between the projection matrices on the top $k$ right singular subspaces of $A$ and $A+G$ by roughly $O( \frac{ \sqrt{kdT} }{ \sigma_k - \sigma_{k+1} })$ where $\sigma_1 \geq \ldots \geq \sigma_d \geq 0$ are the singular values of $A$. When $\sigma_i - \sigma_{i+1} \geq \Omega( \sigma_k -\sigma_{k+1} )$ for $i \in [k]$ is also true, the bound is $O(\frac{ \sqrt{dT} }{ \sigma_k - \sigma_{k+1} })$ which improves upon previously known high probability bounds on the actual Frobenius norm distance by $\frac{\sqrt{m}}{\sqrt{d}}$. The paper also improves previously known bounds for the rank-k covariance matrix approximation by a factor of $\frac{\sqrt{m}}{\sqrt{d}}$.

To derive the bounds, the paper views the addition of a gaussian noise matrix to $A$ as a Brownian motion on the entries of a matrix $\Phi(t) := A+B(t)$ where $B(t)$ is a matrix whose entries undergo standard Brownian motion. This Brownian motion induces a stochastic diffusion process, known as the Dyson-Bessel process on the singular values and singular vectors of $\Phi(t)$. The evolution of the eigenvalues and eigenvectors of of this matrix is determined by a system of stochastic differential equations. Using techniques from stochastic calculus (Ito's lemma), the evolution of the Frobenius distance can be tracked as a stochastic integral of a sum-of-squares of perturbations to the right singular vectors of $\Phi(t)$. Overall, higher order matrix derivatives which appear in the Taylor series expansion of deterministic perturbations vanish in the stochastic case due to the independence of random noise in the Brownian motion and this gives the stronger bounds.

The paper provides a new upper-bound for the right singular vectors of a perturbed matrix by Gaussian noise. The authors show that under a set of extra assumptions compared to the literature, we are able to further reduce the bound for tall matrices. The authors used the same technique as Manghoubi et al. 2022 for using Dyson Brownian motions to analyze the singular values and vectors of the perturbed matrix.

This paper provides new matrix perturbation bounds for the top singular vectors of a matrix A under Gaussian perturbations. The authors improve prior results in the setting when the matrix is much taller than it is wide (a common setting in data applications). Most of the reviewers (besides one outlier) felt that the work was interesting and addresses a fundamental question. There was a broad concern about fit to ICLR given the lack of applications -- the work might find a better home in a theory-focused conference. To their credit, the authors added a section during the rebuttal phase on an application to differential privacy (basically a direct corollary of their result is they can bound the accuracy of the top subspace of a data matrix perturbed using the common Gaussian mechanism. Nevertheless, on balance, this paper seems like a nice contribution to include in ICLR.

Accept (Poster)