Research map / Learning theory and algorithms / Matrix and tensor methods
Singular Subspace Perturbation Bounds via Rectangular Random Matrix Diffusions
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Derives expected Frobenius bounds on how the top-k right singular subspace (and rank-k covariance approximation) of a matrix changes under iid Gaussian noise, by viewing the perturbation as a Dyson-Bessel diffusion and applying Ito's lemma.
Problem
Bounding the perturbation of top-k right singular subspaces and low-rank covariance approximations when a rectangular data matrix A is corrupted by iid Gaussian noise N(0,T), with prior bounds scaling with the number of rows m rather than columns d.
Approach
Treats the Gaussian perturbation as matrix Brownian motion inducing a Dyson-Bessel diffusion on singular values and vectors, then tracks the Frobenius distance of the projected orbit element via Ito's lemma, yielding bounds in terms of singular gaps with d instead of m.
Key results
- Under singular value gap assumption, E||V_k V_k^T - Vhat_k Vhat_k^T||_F = O(sqrt(kd)/(sigma_k - sigma_{k+1}) sqrt(T)), improving by roughly sqrt(m/d) sqrt(k) over Davis-Kahan-based bounds.
- With gaps Omega(sigma_k - sigma_{k+1}) for all i<=k, the bound improves to O(sqrt(d)/(sigma_k - sigma_{k+1}) sqrt(T)).
- The general theorem gives E||Vhat Gamma^T Gamma Vhat^T - V Gamma^T Gamma V^T||_F^2 = O(sum_{i<=k} sum_{j>i} (gamma_i^2-gamma_j^2)^2/(sigma_i-sigma_j)^2) T.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add the proposed Gaussian-noise perturbation bound under the stated singular-gap assumption | Top-k right singular subspace recovery · Top-k right singular subspace recovery | expected Frobenius distance: O\left(\dfrac{\sqrt{kd}}{(\sigma_k - \sigma_{k+1})}\right)\sqrt{T} versus O(\dfrac{\sqrt{km}}{\sigma_k - \sigma_{k+1}} \ | Helped |
| Use the proposed bound when all top-k successive gaps are at least on the order of the kth gap | Top-k right singular subspace recovery · Top-k right singular subspace recovery with comparable top-k gaps | expected Frobenius distance: O\left(\dfrac{\sqrt{d}}{(\sigma_k - \sigma_{k+1})}\right)\sqrt{T} versus O(\dfrac{\sqrt{km}}{\sigma_k - \sigma_{k+1}} \s | Helped |
| Use the proposed bound instead of the Davis-Kahan-Wedin bound | Top-k right singular subspace recovery · Top-k right singular subspace recovery with comparable top-k gaps | expected Frobenius distance: \sqrt{k} \frac{\sqrt{m}}{\sqrt{d}} | Helped |
| Use the proposed bound instead of Theorem 18 of prior work when the kth gap is on the order of the kth singular value | Top-k right singular subspace recovery · Top-k right singular subspace recovery | expected Frobenius distance: \sqrt{k}\frac{\sqrt{m}}{\sqrt{d}} | Helped |
| Add the proposed Gaussian-noise covariance approximation bound | Rank-k covariance matrix approximation · Rank-k covariance matrix approximation | expected Frobenius distance: \frac{\sqrt{m}}{\sqrt{d}} | Helped |
| Use the proposed covariance bound instead of the Davis-Kahan-Wedin bound when the kth gap is on the order of the kth singular value | Rank-k covariance matrix approximation · Rank-k covariance matrix approximation | expected Frobenius distance: \frac{\sqrt{m}}{\sqrt{d}}k | Helped |
| Use the proposed covariance bound instead of Theorem 18 of prior work | Rank-k covariance matrix approximation · Rank-k covariance matrix approximation | expected Frobenius distance: \frac{\sqrt{m}}{\sqrt{d}} \sqrt{k} | Helped |
| Apply the bound in the full-rank special case k=d | Rank-k covariance matrix approximation · Full-rank covariance approximation (k=d) | Frobenius distance: \Theta(\|\Sigma_d\|_F \sqrt{d} \sqrt{T}) | No clear effect |
Surprising findings
- In the full-rank case k=d the Frobenius bound is shown to be tight up to constants, matching Theta(||Sigma_d||_F sqrt(d) sqrt(T)).
Limitations
- Requires top-k singular value gaps of order Omega(sqrt(m) sqrt(T)) (Assumption on gaps with log(1/delta) factor), which may fail in some settings.
- Results only apply to Gaussian perturbations, not other random matrix distributions.
- Bounds hold in expectation rather than with high probability for the subspace result.
Experimental setup
Metrics: expected Frobenius distance between singular subspaces
Baselines: Davis-Kahan-Wedin sin-theta theorem bound Theorem 18 bound from prior work on Gaussian mechanism covariance approximation
Builds on: Davis-Kahan-Wedin sin-theta theorem Ito's lemma Weyl's inequality Dyson-Bessel process
Closest papers by meaning
- Spectral Perturbation Bounds for Low-Rank Approximation with Applications to Privacy (NeurIPS 2025 · similarity 0.86)
- Nearly $d$-Linear Convergence Bounds for Diffusion Models via Stochastic Localization (ICLR 2024 · similarity 0.84)
- How Accurately Can a Gaussian Approximate Stochastic Approximation Iterates? (NeurIPS 2026 · similarity 0.84)
- Entrywise error bounds for low-rank approximations of kernel matrices (NeurIPS 2024 · similarity 0.84)
- An Iterative Algorithm for Differentially Private $k$-PCA with Adaptive Noise (NeurIPS 2025 · similarity 0.83)
- On Differentially Private Subspace Estimation in a Distribution-Free Setting (NeurIPS 2024 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.