Detection of a sparse submatrix of a high-dimensional noisy matrix

DOI10.3150/12-BEJ470MaRDI QIDQ2435256zbMATH OpenFDO

Authors Cristina Butucea, Yuri I. Ingster

Publication date 4 February 2014

Published in Bernoulli (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1109.0898

zbMATH Keywords

detection of sparse signalminimax adaptive testingminimax testingrandom matricessharp detection bounds

Mathematics Subject Classification ID

Signal detection and filtering (aspects of stochastic processes) (60G35) Minimax procedures in statistical decision theory (62C20) Parametric hypothesis testing (62F03) Estimation in multivariate analysis (62H12) Hypothesis testing in multivariate analysis (62H15) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: We observe a $NimesM$ matrix $Y_{ij}=s_{ij}+x{i}_{ij}$ with $x{i}_{ij}simmathcalN(0,1)$ i.i.d. in $i,j$, and $s_{ij}inmathbbR$. We test the null hypothesis $s_{ij}=0$ for all $i,j$ against the alternative that there exists some submatrix of size $nimesm$ with significant elements in the sense that $s_{ij}gea>0$. We propose a test procedure and compute the asymptotical detection boundary $a$ so that the maximal testing risk tends to 0 as $Moinfty$, $Noinfty$, $p=n/No0$, $q=m/Mo0$. We prove that this boundary is asymptotically sharp minimax under some additional constraints. Relations with other testing problems are discussed. We propose a testing procedure which adapts to unknown $(n,m)$ within some given set and compute the adaptive sharp rates. The implementation of our test procedure on synthetic data shows excellent behavior for sparse, not necessarily squared matrices. We extend our sharp minimax results in different directions: first, to Gaussian matrices with unknown variance, next, to matrices of random variables having a distribution from an exponential family (non-Gaussian) and, finally, to a two-sided alternative for matrices with Gaussian elements.

Recommendations

• Sharp detection of smooth signals in a high-dimensional sparse matrix with indirect observations
• Sharp variable selection of a sparse submatrix in a high-dimensional noisy matrix
• Distribution-free, size adaptive submatrix detection with acceleration
• Statistical and computational limits for sparse matrix detection
• Connection between the selection problem for a sparse submatrix of a large-size matrix and the Bayesian problem of hypotheses testing

Cites work

• Detection of a signal of known shape in a multichannel system
• Detection of an anomalous cluster in a network
• Finding large average submatrices in high dimensional data
• Global testing under sparse alternatives: ANOVA, multiple comparisons and the higher criticism
• Higher criticism for detecting sparse heterogeneous mixtures.
• Near-Optimal Detection of Geometric Objects by Fast Multiscale Methods
• Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion
• On combinatorial testing problems
• On the maximal size of large-average and ANOVA-fit submatrices in a Gaussian random matrix
• Simultaneous analysis of Lasso and Dantzig selector
• Some problems of hypothesis testing leading to infinitely divisible distributions

Cited in

(50)

• Sparse sliced inverse regression via Lasso
• Multidimensional two-component Gaussian mixtures detection
• Optimal change point detection in Gaussian processes
• Optimality and sub-optimality of PCA. I: Spiked random matrix models
• Multiscale scanning in inverse problems
• Detecting a planted community in an inhomogeneous random graph
• The overlap gap property in principal submatrix recovery
• Optimal inference with a multidimensional multiscale statistic
• Tensor clustering with planted structures: statistical optimality and computational limits
• Uniform estimation in stochastic block models is slow
• Fast nonasymptotic testing and support recovery for large sparse Toeplitz covariance matrices
• Computational barriers to estimation from low-degree polynomials
• Multidimensional multiscale scanning in exponential families: limit theory and statistical consequences
• Statistical and computational limits for sparse matrix detection
• Connection between the selection problem for a sparse submatrix of a large-size matrix and the Bayesian problem of hypotheses testing
• Optimal testing for planted satisfiability problems
• High-dimensional change-point detection under sparse alternatives
• Computational barriers in minimax submatrix detection
• Energy landscape for large average submatrix detection problems in Gaussian random matrices
• Distribution-free detection of a submatrix
• Community detection in dense random networks
• Higher criticism for large-scale inference, especially for rare and weak effects
• Sharp detection boundaries on testing dense subhypergraph
• Sharp variable selection of a sparse submatrix in a high-dimensional noisy matrix
• Optimal detection of sparse principal components in high dimension
• A simple filter for detecting low-rank submatrices
• Submatrix localization via message passing
• Adaptive sensing performance lower bounds for sparse signal detection and support estimation
• Comment on ``Hypothesis testing by convex optimization
• Sharp detection of smooth signals in a high-dimensional sparse matrix with indirect observations
• Distribution-free, size adaptive submatrix detection with acceleration
• Recognizing linear structure in noisy matrices
• A goodness-of-fit test on the number of biclusters in a relational data matrix
• Free Energy Wells and Overlap Gap Property in Sparse PCA
• Testing correlation of unlabeled random graphs
• Detecting structured signals in Ising models
• Computational lower bounds for graphon estimation via low-degree polynomials
• Heterogeneous dense subhypergraph detection
• Sharp phase transitions in high-dimensional changepoint detection
• Sparse anomaly detection across referentials: a rank-based higher criticism approach
• Exact variable selection in sparse nonparametric models
• Detection of dense subhypergraphs by low-degree polynomials
• Analysis of singular subspaces under random perturbations
• Testing for latent structure via the Wilcoxon-Wigner random matrix of normalized rank statistics
• Pseudo-maximum likelihood theory for high-dimensional rank one inference
• Finding nonoverlapping substructures of a sparse matrix
• The sparse Poisson means model
• Community detection in sparse random networks
• To the memory of Yu. I. Ingster
• Detection of a sparse variable function

Describes a project that uses

Uses Software

• LAS

This page was built for publication: Detection of a sparse submatrix of a high-dimensional noisy matrix

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2435256)