PaperlayerView exact revision on arXiv

Source-linked AI summary

The singular values and vectors of low rank perturbations of large rectangular random matrices

Florent Benaych-Georges, Raj Rao Nadakuditi

arXiv:1103.2221v2math.PR

TL;DR

The paper asks how finite low-rank perturbations change extreme singular values and singular vectors of large rectangular random matrices. It analyzes these quantities through limiting noise-spectrum transforms and master equations, proving almost sure limits, a threshold phase transition, vector-projection behavior, and fluctuations around the limits.

  • Problem

    The paper addresses how to characterize estimated signal singular values and singular vectors when SVD is applied to large rectangular signal-plus-noise matrices.

  • Method

    The paper derives master-equation representations and applies concentration results to analyze low-rank perturbations using integral transforms of the noise singular-value distribution.

  • Results

    Above a critical threshold, perturbation singular values move extreme singular values to equation-defined positions; below it, the extreme singular values do not move significantly, with corresponding vector and fluctuation results.

  • Takeaways & Limitations

    The asymptotic behavior of perturbed singular values and vectors is determined by the noise spectrum through rectangular free-probability transforms, extending beyond Gaussian settings.

  • Takeaways & Limitations

    The analysis assumes singular-value spacings with random-matrix-like repulsion rather than independent-sample-like clumping.

Abstract

from arXiv · show

In this paper, we consider the singular values and singular vectors of finite, low rank perturbations of large rectangular random matrices. Specifically, we prove almost sure convergence of the extreme singular values and appropriate projections of the corresponding singular vectors of the perturbed matrix. As in the prequel, where we considered the eigenvalue aspect of the problem, the non-random limiting value is shown to depend explicitly on the limiting singular value distribution of the unperturbed matrix via an integral transforms that linearizes rectangular additive convolution in free probability theory. The large matrix limit of the extreme singular values of the perturbed matrix differs from that of the original matrix if and only if the singular values of the perturbing matrix are above a certain critical threshold which depends on this same aforementioned integral transform. We examine the consequence of this singular value phase transition on the associated left and right singular eigenvectors and discuss the finite $n$ fluctuations above these non-random limits.

1. Introduction

The paper studies low-rank signal-plus-noise rectangular matrices in high dimensions, characterizing how perturbations affect extreme singular values and associated singular vectors. It identifies a singular-value phase transition governed by integral transforms of the noise spectrum and develops master-equation and concentration methods for the analysis.

  • Motivation: Signal-plus-noise matrices model data or measurements across signal processing, statistics, and machine learning applications.The model combines signal singular values and left/right signal vectors with a random noise-only matrix.
  • Motivation: The paper studies large n and m settings where SVD-based estimates target signal singular values, signal subspaces, and associated singular vectors.The largest singular values and vectors also provide principal components and best rank-r approximations under unitarily invariant norms.
  • Main results: In the large-matrix limit, extreme singular values depend on integral transforms of the noise singular-value distribution and undergo a BBP phase transition at a critical value.The critical value is linked to rectangular free probability, and fluctuations around the asymptotic limits are also characterized.
  • Scope and connections: The results allow broad noise distributions, recover Gaussian eigenvalue and eigenvector results, and provide new right-singular-vector results in the Gaussian setting.The same general principle is intended to extend beyond Gaussian noise, with expressions also supporting a parameter-estimation algorithm.
  • Main results: Perturbation singular values above the threshold can move extreme singular values to solutions of implicit equations, whereas below-threshold values leave them essentially unchanged.The paper also analyzes the corresponding left and right singular vectors and finite-size fluctuations.
  • Proof strategy: The proofs derive master-equation representations for perturbed singular values and vectors and use concentration results to obtain analytical expressions.The strategy follows related finite-rank Hermitian perturbation work while emphasizing the rectangular singular-value setting.

2. Main results

The paper studies extreme singular values and singular vectors of finite-rank perturbations of large rectangular random matrices. Under stated distributional and asymptotic assumptions, it establishes phase transitions governed by integral transforms of the limiting noise singular-value distribution.

  • Assumptions: As n,m grow with n/m tending to c, the noise singular-value distribution converges almost surely to a compactly supported limit under the paper’s assumptions.The smallest and largest noise singular values are also assumed to converge to the support edges.
  • Model: The perturbed matrix is formed by adding a finite-rank random perturbation whose signal vectors arise either from i.i.d. columns or their Gram-Schmidt orthonormalization.In the orthonormalized model, the perturbation’s nonzero singular values are the prescribed θi values.
  • Largest singular values: The r largest perturbed singular values separate from the noise edge according to equations involving an integral transform of the limiting singular-value distribution, while non-outlier singular values retain the edge behavior.The results apply for each fixed signal index and separately characterize indices beyond the perturbation rank.
  • Largest singular vectors: Signal singular vectors above the critical threshold have nonzero asymptotic projections onto their corresponding left and right signal vectors, while projections onto the other signal directions vanish.The theorem also identifies the limiting norms of these projections for both sides of the rectangular matrix.
  • Phase-transition conditions: The largest-singular-value phase transition occurs under edge-density decay exponent α = 1/2, and extensions require singular-value repulsion rather than independent-sample-like clumping.The paper notes that the additional spacing hypothesis is needed for generalization to singular values converging to the upper edge.
  • Smallest singular values and vectors: For square perturbed matrices, analogous phase transitions govern the smallest singular values and singular vectors, but the square restriction avoids technical difficulties from non-monotonicity when c < 1.The corresponding projection results hold for signal singular values above the relevant threshold.

3. Examples

The examples apply the general perturbation results to i.i.d. and Haar random matrices, relating isolated singular values and singular-vector transitions to the limiting noise spectrum.

  • i.i.d. model: For i.i.d. Gaussian matrices, the noise singular-value distribution converges to a limiting density as n,m grow with n/m→c.The extreme eigenvalues converge to the support endpoints of this limiting distribution.
  • i.i.d. model: For a fixed-rank perturbation with singular values θ1≥···≥θr, each fixed extreme singular value is characterized asymptotically through the perturbation strengths and the noise distribution.The formula recovers previously known i.i.d. results as a special case.
  • i.i.d. model: The associated left and right singular vectors undergo analogous phase transitions, with their limiting alignments determined by the same perturbation framework.The section explicitly turns from singular values to singular vectors after stating the value limits.
  • Haar model: For Haar unitary or orthogonal noise, all singular values equal one, so the limiting spectral measure is concentrated at one with support endpoints a=b=1.This gives a square-matrix example with c=1.
  • Haar model: For fixed-rank square perturbations of Haar noise, sufficiently strong perturbations produce isolated extreme singular values, while fixed indices beyond rank r remain at the unperturbed edge.The stated asymptotics distinguish the first r singular values from indices i≥r+1.

4. Proof of Theorems 2.8 and 2.13

The proof reduces perturbed extreme singular values to finite-dimensional random matrix singularity, then uses uniform convergence and continuity to identify their deterministic limits.

  • Proof strategy: The proof begins with Weyl interlacing and reduces the extreme-singular-value problem to a 2r×2r matrix through Lemma 4.1.The reduced matrix is singular precisely at candidate singular values of the perturbed matrix outside the original spectrum.
  • Proof strategy: The random matrix-valued function Mn(z) converges almost surely and uniformly to a deterministic matrix M(z).Analytic-function convergence is used to establish this uniform limit.
  • Proof strategy: Continuity transfers the singularity locations of Mn(z) to those of M(z), identifying the limiting outlier positions.The proof then relates singularity of M(z) to equations involving the D-transform.
  • Proof setup: The argument conditions on the noise matrices so that they may be treated as deterministic while randomness is supported by the perturbation matrix.This conditioning is used in the proof setup for the relevant convergence arguments.
  • Phase transition: When perturbation singular values are below threshold, the corresponding extreme singular values do not move significantly and converge to the noise edge.Interlacing also shows that fixed-rank singular values without limits above b tend to b.
  • Phase transition: For pairwise distinct perturbation singular values, the continuity lemma gives exactly the predicted isolated singular values, each with multiplicity one.Repeated perturbation values are handled by approximation.

5. Proof of Theorems 2.9 and 2.14

The singular-vector proofs use the same finite-dimensional reduction as the singular-value analysis, translating kernel convergence into asymptotic alignment with signal directions.

  • Kernel reduction: A singular pair of the perturbed matrix yields a vector in the kernel of the associated 2r×2r matrix Mn(z).Lemma 5.1 also supplies formulas used to recover the vector projections.
  • Kernel reduction: Uniform convergence of Mn(z) implies that the relevant finite-dimensional vector approaches the kernel of the deterministic limit matrix M(ρ).The orthogonal projection onto the complement of this kernel tends almost surely to zero.
  • Vector alignment: The limiting kernel calculation shows that estimated singular vectors have vanishing components along signal directions whose singular values differ from the selected perturbation value.This yields the stated projection relations for both left and right singular vectors.
  • Vector alignment: Almost-sure asymptotic orthonormality of the signal vectors reduces the remaining projection calculations to diagonal terms.Off-diagonal inner products vanish in the limit.

6. Proof of Theorems 2.10 and 2.15

For the rank-one case, the proof analyzes the reduced determinant near the noise edge to show when the largest perturbed singular value separates from it.

  • Rank-one analysis: For r=1, the proof studies the 2×2 reduced matrix Mn(z) associated with the largest singular value.The rank-one specialization makes the determinant analysis explicit.
  • Rank-one analysis: The determinant’s term involving z^2−b_n^2 controls whether the perturbed largest singular value lies above the largest noise singular value b_n.Here b_n denotes the largest singular value of Xn.
  • Rank-one analysis: With probability tending to one, the largest singular value of the perturbed matrix exceeds b_n.This establishes separation from the noise edge in the analyzed rank-one regime.
  • Rank-one analysis: The associated singular-vector conclusions then follow by applying the second part of Lemma 5.1.The proof reuses the kernel-to-projection mechanism from the singular-vector analysis.

7. Proof of Theorems 2.18 and 2.20

The proof reduces extreme singular-value and singular-vector statements to properties of the random matrix function M_n and derives their finite-n fluctuation laws. In the rank-one case, the leading singular-value fluctuation is identified through a Gaussian limit.

  • The proof specializes first to rank r = 1, writing u = u1 and v = v1 for the signal vectors.
  • The matrix M_n(z) is 2 × 2, and its determinant has exactly one zero above the spectral boundary for sufficiently large n.Its sign changes from positive below eσ1 to negative above eσ1.
  • The proof analyzes the limiting distributions of the entries of M_n to establish the fluctuation behavior of the extreme singular values.
  • The corresponding vector calculations use the relation ϕµX(ρ)ϕeµX(ρ) = θ−2 and show that the relevant projection error tends to zero.
  • n(eσ1 − ρ) converges weakly to sX, where X is a standard Gaussian random variable on R.

8. Appendix

The appendix supplies continuity and concentration tools used to localize extreme eigenvalues and control random-vector bilinear forms. A deterministic matrix-function lemma transfers noninvertibility structure from M to M_n.

  • A continuity lemma is used to localize the extreme eigenvalues of e Xn.
  • Under its analytic assumptions, M(z) has p noninvertibility points z1 > · · · > zp above b, corresponding to selected θi values.
  • Uniform convergence of M_n to M yields p roots zn,1 > · · · > zn,p converging to z1, . . . , zp.
  • For sufficiently large n, these are exactly the noninvertibility points of M_n above b + ε, and each associated matrix has rank 2r − 1.
  • A concentration proposition bounds deviations involving normalized traces and bilinear forms of the random vectors with exponentially small probability.The bound has the form Ce−nα.
Loading 1103.2221v2…