PaperlayerView exact revision on arXiv

Source-linked AI summary

Fundamental limit of sample generalized eigenvalue based detection of signals in noise using relatively few signal-bearing and noise-only samples

N. Raj Rao, Jack W. Silverstein

arXiv:0902.4250v1cs.IT

TL;DR

The paper asks when signals can be reliably detected from relatively few signal-bearing and noise-only samples in arbitrarily colored noise. It analyzes sample generalized eigenvalues using random matrix theory and proves that only population signal eigenvalues above a deterministic threshold are asymptotically distinguishable from noise. The results motivate an effective number of identifiable signals and a threshold-based detection algorithm.

  • Problem

    The central problem is determining whether signals can be reliably detected from finite signal-plus-noise and noise-only samples, a prerequisite for subsequent signal parameter estimation.

  • Method

    The paper applies random matrix theory to sample generalized eigenvalues and defines identifiable signals through a deterministic threshold depending on system dimensionality and sample sizes.

  • Results

    Only population signal eigenvalues above the deterministic threshold can be reliably distinguished asymptotically from noise eigenvalues.

  • Takeaways & Limitations

    Signals below the detectability threshold cannot be reliably detected, whereas signals above it can be detected by the proposed threshold-based approach.

Abstract

from arXiv · show

The detection problem in statistical signal processing can be succinctly formulated: Given m (possibly) signal bearing, n-dimensional signal-plus-noise snapshot vectors (samples) and N statistically independent n-dimensional noise-only snapshot vectors, can one reliably infer the presence of a signal? This problem arises in the context of applications as diverse as radar, sonar, wireless communications, bioinformatics, and machine learning and is the critical first step in the subsequent signal parameter estimation phase. The signal detection problem can be naturally posed in terms of the sample generalized eigenvalues. The sample generalized eigenvalues correspond to the eigenvalues of the matrix formed by "whitening" the signal-plus-noise sample covariance matrix with the noise-only sample covariance matrix. In this article we prove a fundamental asymptotic limit of sample generalized eigenvalue based detection of signals in arbitrarily colored noise when there are relatively few signal bearing and noise-only samples. Numerical simulations highlight the accuracy of our analytical prediction and permit us to extend our heuristic definition of the effective number of identifiable signals in colored noise. We discuss implications of our result for the detection of weak and/or closely spaced signals in sensor array processing, abrupt change detection in sensor networks, and clustering methodologies in machine learning.

I. INTRODUCTION

The paper studies signal-count detection from sample generalized eigenvalues when signal-bearing and noise-only covariance matrices must be estimated from finite samples. It establishes a colored-noise detectability limit and proposes an estimator whose reliability depends on eigen-SNR relative to a critical value.

  • Model-order selection is the critical first step before estimating signal parameters in observations containing signals embedded in additive noise.
  • The approach uses generalized eigenvalues formed by whitening the signal-plus-noise sample covariance matrix with the noise-only sample covariance matrix.
  • The paper extends a prior white-noise analysis to arbitrary colored noise and defines identifiable signals using a deterministic threshold based on sample sizes and system dimensionality.
  • Increasing system dimensionality can raise the detectability threshold, so adding sensors may reduce the effective number of identifiable signals.
  • A new estimator is reliable when a signal's eigen-SNR exceeds a critical value and cannot distinguish it from noise when the eigen-SNR is below that value.

II. PROBLEM FORMULATION

The problem formulation models signal-bearing snapshots as Gaussian signals plus colored Gaussian noise and estimates signal count from generalized eigenvalues of sample covariance matrices. Finite samples blur population eigenvalues, while random-matrix analysis identifies a deterministic threshold separating reliably distinguishable signal eigenvalues from noise eigenvalues.

  • Signal-bearing snapshots are modeled as x_i = A s_i + z_i, with independent Gaussian signal and noise components and an unknown mixing matrix A.
  • When A has full column rank and the signal covariance is nonsingular, the signal covariance has rank k, leaving n − k zero eigenvalues.
  • Population generalized eigenvalues equal one in the n − k dimensional noise subspace, while the remaining k eigenvalues are strictly greater than one.
  • The noise-only sample count must exceed the system dimensionality so its sample covariance is invertible with probability 1.
  • The sample generalized eigenvalues are obtained by eigendecomposing the signal-plus-noise sample covariance whitened by the noise-only sample covariance.
  • Finite-sample blurring makes signal-versus-noise discrimination difficult and motivates a deterministic threshold for reliably distinguishing signal eigenvalues.

III. MAIN RESULT

The paper establishes the asymptotic behavior of sample generalized eigenvalues and identifies a deterministic threshold above which population signal eigenvalues can be distinguished from noise eigenvalues.

  • The signal-free empirical eigenvalue distribution converges almost surely to the population generalized-eigenvalue distribution in the stated high-dimensional limit.
  • Theorem 3.2 characterizes when the largest sample generalized eigenvalues asymptotically separate from the noise eigenvalue bulk.
  • Only population generalized eigenvalues above the deterministic threshold T(c, c1) can be reliably distinguished from noise eigenvalues.The threshold depends on the dimensionality and the numbers of signal-plus-noise and noise-only snapshots.
  • The threshold result recovers the Baik–Silverstein result in the appropriate limiting case.
  • Figure 2 plots the minimum generalized Eigen-SNR T(c, c1)−1 required for asymptotic discrimination as the sensor-to-snapshot ratio varies.The separation between the upper and bottom lines represents SNR loss from estimating the noise covariance matrix.

A. Effective number of identifiable signals

The paper defines an effective number of identifiable signals by counting population generalized eigenvalues above the finite-sample detectability threshold. Signals with smaller eigen-SNRs are asymptotically undetectable by this approach.

  • The effective number of identifiable signals counts eigenvalues of Σ^-1R that exceed T(c, c1).
  • Signals whose eigen-SNR λj−1 is below T(n/m, n/N) are asymptotically undetectable.
  • Figure 2 shows that the required eigen-SNR increases as fewer snapshots are available to estimate the noise-only covariance matrix.

B. Implications for array processing

For two signals in sensor-array processing, identifiability depends on the generalized covariance eigenvalues, sample availability, system dimensionality, and the signals’ spatial relationship.

  • The two-signal covariance model uses uncorrelated signals and array-manifold vectors associated with their source locations.
  • With two signals, the generalized covariance matrix has n−2 eigenvalues equal to one, while the two signal eigenvalues determine detectability.
  • The effective number of signals captures a tradeoff among signal spacing, system dimensionality, available snapshots, and the cosine of the angle between array vectors.
  • Different assumed noise covariance structures, such as AR(1) versus white noise, change the signal SNR required for reliable detection.

C. Other applications

The results connect sample generalized eigenvalue methods to abrupt-change detection in sensor networks and spectral clustering. They also indicate that conditional-independence structure and non-Gaussian data are relevant to understanding when these methods may fail.

  • Abrupt change detection: Conditional independence among sensor observations under a hypothesis is useful when observations follow a Gauss-Markov random field model.This assumption implies a sparse precision matrix.
  • Abrupt change detection: Sparse structure in the inverse noise-only covariance matrix enables experiments with assumed conditional-independence structures to assess detectability of abrupt system changes.
  • Spectral clustering: The results may indicate when generalized eigenvalue-based spectral clustering algorithms fail in machine-learning applications.The cited applications include unsupervised learning, image segmentation, and information retrieval.
  • Spectral clustering: Theorem 3.2 also holds for non-Gaussian data, according to Theorem 6.5.This extends the stated relevance beyond settings commonly assumed to be Gaussian.

IV. AN ALGORITHM FOR RELIABLE DETECTION OF SIGNALS IN NOISE

The paper develops an eigenvalue-counting algorithm for reliable signal detection using Tracy–Widom thresholds, and simulations assess performance near the predicted detectability limit.

  • Algorithm and statistical basis: Above the detectability threshold, signal eigenvalues are expected to follow a Gaussian law; below it, they follow the signal-free Tracy–Widom law.This distributional distinction motivates the detection procedure.
  • Algorithm and statistical basis: Algorithm 1 initializes a significance level, computes a Tracy–Widom quantile and centering and scaling parameters, then iteratively tests eigenvalues to estimate the signal count.The procedure increments the estimated count until the test accepts or the admissible eigenvalue range is exhausted.
  • Numerical validation: Figure 4 illustrates the accuracy of the predicted statistical limit and reliable detection at that limit.The figure uses simulated detection probabilities across signal-to-noise ratio and sample-to-dimension regimes.
  • Algorithm and statistical basis: Algorithm 2 applies analogous Tracy–Widom-based estimation when the noise covariance matrix is known a priori.Its inputs are the eigenvalues of the whitened signal-plus-noise covariance estimate.
  • Numerical validation: Figure 3 compares empirical largest-eigenvalue distributions with and without a signal across 1000 Monte Carlo trials for σ2 = 0.5 and σ2 = 5.The simulations use n = 320, m = 160, and N = 960.

V. CONCLUSION

The conclusion identifies a fundamental finite-sample boundary for generalized-eigenvalue detection: eigen-SNR below the threshold is not reliably detectable, while reducing effective signal-subspace dimension lowers the threshold.

  • Conclusion: Signals below the detectability threshold cannot be reliably detected, whereas signals above it can be reliably detected.The threshold is presented as a fundamental statistical limit for finite-sample discrimination of signal from noise.
  • Conclusion: Adding sensors can degrade performance when signal strength is barely above threshold because the system dimensionality increases.Reducing the dimensionality of the signal subspace lowers the detectability threshold.

A. Mathematical preliminaries

The preliminaries establish the random-matrix framework for sample covariance eigenvalues, using limiting empirical distributions and Stieltjes transforms to characterize spectral behavior.

  • Random-matrix framework: When dimension and sample size grow proportionally, sample covariance matrices need not be close to their population covariance matrices.Their eigenvalue distributions instead admit asymptotic limit theorems.
  • Random-matrix framework: The limiting eigenvalue distribution is represented through its Stieltjes transform, which satisfies an implicit equation in the upper half-plane.The transform provides the analytic description used in subsequent spectral arguments.
  • Random-matrix framework: Stieltjes transforms determine distribution functions through an inversion formula, providing a one-to-one correspondence between the two representations.This links transform-based calculations to eigenvalue distributions.
  • Random-matrix framework: The analysis can equivalently use the m × m dual sample covariance matrix, whose eigenvalues differ only by |n − m| zero eigenvalues.This reformulation is useful when studying the nonzero spectrum.
  • Support characterization: The limiting transform has an explicit inverse, and the associated distribution has qualitative support properties including a continuous derivative on (0, ∞).The inverse is described using the function x_c,H.

B. Support of eigenvalues

The support analysis determines when sample covariance eigenvalues can appear outside the limiting bulk and connects such spectral separation to population eigenvalues outside the support-transform regime.

  • Eigenvalue separation: The support framework distinguishes eigenvalue-distribution convergence from the separate question of whether individual eigenvalues appear outside the limiting support.This motivates the interval-based separation results.
  • Eigenvalue separation: An interval outside the limiting support contains no sample covariance eigenvalues for all sufficiently large dimensions under condition (*).The statement holds almost surely.
  • Eigenvalue separation: When c(1 − H(0)) > 1, the lower support edge is positive and the smallest relevant eigenvalue converges to that edge.The convergence is almost sure.
  • Eigenvalue separation: Intervals not covered by the positive-edge case contain eigenvalues whose locations are constrained relative to the interval boundary for all sufficiently large dimensions.The result is stated through the index of an ordered eigenvalue and the support conditions.
  • Eigenvalue separation: For general bounded population covariance matrices, non-appearance of sample eigenvalues outside the limiting support mirrors separation over corresponding population-support intervals.The theorem assumes finite fourth moments and bounded spectral norm.

C. Behavior of spiked eigenvalues

The analysis characterizes when a small collection of spiked population eigenvalues produces isolated sample eigenvalues outside the limiting bulk spectrum. It also establishes a converse: isolated sample eigenvalues must arise from such spikes under the stated assumptions.

  • Spiked-eigenvalue conditions: Theorem 6.4 gives the converse: any isolated eigenvalue of B_n must be caused by a spiked population eigenvalue.Without a spike, the relevant behavior is governed by the bulk-support case of Theorem 6.1.
  • Spiked-eigenvalue conditions: A spiked eigenvalue can generate an isolated sample eigenvalue when it lies inside an interval outside the support of the remaining population spectrum.Theorem 6.3 allows the number of spiked eigenvalues to grow with n provided it remains o(n).
  • Threshold regime: For a spike above the threshold τ, Theorem 6.3 can accommodate ℓ=o(n) spiked eigenvalues.The threshold construction uses a region separated from the support of the remaining population eigenvalues.
  • Bulk separation: If ℓ bounded spiked eigenvalues converge to t′, the corresponding sample eigenvalues converge to the mapped value x_c,H(−1/t′).The proof uses monotonicity of x_c,H to rule out convergence to different spike locations under the single-limit assumption.
  • Bulk separation: Only o(n) population eigenvalues can lie in the interval associated with an isolated limiting sample eigenvalue when that interval is outside the support of H.This follows because a non-negligible number of eigenvalues there would place mass in the limiting distribution.

E. The eigenvalues of the multivariate F matrix

This section derives the limiting behavior of the multivariate F matrix from random-matrix results for sample covariance matrices. It identifies how population spikes map to sample eigenvalues and how a deterministic threshold separates detectable spikes from the bulk.

  • F-matrix formulation: The multivariate F matrix T_n(1/N)X_nX_n* has the same eigenvalues as B_n, linking generalized-eigenvalue detection to the F-matrix analysis.Its limiting empirical distribution has a density on (0, ∞), with an additional atom at zero when c > 1.
  • Detectability threshold: Theorem 6.5 permits a finite collection of population eigenvalues to converge to a nonrandom spike above the bulk threshold τ while the remaining eigenvalues determine the bulk spectrum.The threshold is defined relative to the limiting upper edge of the nonspiked spectrum.
Loading 0902.4250v1…