Source-linked AI summary
Innovated higher criticism for detecting sparse signals in correlated noise
Peter Hall, Jiashun Jin
TL;DR
Sparse, weak-signal detection with correlated noise is not adequately addressed by standard higher criticism, which uses only marginal information. The paper develops innovated higher criticism and a correlation-dependent detection boundary, showing that dependence can make detection easier and that iHC achieves optimal detection in the Toeplitz case.
Problem
Standard higher criticism was designed for independent noise, while its performance and optimal adaptation to correlated noise require a method that uses the correlation structure.
Method
The paper develops innovated higher criticism and characterizes correlated-noise detection boundaries using the inverse correlation matrix and comparison arguments based on added noise.
Results
In the Toeplitz case, the lower and upper detection-boundary bounds are asymptotically equal, and iHC is optimal while standard HC is not.
Takeaways & Limitations
Correlation can provide a statistical advantage for sparse-signal detection when the detection method is designed to exploit it.
Takeaways & Limitations
Applying the methods to genomic data can be inhibited by the difficulty of estimating Σ_n without information from outside the dataset.
Abstract
from arXiv · showhide
Higher criticism is a method for detecting signals that are both sparse and weak. Although first proposed in cases where the noise variables are independent, higher criticism also has reasonable performance in settings where those variables are correlated. In this paper we show that, by exploiting the nature of the correlation, performance can be improved by using a modified approach which exploits the potential advantages that correlation has to offer. Indeed, it turns out that the case of independent noise is the most difficult of all, from a statistical viewpoint, and that more accurate signal detection (for a given level of signal sparsity and strength) can be obtained when correlation is present. We characterize the advantages of correlation by showing how to incorporate them into the definition of an optimal detection boundary. The boundary has particularly attractive properties when correlation decays at a polynomial rate or the correlation matrix is Toeplitz.
1. Introduction.
The paper develops innovated higher criticism (iHC) to exploit correlation in sparse-signal detection, rather than applying standard HC designed for independent data. It extends the detection boundary to correlated noise and shows that dependence can improve detection performance.
- 1. Introduction.: Innovated higher criticism modifies standard HC to optimize sparse-signal detection under correlated noise.Standard HC uses marginal information without adequately exploiting correlation structure.
- 1. Introduction.: Correlation can make detection statistically easier than independence because nearby noise values vary less and may be easier to identify.With perfect correlation, the noise is constant across locations and can be removed.
- 1. Introduction.: The paper extends the detection boundary to dependent data, where it depends on correlation structure as well as signal sparsity and strength.For polynomially decaying correlation, the paper constructs lower and upper bounds using diagonal entries of the inverse correlation matrix.
- 1. Introduction.: In the Toeplitz case, the lower and upper bounds are asymptotically equal, making iHC optimal while standard HC is not.This establishes a precise correlated-noise detection boundary in that special case.
- 1. Introduction.: The paper’s contribution differs from earlier dependence research by exploiting advantages of dependence rather than primarily minimizing its disadvantages.It reports improved performance relative to both independence and inappropriate use of independence-based methods on dependent data.
2. Sparse signal model and review of HC.
The paper studies testing for sparse, faint signals in a high-dimensional Gaussian model and reviews higher criticism’s optimal adaptivity in uncorrelated noise. The detection boundary separates detectable from undetectable signal regimes, while HC adapts to unknown sparsity and strength.
- 2. Sparse signal model and review of HC.: The model tests whether an n-dimensional Gaussian mean vector is zero or contains a sparse, faint signal with known unit-diagonal covariance.The correlated case arises when observations are closely spaced in time or space and also relates to global testing in linear models.
- 2. Sparse signal model and review of HC.: Signal sparsity is represented by m nonzero coordinates, while signal strength is represented by A_n; increasing either makes detection easier.The paper mainly assumes randomly located signals with common magnitude, while allowing related signal-strength variations.
- 2. Sparse signal model and review of HC.: The detection boundary r = ρ*(β) divides the β–r plane into detectable and undetectable regions.Below the boundary no test reliably separates the hypotheses, whereas above it reliable detection is possible.
- 2.3. Higher criticism and its optimal adaptivity in the uncorrelated case: Higher criticism uses ordered marginal p-values to detect many statistically significant results without requiring known sparsity or signal strength.The statistic is built from standardized deviations of ordered p-values from their null behavior.
- 2.3. Higher criticism and its optimal adaptivity in the uncorrelated case: For r > ρ*(β), higher criticism has asymptotically full power throughout the detectable region and adapts to unknown β and r.This is the optimal adaptivity established for the uncorrelated case.
- 2. Sparse signal model and review of HC.: In correlated noise, the exact detection boundary may depend on Σ_n in a complicated way, motivating separate lower and upper bounds.The paper then introduces iHC to obtain the upper bound.
3. Lower bound to detectability.
The lower-bound analysis compares correlated Gaussian experiments through added noise and exploits polynomial off-diagonal decay of covariance matrices. It yields a correlation-dependent lower bound on the detection boundary, below which reliable testing is impossible.
- 3.1. Comparison of experiments: Adding noise makes inference harder.: The lower-bound proof uses comparison of experiments, where adding noise makes inference more difficult by reducing separation between null and alternative distributions.The argument measures this reduction using distances such as Hellinger or χ2 distance.
- 3.1. Comparison of experiments: Adding noise makes inference harder.: If Σ* ≥ Σ in positive-semidefinite order, the model with covariance Σ* can be viewed as the model with covariance Σ plus independent Gaussian noise.This representation supports comparing detection difficulty across covariance structures.
- 3.2. Matrices with polynomial off-diagonal decay: For matrices with polynomial off-diagonal decay, the inverse and Cholesky factorization inherit the same decay rate under mild conditions.This matrix property makes the transformed correlated-noise problem analyzable.
- 3.3. Lower bound to detectability.: In correlated settings, replacing the independence boundary by r < γ̄_0^-1ρ*(β) provides a lower bound on the detection boundary.Below this bound, the null and alternative merge asymptotically and every test’s total type I and II errors converge to 1.
- 3.3. Lower bound to detectability.: The upper-bound analysis adapts higher criticism to correlated noise by constructing innovated higher criticism.This provides the route toward matching the lower bound in settings such as Toeplitz covariance.
4. Innovated higher criticism, upper bound to detectability.
Innovated higher criticism incorporates correlation through innovations, transforming correlated observations so signals become stronger and detection can improve. The resulting procedure establishes upper-bound results and is optimal in Toeplitz settings, while bandwidth selection balances signal amplification against induced noise correlation.
- Motivation: Standard higher criticism neglects correlation structure, motivating innovated higher criticism (iHC), which incorporates correlation through innovations.The construction is connected to the time-series notion of innovation.
- Innovation transform: For a positive definite Σn, Un is defined as the inverse of its Cholesky factorization and satisfies UnΣnU′n = In.This transformation converts the correlated noise into an uncorrelated form.
- Signal strengthening: After innovation transformation, the signal coordinates are expected to retain at least m entries of size An, making correlated-noise detection easier than uncorrelated-noise detection.Applying standard HC to UnX therefore yields greater power than applying it directly to X.
- Innovated higher criticism: The proposed iHC further transforms signal clusters into singletons, trading fewer signals for stronger individual signals because HC is more sensitive to strength than count.The construction bands Un and then normalizes each column of the banded matrix.
- Bandwidth choice: Choosing bandwidth bn trades stronger signals against stronger noise correlation; logarithmically large bn is usually appropriate under polynomial off-diagonal decay.The banded normalized matrix has bandwidth 2bn −1.
- Detectability: In Toeplitz cases, the lower and upper detection bounds coincide, establishing iHC as optimal across settings ranging from weak to strong dependence.The paper also reports an upper-bound result for iHC under stated correlation conditions.
- Scope and estimation: Estimating Σn can inhibit applications such as genomic analysis when information outside the dataset is unavailable.The paper notes that low overall genomic correlation may nevertheless support working under an independence assumption.
5. Application in the Toeplitz case.
For Toeplitz correlation matrices generated by suitable spectral densities, innovated higher criticism achieves the optimal detection boundary, which is improved relative to independence by a factor determined by C(f).
- Model: The Toeplitz model uses a truncated Toeplitz correlation matrix generated by a symmetric, positive spectral density f.Its entries are Fourier coefficients of f, and regularity assumptions provide convenient asymptotic properties.
- Asymptotic structure: The inverse of Σn(f) is typically asymptotically equivalent to the Toeplitz matrix generated by 1/f.This relation supports the analysis of the innovated procedure in the Toeplitz setting.
- Detection boundary: When C(f)·r < ρ∗(β), the null and alternative hypotheses merge asymptotically, and every test has type-I plus type-II error tending to 1.This establishes the lower boundary for detection.
- Detection boundary: When C(f)·r > ρ∗(β), iHC with bandwidth bn = log n has type-I error tending to zero and power tending to 1.The rejection rule uses an iHC threshold of (log n)2.
- Phase diagram: The curve r = C(f)^−1ρ∗(β) partitions the β–r plane into undetectable and detectable regions, squeezing the uncorrelated diagram vertically by 1/C(f).C(f) ≥ 1, with equality only for f ≡ 1, the uncorrelated case.
6. Extension: When signals appear in clusters.
The paper extends innovated higher criticism to signals occurring in clusters rather than isolated locations, representing cluster structure through shifted signal vectors and a lower triangular Toeplitz operator.
- Motivation: The extension allows signals to appear in clusters instead of as isolated singletons.The preceding model places signal locations randomly, while the clustered model investigates groups of consecutive signals.
- Cluster model: Each of m randomly located clusters contains K consecutive signals with strengths g0An, g1An, ..., gK−1An.Here K is fixed and An = √(2r log n).
- Cluster model: The cluster signal vector is constructed from a base sparse vector and its backward shifts using the matrix B.B shifts components one position backward, with zero added at the bottom.
- Cluster model: The function g(θ) = Σ0≤k≤K−1 gkBk defines a lower triangular Toeplitz matrix encoding the within-cluster signal profile.This operator combines the shifted copies with coefficients gk.
- Detection boundary: For the general clustered model, the expected detection boundary is r = C(f,g)^−1·ρ∗(β).The theorem uses C(f,g)·r relative to ρ∗(β): below it hypotheses merge, while above it iHC achieves vanishing type-I error and power tending to 1.
7. The case of strong dependence.
Under strong dependence, the paper analyzes a restricted slowly decaying correlation model, decomposes its correlation matrix into tractable factors, and derives a detection boundary characterized by C(fα,g0).
- Setting: The strong-dependence setting considers Gaussian observations with slowly decaying correlation and randomly located sparse signals.The dependence range is parameterized by α and α0 through k0 ≈ n^(α0/α).
- Setting: The strong-dependence correlation model is more restrictive because its boundary constants depend on α and positive definiteness is delicate for more general matrices.These conditions constrain the scope of the strong-dependence analysis.
- Motivation: Standard HC has seriously damaged detectability under strong dependence, while the paper addresses the corresponding boundary and an adaptive procedure.The strong-dependence section targets optimal detection where prior work left the boundary and adaptation open.
- Method: The key method decomposes the correlation matrix into three relatively tractable matrices and transforms the data using a lower triangular Toeplitz factor and diagonal scaling.The transformed covariance is asymptotically equivalent to a Toeplitz matrix generated by fα.
- Results: The strong-dependence model has detection boundary C(fα,g0)·r = ρ∗(β): below it hypotheses merge, while above it iHC has type-I error tending to zero and power tending to 1.The signal strength is re-scaled before applying this characterization.
8. Simulation study.
The simulation study compares standard HC with two innovated-HC bandwidth choices across correlated Gaussian signal-detection settings. Across experiments, iHC-b generally outperforms iHC-a, which outperforms HC, with stronger correlation increasing the advantage of iHC.
- Experimental setup: The study compares standard HC with iHC using bandwidths b_n = 1 and b_n = log n, denoted HC, HC-a, and HC-b.Data are generated from sparse Gaussian signals added to correlated Gaussian noise.
- Experiment (a): Experiment (a) varies ρ from −0.45 to 0.45 across four (β,r) settings and repeats each procedure 500 times under null and alternative hypotheses.The procedures are evaluated using simulated HC scores for both hypotheses.
- Evaluation: Results are summarized by minimum sums of type I and II errors and empirical power using the upper 10% null-score percentile as threshold.The asymptotic (log n)^2 cut-off is described as conservative for moderately large n, motivating empirical thresholds.
- Results: iHC-b outperforms iHC-a, and iHC-a outperforms HC; the advantage of iHC becomes more prominent as |ρ| increases.Under the null, HC-b scores are usually smaller, mainly because of its normalization term.
- Additional experiments: Experiment (b) with a Toeplitz covariance generated by f(θ) = 1 + 2 cos(θ) + 2ρcos(2θ) yields the same ordering in minimum error sums.Experiment (c) reports improving performance as n increases, up to n = 2500.
9. Discussion.
The discussion interprets innovated HC as an optimal procedure that incorporates correlation through the inverse covariance structure. For Toeplitz covariance matrices, the detection boundary is characterized exactly, while broader covariance settings and applications remain open directions.
- Main contribution: Innovated HC builds the correlation structure into higher criticism, with extreme diagonal entries of Σ_n^-1 playing a key role.The procedure is designed for correlated-noise testing rather than applying standard HC unchanged.
- Detection boundary: For Toeplitz correlation matrices, the detection-boundary limits merge at the Wiener interpolation rate C(f), giving r = C(f)^-1 · ρ*(β).Innovated HC has asymptotically full power in the interior of the detectable region.
- Detection boundary: The detection boundary partitions the β–r plane into detectable and undetectable regions, and iHC is asymptotically optimal for detection in the supported Toeplitz setting.Neither β nor r is used to construct iHC.
- Relation to prior work: Relative to prior work, the paper addresses how correlation can be exploited, whereas earlier studies examined standard HC under independent or dependent noise without this remedy.The authors state that innovated HC is optimal for both referenced models.
- Extensions and scope: The approach may extend to feature selection and to settings where covariance matrices can be estimated accurately under polynomial off-diagonal decay.Sparse, unspecified covariance patterns remain more challenging because less is known about their inverses.
10. Proofs of main results.
The proofs establish the main results by comparing correlated-noise models through Hellinger distance and transformed, banded representations. They also show that higher criticism can retain asymptotic detection power under the stated sparse-signal conditions.
- Proof strategy: The matrix comparison is reduced to proving ˜U′˜U ≤ (1 −δ)^−1Σ and showing that the associated Hellinger distance tends to zero.The required matrix inequality follows from bounds on the truncation error and eigenvalues.
- Proof strategy: The transformed model uses a banded matrix and sparse signals whose nonzero coordinates form disjoint clusters of size O(log^2 n).The banded structure and separated signal locations simplify the Hellinger-distance calculation.
- Higher-criticism results: When the transformed signals are denser and stronger than a randomly located equal-strength configuration, standard higher criticism is no less powerful asymptotically.The comparison uses the monotone likelihood-ratio property of noncentral χ^2 distributions.
- Higher-criticism results: Under the null, the higher-criticism statistic has rejection probability tending to zero as n diverges to infinity.The argument uses convergence of the normalized statistic and control of the second term in the relevant bound.
- Scope extension: The proof framework extends beyond correlation matrices with equal diagonal entries to weaker decay conditions on the inverse Cholesky factor.The resulting matrix approximation error is shown to vanish asymptotically.
A.1. Statement and proof of Lemma A.1.
Lemma A.1 establishes polynomial off-diagonal decay for covariance inverses and inverse Cholesky factors when the covariance matrices belong to the specified class.
- Lemma statement: For λ > 1, inverse covariance entries decay as C · (1 + |j −k|)^−λ.The bound holds uniformly over indices j and k.
- Lemma statement: The inverse Cholesky factor U_n satisfies the same polynomial decay bound.The proof uses finite principal submatrices and direct row calculations.
- Boundary case: When λ = 1, the inverse bound remains valid, while the U_n bound requires an additional log n factor.This marks the boundary of the stated decay result.
A.2. Statement and proof of Lemma A.3.
Lemma A.3 controls the locations and interactions of randomly placed sparse signals, using polynomial decay to show that distant signal contributions are algebraically small.
- Signal spacing: With asymptotically vanishing exception probability, signal locations remain away from the boundaries and are separated by at least C log n·n^(2β−1).The proof restricts attention to configurations satisfying these spacing conditions.
- Interaction control: Polynomial off-diagonal decay makes contributions from separated signal locations algebraically small.The resulting bounds control the off-diagonal terms in the transformed model.
- Interaction control: The diagonal quantities Σ^−1(k,k) are uniformly bounded away from zero and infinity.These bounds are combined with decay estimates to complete the lemma’s calculations.
A.3. Statement and proof of Lemma A.4.
Lemma A.4 and its supporting lemmas control empirical survival processes and transformed Gaussian models under sparse dependence. The results establish negligible approximation errors and asymptotically vanishing Hellinger distances in the relevant regimes.
- Empirical-process control: The normalized empirical survival process is controlled through a Brownian-bridge approximation and tail bounds.The proof combines the approximation with the triangle inequality.
- Empirical-process control: A bandwidth-logarithm decomposition partitions dependent transformed coordinates into 2b_n −1 subsets whose members are independent.Each subset contains N = n/(2b_n −1) observations, enabling empirical-process bounds.
- Matrix approximation: The spectral norm of ˜Σ_n − ¯Σ_n tends to zero as n tends to infinity.The bound follows from decomposing the difference into matrix components and controlling their matrix norms.
- Sparse-location control: Random signal locations lie in the admissible separated set with probability 1 − O((log n)^2 n^(1−2β)).Thus the excluded configurations have asymptotically vanishing probability.
- Hellinger control: For the banded transformed model, E(W_n 1{D_n}) = 1 + o(1) and E(W_n^2 1{D_n}) = 1 + o(1).These moment relations support the Hellinger-distance approximation.
- Hellinger control: Under the theorem conditions, the relevant Hellinger-distance bound converges to zero algebraically fast.This completes the stated asymptotic claim for the transformed model.
- Covariance conditions: Positive definiteness of the covariance sequence requires 0 ≤ α ≤ 2 and 0 < α_0 ≤ α ≤ 1 in the respective cases.These conditions are stated as necessary and sufficient for sufficiently large n.