BARC talk by Chris Schwiegelshohn – University of Copenhagen

▤ Summary

Abstract: We show that for n points in d-dimensional Euclidean space, a data oblivious random projection of the columns onto m in O( log k+log log n eps^-6 log 1/eps) dimensions is sufficient to approximate the cost of all k-means clusterings up to a multiplicative (1±eps) factor. The previous-best upper bounds on m are O(log n eps^-2 ) given by a direct application of the Johnson-Lindenstrauss Lemma, and O( k ε^-2 ) given by [Cohen et al.-STOC’15].

▦ Linked Companies