Statistical and computational limits for sparse matrix detection
From MaRDI portal
Publication:2196237
Abstract: This paper investigates the fundamental limits for detecting a high-dimensional sparse matrix contaminated by white Gaussian noise from both the statistical and computational perspectives. We consider matrices whose rows and columns are individually -sparse. We provide a tight characterization of the statistical and computational limits for sparse matrix detection, which precisely describe when achieving optimal detection is easy, hard, or impossible, respectively. Although the sparse matrices considered in this paper have no apparent submatrix structure and the corresponding estimation problem has no computational issue at all, the detection problem has a surprising computational barrier when the sparsity level exceeds the cubic root of the matrix size : attaining the optimal detection boundary is computationally at least as hard as solving the planted clique problem. The same statistical and computational limits also hold in the sparse covariance matrix model, where each variable is correlated with at most others. A key step in the construction of the statistically optimal test is a structural property for sparse matrices, which can be of independent interest.
Recommendations
- Computational barriers in minimax submatrix detection
- Optimal detection of sparse principal components in high dimension
- Detection of a sparse submatrix of a high-dimensional noisy matrix
- Optimal estimation and rank detection for sparse spiked covariance matrices
- Computational and statistical boundaries for submatrix localization in a large noisy matrix
Cites work
- scientific article; zbMATH DE number 5485485 (Why is no real title available?)
- scientific article; zbMATH DE number 1380608 (Why is no real title available?)
- scientific article; zbMATH DE number 961607 (Why is no real title available?)
- Asymptotic power of sphericity tests for high-dimensional data
- Community detection in dense random networks
- Computational and statistical boundaries for submatrix localization in a large noisy matrix
- Computational barriers in minimax submatrix detection
- Covariance regularization by thresholding
- Detecting positive correlations in a multivariate sample
- Detection of a sparse submatrix of a high-dimensional noisy matrix
- Detection of correlations
- Estimation of functionals of sparse covariance matrices
- Estimation of matrices with row sparsity
- Global testing under sparse alternatives: ANOVA, multiple comparisons and the higher criticism
- Higher criticism for detecting sparse heterogeneous mixtures.
- How Hard Is It to Approximate the Best Nash Equilibrium?
- Large Cliques Elude the Metropolis Process
- Local operator theory, random matrices and Banach spaces.
- Near-Optimal Detection of Geometric Objects by Fast Multiscale Methods
- Nonparametric goodness-of-fit testing under Gaussian models
- Operator norm consistent estimation of large-dimensional sparse covariance matrices
- Optimal detection of heterogeneous and heteroscedastic mixtures
- Optimal detection of sparse principal components in high dimension
- Optimal estimation and rank detection for sparse spiked covariance matrices
- Optimal hypothesis testing for high dimensional covariance matrices
- Optimal rates of convergence for sparse covariance matrix estimation
- Oracle inequalities and optimal inference under group sparsity
- Rate Optimal Denoising of Simultaneously Sparse and Low Rank Matrices
- Refinements of Pinsker's inequality
- Robust principal component analysis?
- Sampling from large matrices
- Searching for a trail of evidence in a maze
- Signal detection in high dimension: the multispiked case
- Some problems of hypothesis testing leading to infinitely divisible distributions
- Sparse CCA: adaptive estimation and computational barriers
- Sparse PCA: optimal rates and adaptive estimation
- Statistical algorithms and a lower bound for detecting planted cliques
- Statistical and computational trade-offs in estimation of sparse principal components
- Tests for high-dimensional covariance matrices
- Volume Ratio, Sparsity, and Minimaxity Under Unitarily Invariant Norms
Cited in
(14)- Detection boundary in sparse regression
- Overparameterized maximum likelihood tests for detection of sparse vectors
- Tensor clustering with planted structures: statistical optimality and computational limits
- Computational barriers in minimax submatrix detection
- Sharp detection of smooth signals in a high-dimensional sparse matrix with indirect observations
- Detecting the large entries of a sparse covariance matrix in sub-quadratic time
- MAP and Bayes tests in sparse vectors detection
- Optimal estimation and computational limit of low-rank Gaussian mixtures
- Detection of a sparse submatrix of a high-dimensional noisy matrix
- A goodness-of-fit test on the number of biclusters in a relational data matrix
- Computational barriers to estimation from low-degree polynomials
- Detection thresholds for the \(\beta\)-model on sparse graphs
- Computational and statistical boundaries for submatrix localization in a large noisy matrix
- Connection between the selection problem for a sparse submatrix of a large-size matrix and the Bayesian problem of hypotheses testing
This page was built for publication: Statistical and computational limits for sparse matrix detection
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2196237)
