Source-linked AI summary
Limiting Laws of Coherence of Random Matrices with Applications to Testing Covariance Structure and Construction of Compressed Sensing Matrices
Tony Cai, Tiefeng Jiang
TL;DR
The paper addresses inference and matrix-construction problems in high dimensions, where p may greatly exceed n. It derives limiting laws for random-matrix coherence in independent and dependent Gaussian settings, then applies them to covariance-structure testing and compressed sensing. The results include new high-dimensional regimes for the laws and a statistic for testing covariance bandedness, while convergence-speed improvement remains open.
Problem
The paper studies how to analyze covariance structure and construct compressed sensing matrices when p can be much larger than n.
Method
It derives limiting laws for coherence in i.i.d. random matrices and dependent Gaussian matrices with banded covariance, then uses them in covariance tests and compressed-sensing analysis.
Results
The results remain valid under moment conditions when log p = o(n^β) for some β > 0, and the paper proposes Ln,τ with a law of large numbers and limiting distribution for testing covariance bandedness.
Takeaways & Limitations
Coherence asymptotics provide a common basis for testing covariance structure and assessing whether random measurement matrices satisfy the mutual incoherence property.
Takeaways & Limitations
The paper leaves improving the convergence speed of Ln,τ as future work.
Abstract
from arXiv · showhide
Testing covariance structure is of significant interest in many areas of statistical analysis and construction of compressed sensing matrices is an important problem in signal processing. Motivated by these applications, we study in this paper the limiting laws of the coherence of an $n\times p$ random matrix in the high-dimensional setting where $p$ can be much larger than $n$. Both the law of large numbers and the limiting distribution are derived. We then consider testing the bandedness of the covariance matrix of a high dimensional Gaussian distribution which includes testing for independence as a special case. The limiting laws of the coherence of the data matrix play a critical role in the construction of the test. We also apply the asymptotic results to the construction of compressed sensing matrices.
1 Introduction
The paper derives limiting laws for the coherence of random matrices when p can greatly exceed n, then uses these results for covariance-structure testing and compressed sensing. It studies both independent entries and dependent Gaussian rows with banded covariance.
- 1 Introduction: High-dimensional random-matrix methods are needed because classical fixed-p, large-n results no longer apply when p is much larger than n.
- 1 Introduction: Coherence is the largest magnitude of the off-diagonal sample correlations, represented by Ln or ˜Ln depending on whether the mean is unknown or known.For compressed sensing, ˜Ln is the usual coherence and small values correspond to incoherence.
- 1.1 Limiting Laws of the Coherence of a Random Matrix: The dependent case considers rows drawn from Np(µ, Σ) with banded covariance and derives limiting distributions for Ln,τ and ˜Ln,τ under the bandedness null hypothesis.The dependent analysis is technically harder because it must account for the dependence structure of Σ.
- 1.2 Testing Covariance Structure: The asymptotic coherence laws support tests of covariance bandedness, including independence as a special case, and the construction of compressed sensing matrices.The covariance test uses coherence of the data matrix, while the compressed-sensing application evaluates the mutual incoherence property.
2 Limiting Laws of Coherence of Random Matrices
The paper derives laws for the coherence of high-dimensional random matrices, focusing on p much larger than n and extending results from independent entries to dependent Gaussian rows. These laws support covariance-structure testing and compressed-sensing matrix construction.
- Limiting laws: The coherence is the largest magnitude among off-diagonal entries of the sample correlation matrix, with particular interest in p ≫ n.The paper studies both ordinary and known-mean sample correlation matrices.
- The i.i.d. Case: For i.i.d. entries, the paper derives a law of large numbers for coherence under boundedness and under exponential-moment conditions.The bounded case assumes log p = o(n), while the exponential-moment case assumes log p = o(n^β), with β = α/(4 + α).
- The i.i.d. Case: Stronger moment conditions permit the law of large numbers to remain valid for higher orders of p.If exponential moments of every positive order exist, β approaches 1 and the admissible order approaches o(n).
- The i.i.d. Case: The asymptotic results cover earlier comparable-dimension results and extend to regimes with p growing nearly exponentially in a power of n.The paper states that, apart from moment conditions, its results cover those of Liu, Lin and Shao and other cited work.
- Applications: The limiting laws are used to construct an asymptotically level-α test for covariance bandedness.The test defined in (18) has asymptotic size α under the stated conditions.
- The Dependent Case: For Gaussian rows with banded covariance, the paper studies dependent coherence statistics and obtains a type-I extreme-value limit under explicit growth and dependence conditions.The conditions include log p = o(n^1/3), τ = o(p^t) for every t > 0, and |Γ_p,δ| = o(p).
- The Dependent Case: The dependent-case theorem also applies to U_n,τ, while violations of either of two essential assumptions can make its conclusion fail.The paper gives examples illustrating the necessity of those assumptions.
3 Testing the Covariance Structure
The paper applies the limiting distribution of coherence to testing whether a high-dimensional Gaussian covariance matrix is banded, including independence as a special case. The resulting test has asymptotic size α under the stated conditions.
- For independent Gaussian observations, the asymptotic distribution of L_n,τ provides a test statistic for covariance bandedness.
- The testing problem asks whether correlations vanish beyond lag τ, with τ = 1 corresponding to independence.
- When τ = 1, L_n,τ reduces to coherence L_n, so the independence test is based on coherence.
- Under Theorem 4’s conditions, the test T has asymptotic size α.
- Eigenvalue-based testing is limited because the largest-eigenvalue distribution is unknown even when p/n approaches a finite positive constant, and eigenvalues are not useful for bandedness when τ ≥ 2.
4 Construction of Compressed Sensing Matrices
The paper uses coherence and its limiting laws to study how random measurement matrices support compressed sensing recovery. These results characterize the likelihood of the mutual incoherence property and provide probability bounds for random matrix coherence.
- Random measurement matrices are sought for recovering k-sparse signals from few linear measurements, because deterministic construction is difficult.
- The mutual incoherence property requires small pairwise column correlations and supports exact noiseless and stable noisy recovery through constrained ℓ1 minimization.
- Theorem 1 and Theorem 2 determine how likely a random matrix is to satisfy the mutual incoherence property.
- For i.i.d. entries with finite exponential-square moments, Proposition 4.1 gives P(L̃_n ≥ t) ≤ 3p^2e^(-ng(t)) for any t > 0.
- The coherence bound applies to three example random matrices under different restrictions on sparsity k, and generally holds under the stated exponential-moment condition.
- The paper corrects a prior claim that coherence for an i.i.d. Gaussian random matrix is approximately 2.
5 Discussion and Comparison with Related Results
The paper extends coherence asymptotics to ultra-high dimensions and dependent Gaussian coordinates, while introducing a bandedness test. It prioritizes limiting results for coherence statistics used in compressed sensing, leaving convergence-rate improvements for future work.
- Comparison with Related Results: The results remain valid when log p = o(n^β) under suitable moment conditions, allowing p to grow substantially with n.This extends the usable dimensional regime beyond earlier settings discussed by the authors.
- Comparison with Related Results: The analysis covers dependent coordinates from Np(µ, Σ) when Σ is banded and µ is arbitrary, rather than only i.i.d. coordinates.The dependence structure of Σ requires more involved arguments than the independent case.
- Testing Covariance Structure: The paper proposes Ln,τ and derives its law of large numbers and limiting distribution for testing covariance-matrix bandedness.Testing independence is included as a special case of the broader bandedness problem.
- Comparison with Related Results: The authors focus on Ln and ˜Ln despite an alternative statistic designed to improve convergence speed under polynomial dimensional growth.They retain these statistics because of their specific use in applications such as compressed sensing.
- Future Work: Improving the convergence speed of Ln,τ remains future work.The paper identifies modification of Ln,τ as a possible route toward faster convergence.
6 Proofs
The proofs reduce coherence results to bounds for maxima of pairwise inner products and normalization terms. They combine Poisson approximation, moderate deviations, concentration inequalities, and tightness under growth and moment conditions.
- Technical Tools: The proof framework defines the maximum off-diagonal magnitude and controls related normalization quantities for the sample correlation matrix.The notation includes maxima such as Wn and several bn,i terms used throughout the arguments.
- Technical Tools: Poisson approximation handles dependence among pairwise exceedance events by assigning each pair a neighborhood of pairs sharing an index.For independent variables, the corresponding external-dependence term can vanish.
- Technical Tools: Moderate-deviation and concentration bounds establish maxima and normalization control under conditions such as log p = o(n^β).The exponent β depends on the available moment condition, including β = α/(4 + α) in one stated result.
- Proofs of Main Theorems: The dependent-case theorem follows the independent-case proof structure while replacing the supporting proposition and tightness condition.The paper explicitly describes the proof of Theorem 2 as a corresponding substitution.
- Proofs of Main Theorems: Theorem 1 assumes i.i.d. entries without loss of generality because coordinatewise shifts and positive rescalings leave the sample correlation matrix unchanged.The proof therefore works with mean-zero, variance-one entries.
7 Appendix
The appendix supplies omitted proofs and verifies technical propositions used by the main theorems. Its arguments combine truncation, conditional bounds, Bernstein and Chernoff inequalities, and model-specific rate calculations.
- Appendix Scope: The appendix proves Proposition 6.2 and Lemmas 6.5–6.7 and 6.9–6.13, which support the main results.It also verifies the three examples introduced in Section 4.
- Technical Proofs: Truncation and exponential-tail arguments control rare large observations before applying concentration bounds to the remaining terms.The proofs use moment conditions to obtain exponentially small error probabilities.
- Technical Proofs: Bernstein and Chernoff inequalities yield tightness and convergence controls for the auxiliary maxima and normalization terms.The resulting bounds are repeatedly used to conclude propositions and lemmas.