Computational barriers in minimax submatrix detection

DOI10.1214/14-AOS1300zbMath1328.62354arXiv1309.5914MaRDI QIDQ2352736

Yihong Wu, Zongming Ma

Publication date: 6 July 2015

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

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

zbMATH Keywords

computational complexityhigh-dimensional statisticsminimax rateasymptotic equivalenceplanted cliquesubmatrix detection

Mathematics Subject Classification ID

Hypothesis testing in multivariate analysis (62H15) Minimax procedures in statistical decision theory (62C20)

Related Items (26)

Isotonic regression with unknown permutations: statistics, computation and adaptation ⋮ Tensor clustering with planted structures: statistical optimality and computational limits ⋮ Computational barriers to estimation from low-degree polynomials ⋮ Distribution-free detection of a submatrix ⋮ Estimation of Wasserstein distances in the spiked transport model ⋮ A goodness-of-fit test on the number of biclusters in a relational data matrix ⋮ Statistical and computational limits for sparse matrix detection ⋮ Estimation of Monge matrices ⋮ Phase transitions for detecting latent geometry in random graphs ⋮ Optimal rates of statistical seriation ⋮ Notes on computational-to-statistical gaps: predictions using statistical physics ⋮ Comment on ``Hypothesis testing by convex optimization ⋮ Parallel tempering for the planted clique problem ⋮ The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs ⋮ Submatrix localization via message passing ⋮ Optimal testing for planted satisfiability problems ⋮ Distribution-Free, Size Adaptive Submatrix Detection with Acceleration ⋮ ECA: High-Dimensional Elliptical Component Analysis in Non-Gaussian Distributions ⋮ The Sup-norm Perturbation of HOSVD and Low Rank Tensor Denoising ⋮ Minimax rates in network analysis: graphon estimation, community detection and hypothesis testing ⋮ Optimality and sub-optimality of PCA. I: Spiked random matrix models ⋮ The overlap gap property in principal submatrix recovery ⋮ Optimal adaptivity of signed-polygon statistics for network testing ⋮ A Unifying Tutorial on Approximate Message Passing ⋮ A sieve stochastic gradient descent estimator for online nonparametric regression in Sobolev ellipsoids ⋮ Computational barriers in minimax submatrix detection

Uses Software

• LAS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimal detection of sparse principal components in high dimension
• On combinatorial testing problems
• Nuclear norm minimization for the planted clique and biclique problems
• Community detection in sparse random networks
• Finding hidden cliques of size \(\sqrt{N/e}\) in nearly linear time
• Finding large average submatrices in high dimensional data
• Asymptotic methods in statistical decision theory
• Expected complexity of graph partitioning problems
• Hiding cliques for cryptographic security
• On the maximal size of large-average and ANOVA-fit submatrices in a Gaussian random matrix
• Computational barriers in minimax submatrix detection
• Do semidefinite relaxations solve sparse PCA up to the information limit?
• Energy landscape for large average submatrix detection problems in Gaussian random matrices
• Detection of a sparse submatrix of a high-dimensional noisy matrix
• Exact matrix completion via convex optimization
• Public-key cryptography from different assumptions
• Hidden Cliques and the Certification of the Restricted Isometry Property
• How Hard Is It to Approximate the Best Nash Equilibrium?
• On the dimension and entropy of probability distributions
• Large Cliques Elude the Metropolis Process
• Statistical Experiments and Decisions
• Finding and certifying a large hidden clique in a semirandom graph
• Computational and statistical tradeoffs via convex relaxation
• Computational Complexity
• Finding Hidden Cliques in Linear Time with High Probability
• Elements of Information Theory
• Statistical algorithms and a lower bound for detecting planted cliques
• The Existence of Probability Measures with Given Marginals

This page was built for publication: Computational barriers in minimax submatrix detection