Piotr Indyk, Ali Vakilian, Tal Wagner, David Woodruff
TL;DR本文研究了距离矩阵的低秩近似算法及其样本复杂度,在实验中得到了验证。
Abstract
A distance matrix $A \in \mathbb R^{n \times m}$ represents all pairwise distances, $A_{ij}=\mathrm{d}(x_i,y_j)$, between two point sets $x_1,...,x_n$ and $y_1,...,y_m$ in an arbitrary metric space $(\mathcal Z, \mathrm{d})$. Such matrices arise in various computational contexts such a