PaperlayerView exact revision on arXiv

Source-linked AI summary

Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions

Nathan Halko, Per-Gunnar Martinsson, Joel A. Tropp

arXiv:0909.4061v2math.NAmath.PR

TL;DR

Classical matrix decomposition algorithms can be inadequate for modern computational demands. The paper develops randomized, modular approximation methods and finds them often faster, more robust, and highly accurate, with failure probability made negligible at modest cost.

  • Problem

    Classical matrix decomposition algorithms are inadequate in some situations arising from new hardware and information-science applications, while useful low-dimensional subspaces remain difficult to identify compactly.

  • Method

    The framework preprocesses a matrix, takes random linear samples, and postprocesses them with classical numerical linear algebra techniques to form an approximation.

  • Results

    Randomized algorithms are often faster and more robust than deterministic methods, while achieving highly accurate results with failure probability below 10^-15 at nominal resource cost.

  • Takeaways & Limitations

    Randomized methods provide effective modern algorithms for approximate matrix factorizations and can help practitioners identify cases where they outperform established methods.

  • Takeaways & Limitations

    Row-extraction postprocessing is fast but usually has larger error than the initial subspace approximation, especially for large matrices.

Abstract

from arXiv · show

Low-rank matrix approximations, such as the truncated singular value decomposition and the rank-revealing QR decomposition, play a central role in data analysis and scientific computing. This work surveys and extends recent research which demonstrates that randomization offers a powerful tool for performing low-rank matrix approximation. These techniques exploit modern computational architectures more fully than classical methods and open the possibility of dealing with truly massive data sets. This paper presents a modular framework for constructing randomized algorithms that compute partial matrix decompositions. These methods use random sampling to identify a subspace that captures most of the action of a matrix. The input matrix is then compressed---either explicitly or implicitly---to this subspace, and the reduced matrix is manipulated deterministically to obtain the desired low-rank factorization. In many cases, this approach beats its classical competitors in terms of accuracy, speed, and robustness. These claims are supported by extensive numerical experiments and a detailed error analysis.

1. Overview. … 1.3. Randomized algorithms.

The paper presents randomized methods for approximate low-rank matrix factorizations, motivated by massive or imprecise data and organized around sampling a useful subspace before deterministic factorization. Its framework addresses fixed-rank and fixed-precision problems through oversampling, incremental error estimation, and efficient reduced computations.

  • 1. Overview.: Classical matrix-decomposition algorithms can be inadequate for massive modern datasets and data that are missing or inaccurate.These limitations motivate methods that avoid unnecessary computational effort while retaining useful approximations.
  • 1. Overview.: Randomized algorithms often provide faster, more robust approximate factorizations with user-selectable accuracy above machine precision.The paper develops these methods alongside classical techniques and supports them with theoretical guarantees.
  • 1.1. Approximation by low-rank matrices.: A low-rank approximation A ≈ B C uses a small inner dimension k to reduce storage, accelerate matrix-vector products, and support data analysis or least-squares problems.Here k is called the numerical rank when it is much smaller than m and n.
  • 1.2. Matrix approximation framework.: The approximation framework first constructs a low-dimensional subspace capturing A’s action, then restricts A to that subspace and factors the reduced matrix deterministically.Stage A uses random sampling, while Stage B uses established QR, SVD, or related methods.
  • 1.3.1. Problem formulations.: The fixed-precision problem seeks an orthonormal basis Q with the smallest dimension that approximates A within a prescribed tolerance.The range of Q should capture most of A’s action while keeping its dimension as small as possible.
  • 1.3.1. Problem formulations.: For fixed-rank approximation, adding a small oversampling parameter provides flexibility crucial to the effectiveness of randomized methods, while incremental construction can estimate residual error.This connects fixed-rank algorithms to fixed-precision approximation.
  • 1.3.2. Intuition.: Random samples of A are likely to span the desired range, and oversampling improves coverage under perturbations; failure probability can decrease superexponentially with p.In practice, p = 5 or p = 10 often gives superb results.

1.4. A comparison between randomized and traditional techniques. … 1.7. Outline of paper.

The paper compares randomized low-rank approximation with deterministic and Krylov methods, then develops error guarantees, a power-iterated randomized SVD, and an outline of the paper’s organization. Across these sections, randomized methods are presented as computationally efficient, stable, and accurate under stated conditions.

  • 1.4.1. A general dense matrix that fits in fast memory.: Randomized SVD reduces the dense-matrix cost to O(mn log(k) + (m + n)k2) flops, versus O(kmn) for rank-revealing QR.The speedup uses structured random matrices to evaluate AΩ rapidly.
  • 1.4.2. A matrix for which matrix–vector products can be evaluated rapidly.: For matrices with rapid matrix–vector products, randomized and Krylov methods have comparable cost, while randomized schemes offer stability and guarantees independent of subtle spectral properties.Krylov methods can sometimes be more accurate for a fixed flop budget.
  • 1.4.3. A general dense matrix stored in slow memory or streamed.: For out-of-core or streamed matrices, standard methods may require O(k) passes, whereas randomized schemes can use one pass, a few additional passes, or modifications enabling a single pass.The basic one-pass approach may need 2 to 4 additional passes when the singular spectrum decays slowly.
  • 1.5. Performance analysis.: The performance analysis derives precise error bounds in terms of singular values and studies how choices of the random matrix Ω affect the algorithm.For Gaussian test matrices, the theorem analyzes average-case behavior under exact arithmetic.
  • 1.5. Performance analysis.: The expected approximation error is within a small polynomial factor of the theoretical minimum σk+1, with a bound slightly sharper than comparable rank-revealing QR bounds.Measure concentration makes the actual error close to the typical outcome, and the stated probability is at least 1 −6 · p−p under mild assumptions.
  • 1.6. Example: Randomized SVD.: Power iteration addresses slowly decaying singular spectra, and q = 1 or q = 2 usually suffices in practice for the randomized SVD.The procedure requires only 2(q + 1) passes over the matrix, while its leading error-bound constant approaches one exponentially fast as q increases.
  • 1.7. Outline of paper.: The paper is organized into an introduction, algorithm descriptions, and theoretical performance analysis, with the latter two parts beginning with internal outlines.Each part is intended to be more or less self-contained.

2. Related work and historical context.

Randomized matrix approximation emerged from earlier probabilistic methods and recently incorporated ideas from random matrix theory into classical factorization algorithms. Related approaches sample or project the matrix, then use deterministic numerical linear algebra to construct approximations.

  • Historical development: Sophisticated random matrix theory entered classical matrix factorization only recently, building on earlier work in computer science and probabilistic methods.
  • General framework: The common randomized pattern preprocesses the matrix, takes random linear samples, and postprocesses them with classical numerical linear algebra.
  • Column sampling: Column-selection methods exploit the fact that a small set of columns can describe most of a numerically low-rank matrix, although optimizing natural objectives is NP-hard.
  • Column sampling: Randomized column methods sample according to column norms or leverage scores, then form approximations from the sampled submatrix, often using a truncated SVD or rank-revealing QR.
  • Dimension reduction: Dimension-reduction methods use random linear maps to embed low-rank matrix rows into lower-dimensional spaces, an approach motivated by the volume and processing speed of modern data.

3. Linear algebraic preliminaries.

This section introduces notation, standard matrix decompositions, and classical methods for computing partial factorizations. For numerically low-rank matrices, these methods produce accurate structured approximations but can require costly matrix access and computation.

  • Motivation: For a matrix with numerical rank k substantially below its dimensions, partial decompositions can approximate it well and motivate randomized methods.Sections 4 and 5 develop randomized techniques, while this section reviews the classical approaches.
  • Classical partial QR: Businger–Golub pivoted QR halts when the residual column Frobenius norm falls below ε, producing Q, R, and E with ∥E∥F ≤ ε at cost O(ℓmn).The step count ℓ is typically close to the minimal rank needed to achieve precision ε in the Frobenius norm, although rank overprediction is possible.
  • Classical partial QR: The Gu–Eisenstat rank-revealing QR algorithm typically costs O(kmn), can be slightly more expensive rarely, and can also produce an approximate interpolative decomposition.It succeeds for all matrices, and σk+1 is the minimal rank-k approximation error.
  • Classical partial SVD: A truncated full SVD costs O(mn min{m, n}) flops, whereas partial QR postprocessing and Krylov methods compute partial SVDs at comparable O(kmn) cost.The full SVD approach is stable and accurate; Krylov implementations require stabilization techniques and have complex costs.
  • Postprocessing: Given a rank-k partial decomposition, QR postprocessing yields orthonormal Q and weakly upper-triangular R satisfying ∥A − QR∥ ≤ ε.The construction factors C, QR-factorizes R1B, and forms Q = Q1Q2.
  • Postprocessing: The analogous SVD postprocessing produces diagonal Σ and orthonormal U and V satisfying ∥A − UΣV∗∥ ≤ ε.It QR-factorizes C, computes an SVD of R1B, and forms U = Q1U2.

4. Stage A: Randomized schemes for approximating the range.

Stage A uses randomized sampling to construct a low-dimensional orthonormal basis approximating the range of a matrix, then improves the basic scheme for unknown rank, slowly decaying spectra, and faster structured transforms. Gaussian sampling typically needs only modest oversampling, while power iteration improves accuracy at additional multiplication cost.

  • Basic randomized range finder: Algorithm 4.1 draws an n × ℓ Gaussian matrix Ω, forms Y = AΩ, and orthonormalizes its columns to obtain an m × ℓ basis Q.Q is constructed as an orthonormal basis for the range of Y, for example through the QR factorization Y = QR.
  • Oversampling: For Gaussian test matrices, a small constant oversampling parameter such as p = 5 or p = 10 is usually adequate and adds negligible computation.There is rarely any advantage to selecting p > k.
  • Adaptive sampling: Adaptive implementations increase the number of samples until the approximation error reaches the desired tolerance, so users do not choose the oversampling parameter directly.This approach addresses the common case where the target rank k is unknown in advance.
  • Accuracy enhancement: Power iteration requires 2q + 1 times as many matrix–vector multiplies as Algorithm 4.1 but is far more accurate when singular values decay slowly.Its heuristic error factor is C1/(2q+1) when the original scheme is within a factor C of optimal.
  • Accuracy enhancement: In floating-point arithmetic, power iteration can lose information from small singular modes, but orthonormalizing between applications of A and A∗ remedies the problem.Modes with singular values smaller than roughly µ1/(2q+1)∥A∥ may be lost when machine precision is µ.
  • Structured random transforms: Structured random transforms can identify near-optimal bases with ℓ∼(k + log(n)) log(k) samples, although their oversampling requirements and behavior are not fully understood.In practice, some transforms typically require no more oversampling than a Gaussian matrix.

5. Stage B: Construction of standard factorizations.

Stage B converts the sampled subspace basis Q into standard factorizations, chiefly by either forming B = Q∗A directly or avoiding matrix–matrix products through row extraction. The direct approach preserves the approximation error, while row extraction is faster but can lose accuracy.

  • Direct postprocessing: When ∥A−QB∥≤ε with B=Q∗A, standard factorizations such as an approximate SVD can be constructed without degrading the approximation error.Algorithm 5.1 computes B directly and then applies deterministic postprocessing.
  • Direct postprocessing: The direct SVD scheme is dominated by Q∗A, costing O(kmn) flops for a general dense matrix, while later steps cost O(k2n) and O(k2m) flops.Its matrix–matrix product can be accelerated with BLAS3 and parallel processors, and it is well suited to sparse or structured matrices.
  • Rank truncation: If Q exceeds the desired SVD rank, truncating to the dominant k singular values can increase the approximation error by σk+1 in the worst case.The untruncated approximate SVD has the same rank as Q.
  • Row extraction: Row extraction avoids matrix–matrix products and requires O(k2(m+n)) flops, but its approximation error is usually larger than the initial error ∥A−QQ∗A∥.Algorithm 5.2 is therefore faster than Algorithm 5.1 but less accurate, especially when ε is not small or kn is large.
  • Hermitian and positive-semidefinite matrices: For Hermitian matrices, direct eigenvalue postprocessing satisfies ∥A−UΛU∗∥≤2ε and costs O(kn2) flops, while the positive-semidefinite Nyström method never exceeds ∥A−QQ∗A∥ in spectral-norm error.The Nyström method has roughly the same running time as the Hermitian scheme and is typically much more accurate.

6. Computational costs.

The computational cost of randomized matrix approximation depends on how the matrix is accessed: dense methods scale with matrix dimensions, fast multiplies replace dense costs for sparse or structured matrices, and pass-efficiency matters when data exceeds fast memory. Randomized schemes can also reduce data passes and simplify robust partial spectral decomposition by reducing it to a small dense problem.

  • Dense matrices: For dense m × n matrices, the randomized method costs Trandom ∼mn log(k) + k2(m + n) flops.Stage A uses a structured random matrix, while Stage B uses row extraction.
  • Dense matrices: The randomized dense method can be several times faster than classical techniques for moderate sizes, including m, n ∼103 and k ∼102.If row extraction is impractical, an alternative O(mn log(k)) technique is available; using the direct Stage B method instead raises the total cost to O(kmn) flops.
  • Fast matrix multiplies: When A and A∗ admit fast multiplies, the sparse or structured approach costs Tsparse = 2 (k + p) Tmult + O(k2(m + n)).Here Tmult can be substantially smaller than the dense O(mn) cost, and O(m + n) flops may suffice for a matrix–vector multiplication.
  • Fast matrix multiplies: For slowly decaying singular spectra, q power iterations improve fixed-rank solutions but increase the cost to Tsparse = (2q + 2) (k + p) Tmult + O(k2(m + n)).The power scheme can also be adapted to fixed-precision problems.
  • Numerical robustness: Randomized sampling reduces partial spectral decomposition of a very large matrix to a full decomposition of a small dense matrix, making the final computation suitable for canned routines.The large matrix is accessed through matrix operations, while the reduced dense problem is better understood and easier to implement robustly.
  • Pass-efficiency: For many matrices, randomized techniques achieve accurate approximations with just one pass over the data, whereas classical techniques require at least k passes.When singular spectra decay slowly, power schemes increase the pass count, but typically require no more than five passes.

7. Numerical examples.

The numerical examples test randomized matrix approximation across physical-science operators, data-mining matrices, and structured random matrices. They show near-optimal accuracy for rapidly decaying spectra, rapid improvement from power iterations for slowly decaying spectra, and substantial speedups from SRFT-based methods.

  • Experimental scope: The experiments cover physical-science operators with rapidly decaying spectra, slowly decaying data-mining matrices, and algorithms based on structured random matrices.Sections 7.1–7.3 isolate the performance of the randomized Stage A step.
  • Adaptive range approximation: Algorithm 4.2 achieves approximation errors remarkably close to the theoretical minimum for matrices with rapidly decaying singular values.Across 2000 independent trials, actual and estimated errors concentrate about their mean values, while the estimator remains an upper bound.
  • Adaptive range approximation: For the 1596 × 532 implicitly accessed resistor-network matrix, Algorithm 4.2 shows qualitative performance matching the explicit-matrix experiments.Each matrix-vector application requires solving a sparse linear system of roughly 140 000×140 000.
  • Power schemes: For slowly decaying spectra, increasing the power-scheme exponent q produces a tremendous improvement over the basic q = 0 method.In the eigenvalue approximation experiment, the minimal exponent q = 0 produces miserable results, whereas larger exponents improve the spectrum estimates.
  • Structured random matrices: Structured random matrices yield fast and accurate approximations; SRFTs often provide dramatic speedups, while Gaussian test matrices typically provide moderate speedups over classical methods.The SRFT performs slightly better than a Gaussian random matrix in one error experiment, and standard and modified SRFTs have essentially identical errors.

8. Theoretical preliminaries.

This section develops linear-algebraic preliminaries on positive-semidefinite matrices and orthogonal projectors. It establishes ordering, conjugation, spectral, range, and norm properties used in subsequent arguments.

  • Positive-semidefinite matrices: Positive-semidefinite matrices are Hermitian matrices satisfying u∗Mu ≥ 0 for every nonzero u, while positive-definite matrices require strict inequalities.The psd matrices form a convex cone and induce the order M ≼ N exactly when N − M is psd.
  • Positive-semidefinite matrices: A psd matrix is characterized by nonnegative eigenvalues, is diagonalizable, and has a spectral norm given by a variational characterization.The inverse of a positive-definite matrix is also positive definite.
  • Positive-semidefinite matrices: Conjugation preserves positive semidefiniteness: M ≽ 0 implies A∗MA ≽ 0, and it preserves the order M ≼ N under the same transformation.This rule is repeatedly used to derive matrix inequalities, including perturbation bounds for inverses.
  • Orthogonal projectors: An orthogonal projector is Hermitian and idempotent, satisfies 0 ≼ P ≼ I, and is uniquely determined by its range; I − P projects onto the complementary subspace.For full-column-rank M, the projector onto range(M) has an explicit matrix expression.
  • Orthogonal projectors: If range(N) ⊂ range(M), projecting through M cannot increase spectral norms, while the complementary projection through M cannot decrease them.The section also establishes unitary covariance of projectors and a power-norm inequality for orthogonal projectors.

9. Error bounds via linear algebra.

This section develops a deterministic error analysis for the proto-algorithm and shows how its accuracy depends on the test matrix, singular spectrum, and power-scheme preprocessing. Theorem 9.1 sharpens an earlier bound, while Theorem 9.2 explains why increasing the power improves the estimate exponentially.

  • Deterministic error bound: Theorem 9.1 bounds the approximation error when Ω1 has full row rank, using either the spectral norm or the Frobenius norm.The bound depends on the interaction between the test matrix and the right singular vectors, as well as on the singular spectrum of A.
  • Deterministic error bound: Theorem 9.1 sharpens an earlier literature bound by including squares, yielding slightly better error estimates and consequences for randomized test matrices.The proof uses ideas from perturbation theory of orthogonal projectors.
  • Spectral dependence: Accuracy depends strongly on the distribution of A’s singular-value mass: dominance by large singular values makes a good low-rank basis easier to identify, while substantial small-singular-value mass can reduce accuracy.The relevant blocks are Σ1Ω1 for the gross behavior of A and Σ2Ω2 for a perturbation.
  • Power scheme: The power scheme applies the proto-algorithm to B = (A* A)^qA, whose singular values decay more rapidly before sampling.The resulting basis approximates the original matrix A within the range of the sampled matrix.
  • Power scheme: Increasing the power q drives down the suboptimality of the error bound exponentially fast, though larger q increases the algorithm’s cost.The extra factor can in principle be made arbitrarily close to one.

10. Gaussian test matrices.

Gaussian test matrices provide rotational invariance and random-matrix estimates that support precise expected-error and deviation analyses for randomized low-rank approximation. The resulting bounds characterize how oversampling and power iterations affect Frobenius- and spectral-norm accuracy.

  • Gaussian test matrices: Standard Gaussian matrices have independent standard normal entries and a rotationally invariant distribution.If U and V are orthonormal, then U∗GV remains standard Gaussian.
  • Gaussian test matrices: Gaussian matrix norm, pseudoinverse, concentration, and large-deviation results underpin the analysis of randomized approximation errors.The section separates expected-value results from bounds on the probability of large deviations.
  • Expected approximation error: Expected Frobenius error is compared with the Eckart–Young rank-k baseline and improves quickly as oversampling increases.For p ∼k, the error is within a constant factor of the baseline; with decaying singular values, it may be on the same order as σk+1.
  • Expected approximation error: Expected spectral-norm error combines a σk+1 baseline term with an additional Frobenius-norm contribution whose polynomial factor declines as oversampling increases.The average spectral-norm error remains within a small polynomial factor of σk+1.
  • Deviation bounds: For p ≥4, deviation theorems bound Frobenius- and spectral-error excursions above their expected values with explicit failure probabilities.The spectral bound’s constants and precise form are not optimal, but it provides a fairly good picture of the observed behavior.
  • Power scheme: Power iterations drive the extra spectral-error factor toward one exponentially fast as the exponent q increases.When q ∼log (min{m, n}), the resulting estimate can remove the dimensional factor min{m, n} for decaying tail singular values.

11. SRFT test matrices.

SRFT test matrices accelerate randomized matrix approximation by using structured Fourier-based sampling, while preserving subspace geometry under sufficient sampling. The resulting error bounds are within polynomial factors of optimal rank-k errors, though SRFTs have higher failure probabilities and require a logarithmic sampling factor in worst cases.

  • SRFT construction: An SRFT combines random diagonal modulation, a unitary discrete Fourier transform, and uniform coordinate restriction to form a structured test matrix.This structure allows the matrix product in the randomized proto-algorithm to be performed quickly.
  • Subspace embedding: An appropriately designed SRFT approximately preserves the geometry of a fixed k-dimensional subspace with failure probability at most O(k^-1).Equivalently, an SRFT with dimension ℓ∼k log(k) is unlikely to have a kernel intersecting that subspace.
  • Worst-case limitation: The logarithmic factor log(k) in the lower bound on ℓ cannot generally be removed because worst-case subspaces reduce the sampling requirement to a coupon-collector problem.Such examples require at least k log(k) samples to obtain a complete set of k distinct sampled columns with nonnegligible probability.
  • Approximation guarantees: SRFT-based rank-k approximations achieve spectral- and Frobenius-norm error bounds within polynomial factors of the optimal rank-k baselines, with the factor decreasing as ℓ increases.The baselines are σ_k+1 for spectral norm and the corresponding singular-value tail series for Frobenius norm.
  • Practical performance: SRFT failure probability is roughly k^-1, substantially worse than the Gaussian case’s roughly e^-(ℓ-k), although empirical performance is often strong.The paper reports that ℓ = k + 20 is adequate in almost all applications, despite the general guarantee requiring ℓ∼k log(k).

Appendix A. On Gaussian matrices.

Appendix A collects Gaussian-matrix properties used in the analysis, emphasizing that most results are known while one requires a difficult new argument and the real case is treated explicitly.

  • Scope: The appendix assembles Gaussian-matrix properties used throughout the paper’s analysis.Most results follow quickly from existing literature.
  • New argument: One result requires a surprisingly difficult new argument.
  • Real and complex cases: The discussion focuses on the real case; the complex case is similar but yields better results.

A.1. Expectation of norms.

This section gives propositions for expected norms of scaled Gaussian matrices. It uses Gaussian and Frobenius-norm invariance to reduce the Frobenius calculation to diagonal matrices and notes a related spectral-norm bound due to Gordon.

  • Expectation of norms: Proposition A.1 states the expected Frobenius norm of a scaled Gaussian matrix for fixed real matrices S and T.The matrix G is drawn from the standard Gaussian distribution.
  • Expectation of norms: Orthogonal invariance of Gaussian matrices and unitary invariance of the Frobenius norm permit assuming that S and T are diagonal.The resulting expression remains valid for general S and T because its right-hand side is unitarily invariant.
  • Expectation of norms: Proposition A.2 presents a corresponding expected spectral-norm result for scaled Gaussian matrices.The surrounding discussion identifies Gordon’s literature bound as an excellent result derived using a sharp version of Slepian’s lemma.

A.2. Spectral norm of pseudoinverse.

This section develops bounds for the spectral norm of the pseudoinverse of a rectangular standard Gaussian matrix. It uses a tail-probability proposition and a standard tail-integral argument to bound the expected norm.

  • Spectral-norm tail bound: Proposition A.3 gives a probability bound for the spectral norm of the pseudoinverse of an m×n standard Gaussian matrix when n ≥ m ≥ 2.The bound applies for each t > 0.
  • Expected norm: Proposition A.3 is used to derive an expected spectral-norm bound for a pseudo-inverted Gaussian matrix.The derivation applies the proposition to control the tail in the expectation calculation.
  • Expected norm: The expected norm is computed using the integral formula for the mean of a nonnegative random variable.The resulting inequality holds for all E > 0.
  • Expected norm: The upper bound is minimized by choosing E = C1/(p+1), after which the expression is substituted and simplified.The second inequality follows from Proposition A.3.

A.3. Frobenius norm of pseudoinverse.

This section derives an exact expectation for the squared Frobenius norm of a pseudo-inverted Gaussian matrix and introduces a new large-deviation bound for its tail behavior. The tail result applies under a stronger dimensional condition, although its form and constants are not ideal.

  • Expectation: The squared Frobenius norm of a pseudo-inverted Gaussian matrix is connected to the trace of an inverted Wishart matrix, yielding an exact expectation.The connection enables explicit computation through the inverted Wishart distribution.
  • Expectation: Proposition A.5 concerns an m×n standard Gaussian matrix under the condition n−m ≥2.The proposition establishes the setting for the expectation identity.
  • Tail behavior: Theorem A.6 provides a new bound on the probability of a large deviation for the Frobenius norm of a pseudo-inverted Gaussian matrix.The theorem applies to an m × n standard Gaussian matrix with n −m ≥4 and each t ≥1.
  • Tail behavior: The proof relies on special properties of Gaussian matrices and brute force because standard tail-bound methods often fail without normal or exponential concentration.The authors acknowledge that the theorem’s precise form and constants are not ideal, prioritizing a useful bound with minimal fuss.

A.3.1. Technical background.

This section establishes notation and technical probabilistic results used later, including properties of Lq norms, Gaussian matrices, and chi-square moments. It also introduces assumptions for an m × n Gaussian matrix.

  • The Lq norm of a random variable is defined for q ≥1 and satisfies the triangle inequality.
  • An m × n standard Gaussian matrix with n ≥m is orthogonally equivalent to a random bidiagonal matrix.
  • The squared variables appearing in the Gaussian-matrix representation follow mutually independent χ2 distributions with degrees of freedom indexed by j.
  • The moments of a χ2 variate are characterized using special functions, with the stated result applying when 0 ≤q < k/2.
  • Subsequent lemmas bound positive and negative moments of χ2 variates, with the negative-moment result assuming k ≥5 and 2 ≤q ≤(k −1)/2.
  • The section later considers an m × n Gaussian matrix G under the dimensional assumption n −m ≥4.

A.3.2. Proof of Theorem A.6.

The proof derives a tail bound for Z by representing a Gaussian matrix through an orthogonally equivalent bidiagonal matrix and analyzing its pseudoinverse. Moment bounds, Markov’s inequality, and a union bound then yield the advertised concentration result under n −m ≥4.

  • Context: The proof’s approach is inspired by Szarek’s work on square Gaussian matrices.The paper notes that more conceptual and extensible arguments for inverse spectral-function concentration would be valuable.
  • Representation: Proposition A.7 represents the Gaussian matrix G as orthogonally equivalent to a bidiagonal matrix L, whose pseudoinverse provides a tractable representation for the random variable.The argument uses an analogy with triangular-matrix inversion to express L†.
  • Representation: The proof transfers Frobenius-norm relations from L† to G† using orthogonal equivalence and unitary invariance.This connects the bidiagonal representation to the original Gaussian matrix.
  • Tail bound: For q = (n−m)/2, moment estimates and Markov’s inequality produce large-deviation bounds for each summand.The first relations rely on variate independence and the triangle inequality for the Lq norm.
Loading 0909.4061v2…