Hanson-Wright inequality in Hilbert spaces with application to K-means clustering for non-Euclidean data

DOI10.3150/20-BEJ1251zbMATH Open1475.60044arXiv1810.11180WikidataQ114038756 ScholiaQ114038756MaRDI QIDQ2214261FDOQ2214261

Authors: Xiaohui Chen, Yun Yang 

Publication date: 7 December 2020

Published in: Bernoulli (Search for Journal in Brave)

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 $K$-means clustering problem for non-Euclidean data. Specifically, we establish the exponential rate of convergence for a semidefinite relaxation of the generalized $K$-means, which together with a simple rounding algorithm imply the exact recovery of the true clustering structure.

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

Recommendations

• Hanson-Wright inequality in Banach spaces
• A note on the Hanson-Wright inequality for random vectors with dependencies
• Hanson-Wright inequality and sub-Gaussian concentration
• Sparse Hanson-Wright inequalities for subgaussian quadratic forms
• On the Performance of Clustering in Hilbert Spaces

zbMATH Keywords

Hilbert space\(K\)-meanssemidefinite relaxationHanson-Wright inequality

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Gaussian processes (60G15) Probability theory on linear topological spaces (60B11) Inequalities; stochastic orderings (60E15)

Cites Work

• Clustering functional data
• Nonparametric functional data analysis. Theory and practice.
• Least squares quantization in PCM
• Theory of Reproducing Kernels
• High-dimensional statistics. A non-asymptotic viewpoint
• High-dimensional probability. An introduction with applications in data science
• Theoretical foundations of functional data analysis, with an introduction to linear operators
• Hanson-Wright inequality and sub-Gaussian concentration
• A tail inequality for quadratic forms of subgaussian random vectors
• Adaptive estimation of a quadratic functional by model selection.
• Feature selection via dependence maximization
• A mathematical introduction to compressive sensing
• A bound on tail probabilities for quadratic forms in independent random variables whose distributions are not necessarily symmetric
• A Bound on Tail Probabilities for Quadratic Forms in Independent Random Variables
• A survey of kernel and spectral methods for clustering
• Random weighted projections, random quadratic forms and random eigenvectors
• A note on the Hanson-Wright inequality for random vectors with dependencies
• SubGaussian random variables in Hilbert spaces
• Transference principles for log-Sobolev and spectral-gap with applications to conservative spin systems
• Pushing the Limits of Contemporary Statistics: Contributions in Honor of Jayanta K. Ghosh
• Approximating K‐means‐type Clustering via Semidefinite Programming
• Advanced Lectures on Machine Learning
• Gaussian and bootstrap approximations for high-dimensional U-statistics and their applications
• When do birds of a feather flock together? \(k\)-means, proximity, and conic programming
• Partial recovery bounds for clustering with the relaxed \(K\)-means

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)