The two-to-infinity norm and singular subspace geometry with applications to high-dimensional statistics

Joshua Cape; Minh Tang; Carey E. Priebe

Source-linked AI summary

The two-to-infinity norm and singular subspace geometry with applications to high-dimensional statistics

Joshua Cape, Minh Tang, Carey E. Priebe

arXiv:1705.10735v3May 30, 2017math.ST

TL;DR

The paper addresses how to obtain refined perturbation control for singular vectors and subspaces, especially when singular values are repeated. It combines a Procrustean matrix decomposition with two-to-infinity norm machinery, obtaining entrywise perturbation results across several noise models and applications.

Problem
Existing singular subspace perturbation analysis requires finer control of singular-vector entries and must accommodate singular value multiplicity across statistical applications.
Method
The paper combines a flexible Procrustean matrix decomposition with technical machinery for the two-to-infinity norm to analyze additive singular value decomposition perturbations.
Results
The framework yields perturbation results across i.i.d., row-independent, entry-independent, and dependent noise models, including covariance estimation, singular subspace recovery, and multiple graph inference.
Takeaways & Limitations
The two-to-infinity norm provides finer uniform entrywise control and is preferable in certain settings, including bounded-coherence matrices.
Takeaways & Limitations
The framework does not make a distinct singular value assumption, so singular vectors are identifiable only up to an orthogonal transformation when singular values are repeated.

Abstract

from arXiv · show

The singular value matrix decomposition plays a ubiquitous role throughout statistics and related fields. Myriad applications including clustering, classification, and dimensionality reduction involve studying and exploiting the geometric structure of singular values and singular vectors. This paper provides a novel collection of technical and theoretical tools for studying the geometry of singular subspaces using the two-to-infinity norm. Motivated by preliminary deterministic Procrustes analysis, we consider a general matrix perturbation setting in which we derive a new Procrustean matrix decomposition. Together with flexible machinery developed for the two-to-infinity norm, this allows us to conduct a refined analysis of the induced perturbation geometry with respect to the underlying singular vectors even in the presence of singular value multiplicity. Our analysis yields singular vector entrywise perturbation bounds for a range of popular matrix noise models, each of which has a meaningful associated statistical inference task. In addition, we demonstrate how the two-to-infinity norm is the preferred norm in certain statistical settings. Specific applications discussed in this paper include covariance estimation, singular subspace recovery, and multiple graph inference. Both our Procrustean matrix decomposition and the technical machinery developed for the two-to-infinity norm may be of independent interest.

1. Introduction.

The paper develops perturbation tools for singular vectors and subspaces using the two-to-infinity norm and a Procrustean decomposition. It applies this framework to covariance estimation, singular subspace recovery, and graph inference while allowing singular value multiplicity.

Singular subspace geometry underlies applications including principal component analysis, covariance estimation, spectral clustering, and graph inference.
The paper develops two-to-infinity perturbation tools and Procrustean matrix decompositions for singular vectors and subspaces.The framework yields perturbation bounds within an additive singular value decomposition perturbation model.
The analysis allows singular value multiplicity while assuming only a population singular value gap.
The results improve low-rank singular-vector entrywise bounds and establish among the first estimation bounds for multiple graph inference with edge correlation.
For covariance estimation, the paper studies high-dimensional Gaussian samples under effective-rank, eigengap, conditioning, and coherence assumptions.The covariance application considers simultaneously growing sample size and dimension.

2. Preliminaries.

The preliminaries define the matrix, subspace, norm, and Procrustes-analysis framework used to study singular-vector perturbations. They motivate the two-to-infinity norm as a finer entrywise-control tool and set the singular-value-gap setting for subsequent results.

Norms: The two-to-infinity norm equals the maximum Euclidean row norm and can provide entrywise control through a computable matrix quantity.It may serve as a surrogate for the maximum-entry norm in suitable settings.
Norms: When the row dimension greatly exceeds the column dimension, the two-to-infinity norm can be much smaller than the spectral norm.Bounding it can therefore yield more refined entrywise control.
Procrustes analysis: Procrustes analysis aligns two orthonormal matrix bases using an orthogonal transformation, with the Frobenius-norm solution available explicitly.Solutions under other norms are generally not analytically tractable.
Perturbation geometry: Directly analyzing the aligned difference ˆU − UWU can improve two-to-infinity bounds when its two-to-infinity norm is much smaller than its spectral norm.This regime is especially relevant when the ambient dimension is large relative to the subspace dimension.
Perturbation setup: The perturbation framework writes an observed matrix as ˆX = X + E, with X unobserved and E an additive perturbation.The matrices are analyzed through their partitioned singular value decompositions.
Singular subspaces: The framework primarily assumes a singular-value gap σr(X) ≫ σr+1(X), while also allowing separated sequential singular values more generally.The generalized bounds depend on the relevant two-sided gap.

3. Main results.

The main results introduce a Procrustean matrix decomposition for aligned singular-vector perturbations and combine it with two-to-infinity machinery to derive refined bounds. The decomposition identifies leading and residual terms whose sizes depend on perturbation structure, singular-value gaps, and singular-vector delocalization.

Procrustean decomposition: Theorem 3.1 establishes a Procrustean matrix decomposition for ˆU − UWU whenever ˆX has rank at least r.The aligned difference is decomposed into terms involving the perturbation, singular-vector changes, and singular-value factors.
Procrustean decomposition: Under suitable perturbation and structural conditions, the leading behavior is represented by (I − UU⊤)EVWV ˆΣ^-1.This term reflects the perturbation projected outside the target singular subspace, modulo orthogonal alignment.
Perturbation bounds: Several residual terms can be substantially smaller than conventional subspace-distance bounds under favorable perturbation, singular-gap, or coherence conditions.The relevant conditions involve relative perturbation size, σr+1(X)/σr(ˆX), and ∥U∥2→∞ ≪ 1.
Procrustean decomposition: The first term after the equality sign in Corollaries 3.5 and 3.6 is the leading-order term of practical interest.The paper later quantifies this leading-order interpretation through perturbation bounds.
Perturbation bounds: The unified methodology combines the decomposition, its variants, two-to-infinity machinery, and geometric observations to bound ˆU − UWU.Analogous bounds for right singular vectors follow with the corresponding substitutions.
Perturbation bounds: The results include uniform two-to-infinity perturbation bounds for rectangular matrices and a simpler low-rank specialization under singular-gap and perturbation assumptions.The low-rank case uses σr+1(X) = 0 and a weaker condition on the auxiliary constants.

4. Applications.

The applications translate the perturbation framework into entrywise eigenvector bounds, singular-subspace recovery results, and graph-inference tools. They also connect two-to-infinity control with coherence, random-matrix models, and dependent network models.

Covariance and eigenvector perturbation: The two-to-infinity perturbation bound immediately yields maximum-entry and ℓ∞-type singular-vector bounds up to orthogonal transformation.The orthogonal transformation generalizes sign matching when singular values are distinct and separated.
Covariance and eigenvector perturbation: The framework applies to low-rank matrices with bounded coherence and can extend to robust covariance estimation with heavy-tailed random variables.The paper states that its symmetric result improves prior ℓ∞ perturbation bounds in this setting.
Covariance and eigenvector perturbation: Theorem 4.2 provides a deterministic eigenvector perturbation bound that permits repeated eigenvalues and does not assume small ∥U∥2→∞.Combining it with bounded coherence yields a further specialized bound.
Singular subspace recovery: For Gaussian rectangular noise, Theorem 4.3 gives high-probability upper and lower bounds for right-singular-subspace perturbation that can nearly match.The result concerns ∥ˆV − VWV∥2→∞ under the stated rank, dimension, and signal-strength regime.
Graph inference: In network analysis, the results extend two-to-infinity bounds to models whose population matrix need not have distinct eigenvalues.The Procrustes analysis also suggests a refinement of test statistics for two-sample graph inference.
Graph inference: The generality of the framework permits random graph models with edge-dependence structure, including models satisfying the (C, c, γ) property.The paper identifies dependent-edge models as an important direction for future statistical network-analysis work.

2. The random variables

The multiple-graph inference setting studies leading eigenvectors of an omnibus matrix for correlated stochastic block model graphs. Theorem 4.7 provides a corresponding guarantee, while its dependence on edge correlation is left implicit.

Multiple graph inference: Theorem 4.7 addresses leading-eigenvector estimation for a multiple-graph omnibus matrix when the graphs are not independent.The result concerns a pair of correlated stochastic block model graphs.
Model and assumptions: The model and adjacency omnibus matrices are built from two ρ-correlated graphs, with rank and spectral-gap assumptions imposed on the model matrix.The setup assumes maximum expected degree Δ ≫ log^4(n) and σ_r(O) ≥ cΔ for some c > 0.
Perturbation guarantee: The analysis yields a two-to-infinity perturbation guarantee for the leading eigenvector subspaces.The paper contrasts this with the weaker bound obtained from spectral-norm analysis.
Scope: The dependence of the theorem's constants and probability statement on the edge-correlation factor ρ is not made explicit.The paper states that a more careful analysis could expose this dependence but does not pursue it.

5. Discussion and Conclusion.

The paper concludes that its Procrustean decomposition and two-to-infinity machinery apply across diverse noise models and statistical analyses. It emphasizes flexible, model-specific use while positioning the framework for future applications.

Scope of noise models: The framework covers noise matrices with iid entries, iid rows, independent nonidentically distributed entries, and dependent nonidentically distributed entries.These cases span the application sections' principal noise-model categories.
Application-specific analysis: Each application requires choosing a decomposition variant, transitioning between norms, and analyzing the resulting terms in a model-specific way.The paper gives bounded coherence and direct control of ∥EU∥2→∞ as examples of context-dependent analysis.
Core framework: The paper focuses on decomposing ˆU − UW_U and using the two-to-infinity norm for matrix perturbation analysis.This focus supports refined entrywise singular-vector and eigenvector perturbation bounds.
Future scope: The authors identify ample open problems and applications for future use of the two-to-infinity norm and matrix decompositions.They hope the framework's generality and flexibility will encourage broader use in statistics.

6. Proofs.

This section develops technical properties of the two-to-infinity norm and its relationship to common matrix norms. It also establishes geometric and Procrustes facts used in singular-subspace perturbation analysis.

Two-to-infinity norm: The two-to-infinity norm equals the maximum Euclidean row norm of a matrix.This characterization makes the norm directly interpretable through row-wise magnitudes.
Norm properties: The two-to-infinity norm is subordinate to ℓ2 and ℓ∞ vector norms but is not generally sub-multiplicative for matrices.The section develops constrained product inequalities despite this limitation.
Norm comparison: For tall, skinny rectangular matrices, the two-to-infinity norm can be much smaller than the spectral norm.This separation motivates its use for entrywise control.
Procrustes geometry: The section records Procrustes and singular-subspace relationships needed to compare aligned singular-vector matrices.These include bounds involving the Frobenius-optimal Procrustes transformation and principal-angle quantities.

6.2. Singular subspace geometric bounds.

The section develops geometric bounds for aligned singular subspaces by separating projected residuals from Procrustes alignment error. The resulting decomposition isolates terms that can be controlled in spectral and two-to-infinity norms.

Projected residual: The residual after projecting Ũ onto the span of U has spectral norm equal to ∥sin Θ(Ũ, U)∥2.This identifies the orthogonal residual with the standard subspace-angle quantity.
Canonical-angle geometry: The spectral Procrustes discrepancy is bounded by the largest squared sine of the canonical angles between the two subspaces.The bound is expressed through ∥sin Θ(Ū, U)∥2^2.
Matrix decomposition: The decomposition rewrites the perturbed singular-vector matrix using a noise term and a population-matrix term involving the right-subspace residual.The key identity separates (I − UUᵀ)E V̂ Σ̂^-1 from (I − UUᵀ)X(V̂ − VVᵀV̂)Σ̂^-1.
Aligned perturbation terms: The decomposition further introduces the orthogonal factor W_V to express the noise contribution through aligned and residual right-singular-vector components.The resulting terms include (I − UUᵀ)E(V̂ − V W_V)Σ̂^-1 and (I − UUᵀ)E V W_V Σ̂^-1.
Application relevance: The term (I − UUᵀ)E V W_V Σ̂^-1 can function as the leading-order term in applications.The theorem and its corollaries provide the surrounding norm controls.

6.4. Theorem 3.7.

Theorem 3.7 establishes perturbation bounds for aligned singular vectors under a spectral-gap assumption, using the two-to-infinity norm and allowing singular-value multiplicity. Its consequences connect entrywise perturbation to matrix norms and singular-vector incoherence.

Spectral stability: σr(X) ≥ 2∥E∥2 ensures σr(X̂) remains at least half of σr(X) by Weyl’s inequality.This assumption is used to control the perturbed singular value before applying the theorem’s decomposition and auxiliary bounds.
Proof strategy: Theorem 3.7’s proof combines Corollary 3.6 with Proposition 6.5 and Lemma 6.7 to control aligned singular-vector perturbations.The displayed proof passages identify these results as the ingredients yielding the theorem.
Norm-based bound: 2 × maxη∈{1,∞}{∥E∥η} × maxZ∈{U,V}{∥Z∥2→∞} bounds the resulting perturbation quantity.The bound uses the two-to-infinity norms of the population singular-vector matrices together with the induced perturbation size.

6.7. Theorem 1.1.

Theorem 1.1 derives a high-probability two-to-infinity perturbation bound for leading singular vectors in a Gaussian covariance setting. The proof combines concentration for covariance-noise terms with spectral-gap and effective-rank assumptions.

Assumptions: max{r(Γ), log d} = o(n) is assumed, where r(Γ) := trace(Γ)/σ1(Γ) is Γ’s effective rank.This condition controls the covariance-estimation regime used in the theorem.
Subspace control: Theorem 6.9 provides ∥sin Θ(Û, U)∥2 ≤ C∥En∥2/δr(Γ), linking spectral subspace error to covariance-noise size and the population gap.This spectral bound is used alongside the entrywise analysis in the theorem’s proof.
Spectral condition: δr(Γ) := σr(Γ) − σr+1(Γ) ≥ c2σr(Γ) > 0 supplies the population singular-value gap.The same passage gives the accompanying sin Θ bound, which controls subspace error under this gap.
Concentration argument: The proof bounds EnU entrywise by expanding ⟨Enei, uj⟩ and applying sub-exponential concentration to the resulting centered terms.The argument uses Gaussian structure, Orlicz-norm bounds, and a union bound over indices.
High-probability result: With probability at least 1 − d−2, the aggregated covariance-noise bounds hold under the stated effective-rank and spectral assumptions.The result passage explicitly records the high-probability conclusion after aggregating the preceding observations.

6.8. Theorem 4.2.

Theorem 4.2 specializes the general perturbation decomposition to symmetric rank-r matrices and controls the aligned eigenvector perturbation through term-wise bounds. The proof exploits rank structure and Gaussian concentration for projected noise.

Decomposition: The symmetric rank-r specialization yields a decomposition of Û − UWU into perturbation terms involving E, U, Û, and the inverse perturbed eigenvalue matrix.The displayed decomposition isolates terms for subsequent technical bounds.
Term-wise analysis: Theorem 4.2 bounds each decomposition term using the technical results from Sections 6.1 and 6.2.The proof explicitly identifies these results as the source of the term-wise controls.
Rank simplification: When rank(X) = r, the orthogonal complement contribution involving X vanishes, simplifying the remaining perturbation terms.The simplification follows from the stated rank assumption and the identities involving U and V.
Noise control: The projected Gaussian noise terms are centered independent multivariate normal vectors, enabling concentration-based control of their entries.The proof describes their covariance structure and applies Gaussian concentration with a union bound.
Conclusion: The resulting high-probability bound is obtained by combining the projected-noise estimates with the preceding decomposition and auxiliary inequalities.The proof passages state that these observations are combined to obtain the theorem’s final bound.

6.10. Theorem 4.7.

Theorem 4.7 analyzes aligned singular-vector perturbations for a multiple-graph model by grouping correlated matrix elements and applying bounded-variable concentration. Under a degree condition, it obtains an asymptotic two-to-infinity rate.

Multiple-graph structure: The proof groups matrix elements to handle the multiple-graph correlation structure while bounding ∥Û − UWU∥2→∞.This grouping is the central device used to manage dependence across the graph observations.
Proof components: A spectral-norm bound for the block matrix Ô − O supplies a preliminary control that is combined with coordinatewise bounds for (Ô − O)U.The proof explicitly separates these spectral and two-to-infinity components.
Assumptions: ∆ ≫ log^4(n) and σr(O) ≥ c∆ imply spectral control of the graph-noise and perturbed signal matrices with probability 1 − o(1).These assumptions yield ∥Ai − P∥2 = O(√∆) and ∥Σ̂−1∥2 = O(1/∆) through Weyl’s inequality.
Concentration argument: The proof expands each coordinate into sums of independent, bounded, mean-zero variables and applies Hoeffding’s inequality repeatedly.The bounded ranges differ across the first- and second-order expansions, supporting the coordinatewise concentration steps.
Main rate: The aligned perturbation satisfies ∥Û − UWU∥2→∞ = O_r((log n)/∆) with probability 1 − o(1) as n → ∞.This is the theorem’s stated asymptotic two-to-infinity rate.