A Simple SVD Algorithm for Finding Hidden Partitions

DOI10.1017/S0963548317000463zbMath1386.68110arXiv1404.3918OpenAlexW2963660540MaRDI QIDQ4601058

Van H. Vu

Publication date: 19 January 2018

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Combinatorial probability (60C05) Randomized algorithms (68W20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (21)

Asymptotic Theory of Eigenvectors for Random Matrices With Diverging Spikes ⋮ Model-free Nonconvex Matrix Completion: Local Minima Analysis and Applications in Memory-efficient Kernel PCA ⋮ Optimal Bipartite Network Clustering ⋮ Unnamed Item ⋮ Rate optimal Chernoff bound and application to community detection in the stochastic block models ⋮ A simple spectral algorithm for recovering planted partitions ⋮ Unnamed Item ⋮ Entrywise eigenvector analysis of random matrices with low expected rank ⋮ A Spectral Method for Joint Community Detection and Orthogonal Group Synchronization ⋮ Eigenvector Computation and Community Detection in Asynchronous Gossip Models ⋮ Recovering nonuniform planted partitions via iterated projection ⋮ Partitioning Well-Clustered Graphs: Spectral Clustering Works! ⋮ Estimating the number of communities by spectral methods ⋮ Recovering the structure of random linear graphs ⋮ Layout of random circulant graphs ⋮ Convex relaxation methods for community detection ⋮ Subspace estimation from unbalanced and incomplete data matrices: \({\ell_{2,\infty}}\) statistical guarantees ⋮ Consistent nonparametric estimation for heavy-tailed sparse graphs ⋮ Optimality of spectral clustering in the Gaussian mixture model ⋮ A multiscale environment for learning by diffusion ⋮ Graph Powering and Spectral Robustness

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding hidden cliques of size \(\sqrt{N/e}\) in nearly linear time
• The eigenvalues of random symmetric matrices
• A new look at independence
• Random weighted projections, random quadratic forms and random eigenvectors
• Graph Partitioning via Adaptive Spectral Techniques
• Spectral Algorithms
• Almost all k-colorable graphs are easy to color
• A Spectral Technique for Coloring Random 3-Colorable Graphs
• Coloring Random and Semi-Random k-Colorable Graphs
• Finding and certifying a large hidden clique in a semirandom graph
• Spectral analysis of data
• Spectral techniques applied to sparse random graphs
• Finding Hidden Cliques in Linear Time with High Probability
• The Rotation of Eigenvectors by a Perturbation. III
• Perturbation bounds in connection with singular value decomposition
• Spectral norm of random matrices

This page was built for publication: A Simple SVD Algorithm for Finding Hidden Partitions