Tensor clustering with planted structures: statistical optimality and computational limits
From MaRDI portal
Publication:2119244
DOI10.1214/21-AOS2123zbMath1486.62187arXiv2005.10743OpenAlexW3026325780MaRDI QIDQ2119244
Publication date: 23 March 2022
Published in: The Annals of Statistics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2005.10743
average-case complexityhigh-order clusteringhypergraphic planted cliquehypergraphic planted dense subgraphstatistical-computational phase transition
Computational methods for problems pertaining to statistics (62-08) Classification and discrimination; cluster analysis (statistical aspects) (62H30) Hypothesis testing in multivariate analysis (62H15) Random graphs (graph-theoretic aspects) (05C80) Minimax procedures in statistical decision theory (62C20)
Related Items
Inference for low-rank tensors -- no need to debias ⋮ Sharp detection boundaries on testing dense subhypergraph ⋮ Generalized Low-Rank Plus Sparse Tensor Estimation by Fast Riemannian Optimization ⋮ Long random matrices and tensor unfolding
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Tensor Decompositions and Applications
- Statistical and computational trade-offs in estimation of sparse principal components
- Optimal detection of sparse principal components in high dimension
- Consistency of spectral hypergraph partitioning under planted partition model
- Nuclear norm minimization for the planted clique and biclique problems
- Finding one community in a sparse graph
- Community detection in sparse random networks
- Finding hidden cliques of size \(\sqrt{N/e}\) in nearly linear time
- Sparse CCA: adaptive estimation and computational barriers
- On the maximal size of large-average and ANOVA-fit submatrices in a Gaussian random matrix
- Statistical limits of spiked tensor models
- Statistical and computational limits for sparse matrix detection
- Three-way clustering of multi-tissue multi-individual gene expression data using semi-nonnegative tensor decomposition
- 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
- Biclustering in data mining
- Community detection in dense random networks
- Rank-One Approximation to High Order Tensors
- Sharp variable selection of a sparse submatrix in a high-dimensional noisy matrix
- Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices
- High-Dimensional Covariance Decomposition into Sparse Markov and Independence Models
- Sum-of-squares Lower Bounds for Planted Clique
- Incoherence-Optimal Matrix Completion
- Hidden Cliques and the Certification of the Restricted Isometry Property
- Large Cliques Elude the Metropolis Process
- Cliques in random graphs
- A Multilinear Singular Value Decomposition
- On the Best Rank-1 and Rank-(R1 ,R2 ,. . .,RN) Approximation of Higher-Order Tensors
- Tensor SVD: Statistical and Computational Limits
- Minimizing the Union: Tight Approximations for Small Set Bipartite Vertex Expansion
- On the Complexity of Random Satisfiability Problems with Planted Solutions
- Finding Planted Subgraphs with Few Eigenvalues using the Schur--Horn Relaxation
- A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem
- Statistical Algorithms and a Lower Bound for Detecting Planted Cliques
- Finding and certifying a large hidden clique in a semirandom graph
- The Average-Case Time Complexity of Certifying the Restricted Isometry Property
- HIGH DIMENSIONAL ESTIMATION VIA SUM-OF-SQUARES PROOFS
- Computational and statistical tradeoffs via convex relaxation
- Optimal Sparse Singular Value Decomposition for High-Dimensional High-Order Data
- Efficient Algorithms and Lower Bounds for Robust Linear Regression
- Convex biclustering
- The Sup-norm Perturbation of HOSVD and Low Rank Tensor Denoising
- Most Tensor Problems Are NP-Hard
- Finding Hidden Cliques in Linear Time with High Probability
- The Monotone Complexity of $k$-Clique on Random Graphs
- Provable Sparse Tensor Decomposition
- Limits of local algorithms over sparse random graphs
