Vector Quantization (k-means problem)

Vector Quantization, or the k-means problem, aims to find a codebook C consisting of k d-dimensional vectors for a given dataset X of d-dimensional numerical vectors and a positive integer k, such that the sum of squared distances from each vector in X to its nearest vector in C is minimized. This problem is NP-hard and is widely applied in areas such as data compression, cluster analysis, and feature encoding, making it of significant theoretical and practical importance.