Source-linked AI summary
Random perturbation of low rank matrices: Improving classical bounds
Sean O'Rourke, Van Vu, Ke Wang
TL;DR
The paper asks how perturbations affect singular values and vectors, especially when data matrices are low rank. It develops sharper bounds for random perturbations and relates closeness of singular subspaces to approximation and, in some cases, recovery.
Problem
The paper studies how a perturbation changes singular values and vectors, quantities central to leading-component computation and low-rank approximation.
Source: §1 · p. 1, §1.1 · p. 2Method
It derives perturbation bounds for individual singular vectors and leading singular subspaces under concentrated-noise assumptions and low-rank structure.
Source: §2 · pp. 6, 8Results
The new results show the original and perturbed leading singular subspaces are close, and projecting the perturbed matrix onto its leading subspace can approximate the original matrix’s rank-j approximation.
Source: §2 · p. 8, §3 · p. 13Takeaways & Limitations
In certain cases, repeating the projection operation can provide enough information to recover A completely or estimate a required parameter with high accuracy and certainty.
Source: §3 · p. 13The factor √j in one bound is believed to be suboptimal and is attributed to the proof; precise recovery algorithms work only under certain structural assumptions on A.
Source: §2 · p. 9, §7 · p. 23
Abstract
from arXiv · showhide
Matrix perturbation inequalities, such as Weyl's theorem (concerning the singular values) and the Davis-Kahan theorem (concerning the singular vectors), play essential roles in quantitative science; in particular, these bounds have found application in data analysis as well as related areas of engineering and computer science. In many situations, the perturbation is assumed to be random, and the original matrix has certain structural properties (such as having low rank). We show that, in this scenario, classical perturbation results, such as Weyl and Davis-Kahan, can be improved significantly. We believe many of our new bounds are close to optimal and also discuss some applications.
1. Introduction
The paper studies how perturbations affect singular values and vectors, a problem central to computing leading components and low-rank approximations. It argues that classical bounds can be sharpened when the data matrix is low rank and the perturbation is random.
1. Introduction
- Computing leading singular values and vectors is central to PCA and low-rank approximation, especially when matrix dimensions are large and the target rank is small.The paper frames perturbation of these quantities as its main problem.Source: §1 · p. 1, §1.1 · p. 2
1.1. The perturbation problem.
- For the leading singular vector, the modified sine bound is at most 2∥E∥/δ and is sharp up to the constant 2.When δ > 2∥E∥, the perturbed leading vector is uniquely determined up to sign.Source: §1.1 · pp. 2–3
1.2. The random setting.
- When A has rank r much smaller than n, the Bernoulli-noise bounds improve on the classical bound, with √r replacing √n in the stated bounds.The authors say their strongest results require neither independent entries nor the Bernoulli-only assumptions used to state Theorems 9 and 10.Source: §1.2 · p. 5
1.3. Preliminaries: Models of random noise.
- The concentration framework is closed under addition and gives a high-probability spectral-norm bound for E.The norm bound has scale C′n^(1/γ), with constants depending on the concentration parameters.Source: §1.3 · p. 6
2. Main results
For low-rank data matrices, the paper develops improved perturbation bounds for singular vectors and singular spaces, with dimension dependence tied to rank rather than ambient dimension. It also extends these bounds to selected singular-value intervals and discusses their sharpness and relation to prior work.
2. Main results
- For rank-one A with Wigner perturbation E, results in match the bound in (5) up to constant factors; gives the same match under technical assumptions.The paper says the bounds in (5) match the exact asymptotic behavior of the dot product studied in, up to constant factors.Source: §2 · pp. 7–8
- The results extend to angles between individual singular vectors and to subspaces spanned by the first j singular vectors, which are used in low-rank approximation.The paper also states that bounds for subspace angles may have many applications.Source: §2 · p. 8
- Applying Theorem 18 twice yields a bound for subspaces spanned by singular vectors indexed by an interval, though an optimal bound for arbitrary index sets remains open.The result is stated for indices j through l.Source: §2 · p. 9
- Theorem 22's recursive bound depends on earlier vector-angle bounds, is not believed sharp, and nevertheless improves a similar bound in.The authors identify its inductive dependence on bounds for indices i < j as the reason they do not believe it is sharp.Source: §2 · p. 10
- When r = O(1) and E is Wigner, the bounds in Theorem 23 are sharp up to constant factors, according to exact asymptotic results in [44].The cited results give the asymptotic location and joint fluctuations of the largest r eigenvalues.Source: §2 · p. 11
2.1. Related results.
- Related work includes Gaussian-entry singular-vector estimates, eigenvector dynamics under symmetric Brownian perturbations [2], and spiked covariance studies [12] [26] [41].The authors suggest finding a common generalization for these problems would be interesting.Source: §2.1 · p. 12
3. Overview and outline
The overview sketches how concentration of the random perturbation helps control singular-vector changes, and outlines extensions to subspaces and matrix recovery. It also describes the symmetrization used to connect singular-vector bounds to eigenvector bounds.
3. Overview and outline
- The proof controls singular-vector changes by bounding perturbation terms and gaps between perturbed and unperturbed eigenvalues using concentration.For the leading eigenvalue, the outline first uses a lower bound on the perturbed eigenvalue, then relates its gap from the second eigenvalue to the original gap.Source: §3 · p. 12
- In Section 5, the authors apply the concentration property to upper-bound terms of the form vkEv′j, then combine these bounds to complete proofs of Theorems 14, 18, 22, and 23.Source: §3 · p. 12
- The results extend to angles between indexed singular vectors and between subspaces spanned by the first j singular vectors.The section notes that these leading singular-vector subspaces are relevant to low-rank approximation.Source: §3 · p. 13
- For matrix recovery, projecting the noisy observation onto its leading j-dimensional singular subspace can approximate the corresponding rank-j approximation of the unknown matrix.The outline adds that repeated projection may recover the matrix or estimate a required parameter in certain cases.Source: §3 · p. 13
4. Preliminary tools
The preliminary tools transform the rectangular singular-vector problem into a symmetric eigenvector problem and transfer concentration to that formulation. They then use concentration bounds and sphere nets to control perturbations on low-rank subspaces.
4. Preliminary tools
- A symmetric block-matrix transformation encodes the singular values as eigenvalues and the left and right singular vectors as eigenvectors, allowing the proofs to work with eigenvector bounds.The section states that the transformed matrices suffice for proving Theorems 14, 18, 22, and 23.Source: §4 · p. 13
- The transformation preserves the concentration property, with adjusted constants, so concentration estimates for E also apply to its symmetric counterpart.The stated constants are ˜C1 = 2C1 and ˜c1 = c1/2^γ.Source: §4 · p. 14
- Sphere nets discretize the unit sphere and support concentration-based bounds for perturbations restricted to subspaces associated with a rank-r matrix.The section introduces ε-nets and derives further lemmas from the concentration property.Source: §4 · p. 15
- The resulting lemmas bound perturbation behavior for individual singular directions and for the leading j-dimensional subspace.The subspace bound is obtained using the Courant minimax principle.Source: §4 · pp. 15–16
5. Proof of Theorems 14, 18, 22, and 23
The proofs use concentration-derived events and bounds in the symmetric formulation to establish the paper’s singular-vector and subspace perturbation results. They translate these estimates back to the original singular-vector setting.
5. Proof of Theorems 14, 18, 22, and 23
- This section proves Theorems 14, 18, 22, and 23; for Theorems 14 and 22, Proposition 26 reduces the task to bounding sin ∠(uj, vj), with uj and vj formed from singular vectors of A and A + E.Source: §5 · pp. 17, 19
- In the proof of Theorem 14, applying bounds from Lemmas 32 and 33 with j = 1 yields a bound; its correct absolute constant follows from that bound and Proposition 26.The lower bound on probability in (30) is written using C1, c1, γ by recalling the definitions of ˜C1 and ˜c1 in Lemma 27.Source: §5 · p. 19
- The proof of Theorem 22 combines its bounds with earlier individual-vector angle estimates, which depend on angles for preceding indices.The accompanying note explains that the proof can instead track only left or only right singular-vector coordinates to avoid dependence on both sides.Source: §5 · pp. 19–20
- Theorem 18 treats the angle between the subspaces spanned by the first j transformed eigenvectors, using the bounds from Lemmas 32 and 33.The proof defines the two subspaces as spans of the first j eigenvectors before bounding their angle.Source: §5 · p. 20
6. The concentration property
The section gives examples of random perturbations satisfying the concentration property, including independent-entry models and models without independent entries. It also points to Gaussian and sub-exponential examples.
6. The concentration property
- Bernoulli perturbations satisfy stated concentration bounds, and the section says those bounds also hold for Gaussian noise.For Gaussian entries, the text explains that u^T E v is standard normal for fixed unit vectors u and v.Source: §6 · p. 21
- For independent mean-zero entries bounded almost surely by K, Hoeffding’s inequality is used to obtain a concentration bound for fixed unit vectors.The proof represents the bilinear form as a sum of independent random variables.Source: §6 · p. 22
- Independent entries with rapidly decaying tails yield concentration after standard truncation; iid sub-exponential entries provide an example.The cited example assumes mean zero and variance one.Source: §6 · pp. 22–23
- Entry independence is not necessary for the concentration property; random orthogonal matrices and elliptic ensembles are cited as examples.The text points to standard truncation and concentration results for the elliptic-ensemble example.Source: §6 · p. 23
7. An application: The matrix recovery problem
The section applies the paper’s results to recovery from partially observed noisy matrices. It highlights high-probability approximation of a specified row or column, rather than only average whole-matrix accuracy.
7. An application: The matrix recovery problem
- The recovery setting observes each entry of a noisy matrix with probability p and treats unobserved entries as zero; the goal is to reconstruct the low-rank matrix.The matrix is large and unknown, and the observation may be only a noisy image or a small part of it.Source: §7 · p. 23
- The analysis provides high-probability approximation of any specified column or row, including an individual viewer’s ratings or a particular movie’s ratings in the Netflix example.The authors contrast this with earlier Frobenius-norm guarantees, which do not guarantee accuracy for a specific row or column.Source: §7 · p. 23
- Earlier Frobenius-norm approximation guarantees do not ensure accuracy for a particular row or column, while exact-recovery algorithms cited here require structural assumptions on A.The cited exact-recovery algorithms are associated with [11, 14, 15, 16, 17].Source: §7 · p. 23
- Theorem 39 considers an arbitrary column and the subspace spanned by the first j singular vectors, under rank, bounded-noise, concentration, and singular-value-gap assumptions.It specifies a bounded-entry noise matrix Z and a gap δ_j = σ_j − σ_{j+1}; the supplied theorem passage does not include the bound itself.Source: §7 · pp. 23, 25