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

Research output: Contribution to journalArticlepeer-review

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.

Original languageEnglish (US)
Pages (from-to)586-614
Number of pages29
JournalBernoulli
Volume27
Issue number1
DOIs
StatePublished - Feb 2021

Keywords

  • Hanson–Wright inequality
  • Hilbert space
  • K-means
  • Semidefinite relaxation

ASJC Scopus subject areas

  • Statistics and Probability

Fingerprint

Dive into the research topics of 'Hanson–Wright inequality in Hilbert spaces with application to K-means clustering for non-Euclidean data'. Together they form a unique fingerprint.

Cite this