Distortion of a codebook, computed as transport to its atoms

Pollard's formulation of k-means is exactly a transport problem: the empirical measure is pushed onto a finitely supported one, and the distortion is the transport cost. Because nearest-point assignment is itself an optimal plan for the induced weights, the transport cost and the ordinary mean-squared distortion coincide – so the two are computed separately here and both reported, which turns the identity into a self-check.

Usage

Otmqd(X, centroids)

Arguments

X

Data points, n by d, given equal weight.

centroids

Codebook, K by d.

Value

List with dist, dist_assign, gap, labels, weights, n, K, d.

Details

Formula: Distortion = OT(mu, nu_quant) with nu_quant supported on the centroids and weighted by the assignment proportions; equal to (1/n) sum_i min_k ||x_i - c_k||^2 – Pollard (1982).

References

Pollard, D. (1982). IEEE Transactions on Information Theory 28(2):199-205. doi:10.1109/TIT.1982.1056481 .

Examples

V <- c(1, 2, 3, 4, 5, 6, 7, 8)
Otmqd(V, V)
#> $dist
#> [1] 0
#> 
#> $dist_assign
#> [1] 0
#> 
#> $gap
#> [1] 0
#> 
#> $labels
#> [1] 0 1 2 3 4 5 6 7
#> 
#> $weights
#> [1] 0.125 0.125 0.125 0.125 0.125 0.125 0.125 0.125
#> 
#> $n
#> [1] 8
#> 
#> $K
#> [1] 8
#> 
#> $d
#> [1] 1
#> 
#> $method
#> [1] "Quantization distortion as transport cost"
#> 
#> attr(,"class")
#> [1] "morie_rich_result" "list"