Close
Publizieren
Besondere Sammlungen
Digitalisierungsservice
Hilfe
Impressum
Datenschutz
jump to main content
Search Details
Quicksearch:
OK
Title
Title
Content
Content
Page
Page
Search Book
Algorithms for the Bregman k-Median problem / Marcel R. Ackermann. 2009
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
The search-operation requires javascript to be activated.