Iterative algorithm for discrete structure recovery
From MaRDI portal
Publication:2131266
DOI10.1214/21-AOS2140zbMath1486.62058arXiv1911.01018OpenAlexW2989055629MaRDI QIDQ2131266
Publication date: 25 April 2022
Published in: The Annals of Statistics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1911.01018
high-dimensional statisticsgroup synchronizationk-means clusteringapproximate rankingmultireference alignment
Classification and discrimination; cluster analysis (statistical aspects) (62H30) Linear regression; mixed models (62J05) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Statistical ranking and selection procedures (62F07)
Related Items (3)
Variable selection, monotone likelihood ratio and group sparsity ⋮ A unified approach to synchronization problems over subgroups of the orthogonal group ⋮ An \({\ell_p}\) theory of PCA and spectral clustering
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Consistency thresholds for the planted bisection model
- SLOPE is adaptive to unknown sparsity and asymptotically minimax
- Minimax rates of community detection in stochastic block models
- The planar \(k\)-means problem is NP-hard
- UPS delivers optimal phase diagram in high-dimensional variable selection
- Statistical guarantees for the EM algorithm: from population to sample-based analysis
- Tightness of the maximum likelihood semidefinite relaxation for angular synchronization
- A local search approximation algorithm for \(k\)-means clustering
- Angular synchronization by eigenvectors and semidefinite programming
- Iterative hard thresholding for compressed sensing
- High-dimensional variable selection
- SLOPE-adaptive variable selection via convex optimization
- NP-hardness of Euclidean sum-of-squares clustering
- On the convergence properties of the EM algorithm
- A proof of the block model threshold conjecture
- Improved bounds for square-root Lasso and square-root slope
- Variable selection with Hamming loss
- Community detection in degree-corrected block models
- Optimality and sub-optimality of PCA. I: Spiked random matrix models
- Slope meets Lasso: improved oracle bounds and optimality
- Singularity, misspecification and the convergence rate of EM
- Minimax rates in network analysis: graphon estimation, community detection and hypothesis testing
- Randomly initialized EM algorithm for two-component Gaussian mixture achieves near optimality in \(O(\sqrt{n})\) iterations
- Optimal rates of estimation for multi-reference alignment
- Entrywise eigenvector analysis of random matrices with low expected rank
- Theoretical and computational guarantees of mean field variational inference for community detection
- A general framework for Bayes structured linear models
- Group synchronization on grids
- Partial recovery bounds for clustering with the relaxed \(K\)-means
- Sup-norm convergence rate and sign concentration property of Lasso and Dantzig estimators
- High-dimensional graphs and variable selection with the Lasso
- Efficient random graph matching via degree profiles
- Minimax rates in permutation estimation for feature matching
- Achieving Exact Cluster Recovery Threshold via Semidefinite Programming: Extensions
- Achieving Exact Cluster Recovery Threshold via Semidefinite Programming
- Exact Recovery in the Stochastic Block Model
- Multireference alignment using semidefinite programming
- Hard Thresholding Pursuit: An Algorithm for Compressive Sensing
- Improved Spectral-Norm Bounds for Clustering
- Finding hidden hamiltonian cycles
- Community structure in social and biological networks
- The Projected Power Method: An Efficient Algorithm for Joint Alignment from Pairwise Differences
- Exponential Error Rates of SDP for Block Models: Beyond Grothendieck’s Inequality
- Minimax Rates and Efficient Algorithms for Noisy Sorting
- Fundamental Limits in Multi-Image Alignment
- Bispectrum Inversion With Application to Multireference Alignment
- Near-Optimal Bounds for Phase Synchronization
- Least squares quantization in PCM
- Information-Theoretic Limits on Sparsity Recovery in the High-Dimensional and Noisy Setting
- Necessary and Sufficient Conditions for Sparsity Pattern Recovery
- The Sample Complexity of Multireference Alignment
- Optimal Variable Selection and Adaptive Noisy Compressed Sensing
- Achieving the Bayes Error Rate in Synchronization and Block Models by SDP, Robustly
- Hidden Hamiltonian Cycle Recovery via Linear Programming
- Multireference Alignment Is Easier With an Aperiodic Translation Distribution
- Nearly Sharp Sufficient Conditions on Exact Sparsity Pattern Recovery
- Thresholded Basis Pursuit: LP Algorithm for Order-Wise Optimal Support Recovery for Sparse and Approximately Sparse Signals From Noisy Random Measurements
- Information Theoretic Bounds for Compressed Sensing
- Information-Theoretic Limits on Sparse Signal Recovery: Dense versus Sparse Measurement Matrices
- Achieving Optimal Misclassification Proportion in Stochastic Block Model
- Semidefinite programs on sparse random graphs and their application to community detection
- Linear Regression With Shuffled Data: Statistical and Computational Limits of Permutation Recovery
This page was built for publication: Iterative algorithm for discrete structure recovery
