Statistical and computational limits for sparse matrix detection

DOI10.1214/19-AOS1860zbMATH Open1453.62285arXiv1801.00518MaRDI QIDQ2196237FDOQ2196237

Authors: Yanyan Li 

Publication date: 28 August 2020

Published in: The Annals of Statistics (Search for Journal in Brave)

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 $pimesp$ matrices whose rows and columns are individually $k$-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 $k$ exceeds the cubic root of the matrix size $p$: 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 $k$ 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.

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

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

zbMATH Keywords

sparse covariance matrixminimax ratessparse detectioncomputational limits

Mathematics Subject Classification ID

Computational methods for problems pertaining to statistics (62-08) Estimation in multivariate analysis (62H12) Hypothesis testing in multivariate analysis (62H15) Minimax procedures in statistical decision theory (62C20)

Cites Work

• Title not available (Why is that?)
• Global testing under sparse alternatives: ANOVA, multiple comparisons and the higher criticism
• Covariance regularization by thresholding
• Some problems of hypothesis testing leading to infinitely divisible distributions
• Higher criticism for detecting sparse heterogeneous mixtures.
• Optimal hypothesis testing for high dimensional covariance matrices
• Robust principal component analysis?
• Local operator theory, random matrices and Banach spaces.
• Operator norm consistent estimation of large-dimensional sparse covariance matrices
• Nonparametric goodness-of-fit testing under Gaussian models
• Detecting positive correlations in a multivariate sample
• Sparse PCA: optimal rates and adaptive estimation
• Community detection in dense random networks
• Optimal detection of heterogeneous and heteroscedastic mixtures
• Optimal detection of sparse principal components in high dimension
• Title not available (Why is that?)
• Tests for high-dimensional covariance matrices
• Oracle inequalities and optimal inference under group sparsity
• Optimal rates of convergence for sparse covariance matrix estimation
• Detection of a sparse submatrix of a high-dimensional noisy matrix
• Signal detection in high dimension: the multispiked case
• Asymptotic power of sphericity tests for high-dimensional data
• Refinements of Pinsker's inequality
• Large Cliques Elude the Metropolis Process
• Volume Ratio, Sparsity, and Minimaxity Under Unitarily Invariant Norms
• Near-Optimal Detection of Geometric Objects by Fast Multiscale Methods
• Searching for a trail of evidence in a maze
• Estimation of matrices with row sparsity
• Statistical and computational trade-offs in estimation of sparse principal components
• How Hard Is It to Approximate the Best Nash Equilibrium?
• Title not available (Why is that?)
• Detection of correlations
• Statistical algorithms and a lower bound for detecting planted cliques
• Sampling from large matrices
• Computational barriers in minimax submatrix detection
• Optimal estimation and rank detection for sparse spiked covariance matrices
• Sparse CCA: adaptive estimation and computational barriers
• Estimation of functionals of sparse covariance matrices
• Rate Optimal Denoising of Simultaneously Sparse and Low Rank Matrices
• Computational and statistical boundaries for submatrix localization in a large noisy matrix

Cited In (13)

• Detection boundary in sparse regression
• Overparameterized maximum likelihood tests for detection of sparse vectors
• Computational barriers in minimax submatrix detection
• Tensor clustering with planted structures: statistical optimality and computational limits
• 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
• A goodness-of-fit test on the number of biclusters in a relational data matrix
• Detection of a sparse submatrix of a high-dimensional noisy 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)