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

DOI10.3150/12-BEJ470zbMath1457.62072arXiv1109.0898MaRDI QIDQ2435256

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

random matricesminimax testingdetection of sparse signalminimax adaptive testingsharp detection bounds

Mathematics Subject Classification ID

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

Related Items (37)

Tensor clustering with planted structures: statistical optimality and computational limits ⋮ Energy landscape for large average submatrix detection problems in Gaussian random matrices ⋮ 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 two-component Gaussian mixtures detection ⋮ Distribution-free detection of a submatrix ⋮ Optimal detection of sparse principal components in high dimension ⋮ Optimal change point detection in Gaussian processes ⋮ The sparse Poisson means model ⋮ Sharp detection boundaries on testing dense subhypergraph ⋮ 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 ⋮ Community detection in sparse random networks ⋮ Testing correlation of unlabeled random graphs ⋮ Detecting structured signals in Ising models ⋮ 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 ⋮ To the memory of Yu. I. Ingster ⋮ Detection of a sparse variable function ⋮ Adaptive sensing performance lower bounds for sparse signal detection and support estimation ⋮ Comment on ``Hypothesis testing by convex optimization ⋮ Multiscale scanning in inverse problems ⋮ Submatrix localization via message passing ⋮ Optimal testing for planted satisfiability problems ⋮ Distribution-Free, Size Adaptive Submatrix Detection with Acceleration ⋮ Sharp variable selection of a sparse submatrix in a high-dimensional noisy matrix ⋮ Community detection in dense random networks ⋮ Detecting a planted community in an inhomogeneous random graph ⋮ Optimality and sub-optimality of PCA. I: Spiked random matrix models ⋮ Sparse Sliced Inverse Regression Via Lasso ⋮ High-dimensional change-point detection under sparse alternatives ⋮ The overlap gap property in principal submatrix recovery ⋮ Optimal inference with a multidimensional multiscale statistic ⋮ Computational barriers in minimax submatrix detection ⋮ Higher criticism for large-scale inference, especially for rare and weak effects

Uses Software

• LAS

Cites Work

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

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