Statistical and computational limits for sparse matrix detection

DOI10.1214/19-AOS1860zbMath1453.62285arXiv1801.00518MaRDI QIDQ2196237

Yanyan Li

Publication date: 28 August 2020

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

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

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)

Related Items (3)

Tensor clustering with planted structures: statistical optimality and computational limits ⋮ Computational barriers to estimation from low-degree polynomials ⋮ A goodness-of-fit test on the number of biclusters in a relational data matrix

Cites Work

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

This page was built for publication: Statistical and computational limits for sparse matrix detection