1

While other answers are correct, I want to mention one result from Polynomial Time Approximation Schemes for Geometric k-Clustering, which is weaker, which roughly says that there exists a (randomized) mapping which does not increase the distance between two points which are already close enough and it does not decrease the distance between two point which ...


1

Let the matrix consist of $n$ points in $d$-dimensional space. We first generate a projection matrix $d\times K$ whose each entry is sampled from the Cauchy distribution. Then the sketch matrix is computed via projecting the input matrix on the projection matrix. For a pair of points, we compute their sketch vector using the same projection matrix. Then we ...


Only top voted, non community-wiki answers of a minimum length are eligible