Approximating Spectral Clustering via Sampling: A Review
From MaRDI portal
Publication:3297374
DOI10.1007/978-3-030-29349-9_5zbMath1436.62446arXiv1901.10204OpenAlexW2912682706MaRDI QIDQ3297374
Andreas Loukas, Nicolas Tremblay
Publication date: 3 July 2020
Published in: Sampling Techniques for Supervised or Unsupervised Tasks (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1901.10204
Classification and discrimination; cluster analysis (statistical aspects) (62H30) Inference from stochastic processes and spectral analysis (62M15) Research exposition (monographs, survey articles) pertaining to statistics (62-02)
Related Items
Sparse and smooth: improved guarantees for spectral clustering in the dynamic stochastic block model, Randomized Spectral Clustering in Large-Scale Stochastic Block Models, Unnamed Item, Unnamed Item, Data Analytics on Graphs Part I: Graphs and Spectra on Graphs, Unnamed Item
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions
- Determinantal processes and independence
- An implicit restarted Lanczos method for large symmetric eigenvalue problems
- Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
- A computational study of several relocation methods for \(k\)-means algorithms.
- A sharp oracle inequality for graph-slope
- Random sampling of bandlimited signals on graphs
- Adaptive estimation of a quadratic functional by model selection.
- Consistency of spectral clustering in stochastic block models
- Consistency of spectral clustering
- The rotation of eigenvectors by a perturbation
- Advanced Coarsening Schemes for Graph Partitioning
- Determinantal Point Processes for Machine Learning
- Computational Advertising: Techniques for Targeting Relevant Ads
- Dimensionality Reduction for k-Means Clustering and Low Rank Approximation
- Efficient estimation of eigenvalue counts in an interval
- Spectral redemption in clustering sparse networks
- Randomized Dimensionality Reduction for <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-Means Clustering
- Spectral Sparsification of Graphs
- An optimal algorithm for approximate nearest neighbor searching fixed dimensions
- Linear-Time Approximation for Maximum Weight Matching
- Matrix approximation and projective clustering via volume sampling
- Efficient algorithms for substring near neighbor problem
- A FAST k-MEANS IMPLEMENTATION USING CORESETS
- A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
- A simple min-cut algorithm
- On the Quality of Spectral Separators
- Templates for the Solution of Algebraic Eigenvalue Problems
- A local search approximation algorithm for k-means clustering
- Input Sparsity Time Low-rank Approximation via Ridge Leverage Score Sampling
- Discrete Signal Processing on Graphs: Sampling Theory
- Modern Algorithms of Cluster Analysis
- A Note On Spectral Clustering
- Autoregressive Moving Average Graph Filtering
- Signals on Graphs: Uncertainty Principle and Sampling
- Least squares quantization in PCM
- An Improved Spectral Graph Partitioning Algorithm for Mapping Parallel Computations
- Performance of Johnson-Lindenstrauss transform for k -means and k -medians clustering
- Eigendecomposition-Free Sampling Set Selection for Graph Signals
- The effectiveness of lloyd-type methods for the k-means problem
- Multi-way spectral partitioning and higher-order cheeger inequalities
- Approaching Optimality for Solving SDD Linear Systems
- A unified framework for approximating and clustering data
- Fast monte-carlo algorithms for finding low-rank approximations
- Fast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a Matrix
- Minimum cuts in near-linear time
- Partitioning Well-Clustered Graphs: Spectral Clustering Works!
- Graph Sparsification by Effective Resistances
