Content

•  
   1 Introduction
•  
   1.1 State of the art
•  
   1.2 Outline and main results
•  
   1.3 Bibliographic notes
•  
   2 Bregman divergences
•  
   2.1 Definition
•  
   2.1.1 Basic properties
•  
   2.1.2 Examples of Bregman divergences
•  
  2.2 μ-similarity
•  
   2.2.1 Mahalanobis distances
•  
   2.2.2 μ-similar Bregman divergences
•  
   2.2.3 Examples of μ-similar Bregman divergences
•  
   3 The k-median problem
•  
  3.1 The generalized k-median problem
•  
   3.1.1 Definitions and notation
•  
   3.1.2 Properties
•  
   3.2 Bregman k-median clustering
•  
   3.3 A simple optimal algorithm for d=1
•  
   4 (1+ε)-approximate clustering by uniform sampling
•  
  4.1 Algorithm for [γ,δ]-sampleable dissimilarity measures
•  
   4.1.1 Superset sampling
•  
   4.1.2 The algorithm
•  
   4.1.3 Analysis for k=2
•  
   4.1.4 Analysis for k≥2
•  
   4.1.5 Adaptation for weighted input sets
•  
  4.2 Sampling for large classes of dissimilarity measures
•  
   4.2.1 Sampling for Mahalanobis distances
•  
   4.2.2 Sampling for μ-similar Bregman divergences
•  
   4.2.3 Sampling for the Hellinger distance
•  
   4.2.4 Sampling for arbitrary metrics with bounded doubling dimension
•  
   4.2.5 Sampling for the Hamming distance
•  
   4.3 Generalization of the sampling property
•  
   4.4 Discussion
•  
   5 A practical O(log k)-approximate algorithm
•  
  5.1 Algorithm BregMeans++
•  
   5.1.1 Non-uniform sampling scheme for -similar Bregman divergences
•  
   5.1.2 Proof of Theorem 5.3
•  
  5.2 Non-uniform sampling on separable instances
•  
   5.2.1 Separable input sets
•  
   5.2.2 Proof of Theorem 5.10
•  
   5.3 Discussion
•  
   6 Strong coresets for Mahalanobis distances
•  
   6.1 Har-Peled-Mazumdar coresets
•  
   6.1.1 Euclidean k-means clustering
•  
   6.1.2 Mahalanobis k-median clustering
•  
   6.1.3 Properties of Har-Peled-Mazumdar coresets
•  
   6.2 A new coreset construction based on non-uniform sampling
•  
   6.2.1 Coreset Construction
•  
   6.2.2 Proof of Theorem 6.14
•  
   6.3 Discussion
•  
   7 Weak coresets for μ-similar Bregman divergences
•  
  7.1 Construction of -weak coresets
•  
   7.1.1 Chen's coreset construction for Bregman divergences
•  
   7.1.2 Proof of Theorem 7.4
•  
   7.2 Application to Bregman k-median clustering
•  
   7.3 Discussion
•  
   8 On the limits of using uniform sampling
•  
   8.1 Sampleable Bregman divergences avoid singularities
•  
   8.2 Explicit domain bounds for some Bregman divergences
•  
   8.3 Discussion
•  
   A Applications
•  
   A.1 Estimating mixtures of identical Gaussian sources
•  
   A.2 Model reduction for data compression
•  
   A.3 Codebook generation for vector quantization in speech processing
•  
  B Mathematical fundamentals
•  
  B.1 The vectorspace ℝd
•  
   B.1.1 Vector arithmetic and inner product
•  
   B.1.2 Distances and metrics
•  
   B.1.3 Convex sets
•  
   B.1.4 Relative interior
•  
  B.2 Inequalities
•  
   B.2.1 Triangle inequality of the reals
•  
   B.2.2 Bounds to the binomial coefficient
•  
   B.2.3 Bounds on the harmonic number
•  
   B.2.4 Chebyshev's sum inequality
•  
  B.3 Calculus
•  
   B.3.1 Partial derivatives
•  
   B.3.2 Mean value theorem
•  
   B.3.3 Taylor expansion
•  
   B.3.4 Convex functions
•  
   B.3.5 Positive definiteness
•  
  B.4 Probability theory
•  
   B.4.1 Probability, expectation, and variance
•  
   B.4.2 Law of conditional probability
•  
   B.4.3 Law of total probability
•  
   B.4.4 Law of total expectation
•  
   B.4.5 Union bound
•  
   B.4.6 Markov's inequality
•  
   B.4.7 Chebyshev's inequality
•  
   B.4.8 Chernoff bounds