Hanson-Wright inequality in Hilbert spaces with application to K-means clustering for non-Euclidean data
From MaRDI portal
Publication:2214261
Abstract: We derive a dimension-free Hanson-Wright inequality for quadratic forms of independent sub-gaussian random variables in a separable Hilbert space. Our inequality is an infinite-dimensional generalization of the classical Hanson-Wright inequality for finite-dimensional Euclidean random vectors. We illustrate an application to the generalized -means clustering problem for non-Euclidean data. Specifically, we establish the exponential rate of convergence for a semidefinite relaxation of the generalized -means, which together with a simple rounding algorithm imply the exact recovery of the true clustering structure.
Recommendations
Cites work
- A Bound on Tail Probabilities for Quadratic Forms in Independent Random Variables
- A bound on tail probabilities for quadratic forms in independent random variables whose distributions are not necessarily symmetric
- A mathematical introduction to compressive sensing
- A note on the Hanson-Wright inequality for random vectors with dependencies
- A survey of kernel and spectral methods for clustering
- A tail inequality for quadratic forms of subgaussian random vectors
- Adaptive estimation of a quadratic functional by model selection.
- Advanced Lectures on Machine Learning
- Approximating K‐means‐type Clustering via Semidefinite Programming
- Clustering functional data
- Feature selection via dependence maximization
- Gaussian and bootstrap approximations for high-dimensional U-statistics and their applications
- Hanson-Wright inequality and sub-Gaussian concentration
- High-dimensional probability. An introduction with applications in data science
- High-dimensional statistics. A non-asymptotic viewpoint
- Least squares quantization in PCM
- Nonparametric functional data analysis. Theory and practice.
- Partial recovery bounds for clustering with the relaxed \(K\)-means
- Pushing the Limits of Contemporary Statistics: Contributions in Honor of Jayanta K. Ghosh
- Random weighted projections, random quadratic forms and random eigenvectors
- SubGaussian random variables in Hilbert spaces
- Theoretical foundations of functional data analysis, with an introduction to linear operators
- Theory of Reproducing Kernels
- Transference principles for log-Sobolev and spectral-gap with applications to conservative spin systems
- When do birds of a feather flock together? \(k\)-means, proximity, and conic programming
Cited in
(6)- Diffusion \(K\)-means clustering on manifolds: provable exact recovery via semidefinite relaxations
- Community detection with dependent connectivity
- Partial recovery bounds for clustering with the relaxed \(K\)-means
- Optimally tackling covariate shift in RKHS-based nonparametric regression
- Correlation Tensor Decomposition and Its Application in Spatial Imaging Data
- An \({\ell_p}\) theory of PCA and spectral clustering
This page was built for publication: Hanson-Wright inequality in Hilbert spaces with application to \(K\)-means clustering for non-Euclidean data
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2214261)
