Bernoulli · 2020 · 23 citations · 21 references
Natural SciencesComputer ScienceMathematicsMachine LearningProbability TheoryStatisticsConvex AnalysisConvex OptimizationDimensionality ReductionDocument ClusteringText ClusteringConvex RelaxationsFinite-dimensional Hilbert SpacesInfinite-dimensional Hilbert SpacesK-means ClusteringSemidefinite ProgrammingSemidefinite Programming RelaxationSemidefinite RelaxationSeparable Spaces
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.
21
Least squares quantization in PCM
Sheelagh Lloyd · IEEE Transactions on Information Theory · 1982 · 15.6K citations · Full text
N. Aronszajn · Transactions of the American Mathematical Society · 1950 · 5.4K citations · Full text
A survey of kernel and spectral methods for clustering
Maurizio Filippone, Francesco Camastra, Francesco Masulli et al. · Pattern Recognition · 2007 · 829 citations