Computational and statistical boundaries for submatrix localization in a large noisy matrix
From MaRDI portal
Publication:2403425
DOI10.1214/16-AOS1488zbMath1392.62017arXiv1502.01988OpenAlexW3101407508MaRDI QIDQ2403425
T. Tony Cai, Tengyuan Liang, Alexander Rakhlin
Publication date: 8 September 2017
Published in: The Annals of Statistics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1502.01988
minimaxcomputational complexitylower boundssignal-to-noise ratiodetectionplanted cliquesubmatrix localizationcomputational boundarystatistical boundary
Related Items
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 ⋮ Compressed spectral screening for large-scale differential correlation analysis with application in selecting glioblastoma gene modules ⋮ Statistical and computational limits for sparse matrix detection ⋮ Parallel tempering for the planted clique problem ⋮ Submatrix localization via message passing ⋮ Distribution-Free, Size Adaptive Submatrix Detection with Acceleration ⋮ The Sup-norm Perturbation of HOSVD and Low Rank Tensor Denoising ⋮ The overlap gap property in principal submatrix recovery ⋮ A sieve stochastic gradient descent estimator for online nonparametric regression in Sobolev ellipsoids
