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.
The focus of the paper is to understand the fundamental limits of detecting sparse matrices from both the statistical and computational perspectives. While achieving the optimal estimation rates does not suffer from any computational barrier, it turns out the detection counterpart does when and only when the sparsity level exceeds the cubic root of the matrix size. The main result is a tight characterization of the statistical and computational limits of detecting sparse matrices in both the Gaussian noise model and the covariance matrix model, which precisely describe when achieving optimal detection is easy hard and impossible, respectively.
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
- 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?
- 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?)
- 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 thresholds for the \(\beta\)-model on sparse graphs
- Detection boundary in sparse regression
- Tensor clustering with planted structures: statistical optimality and computational limits
- MAP and Bayes tests in sparse vectors detection
- Computational barriers to estimation from low-degree polynomials
- Connection between the selection problem for a sparse submatrix of a large-size matrix and the Bayesian problem of hypotheses testing
- Computational barriers in minimax submatrix detection
- Computational and statistical boundaries for submatrix localization in a large noisy matrix
- Detection of a sparse submatrix of a high-dimensional noisy matrix
- Detecting the large entries of a sparse covariance matrix in sub-quadratic time
- Sharp detection of smooth signals in a high-dimensional sparse matrix with indirect observations
- A goodness-of-fit test on the number of biclusters in a relational data matrix
- Overparameterized maximum likelihood tests for detection of sparse vectors
- Optimal estimation and computational limit of low-rank Gaussian mixtures
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)
