Sublinear Time Low-Rank Approximation of Distance Matrices
Sublinear Time Low-Rank Approximation of Distance Matrices
复制标题
DOI：
--
复制
发表时间：
2018-09
期刊：
影响因子：
--
通讯作者：
Ainesh Bakshi;David P. Woodruff
中科院分区：
文献类型：
--
作者：
Ainesh Bakshi;David P. Woodruff
让Ƥ = {p1, p2，…pn}和Q = {q1, q2…Qm}是任意度量空间中的两个点集。设A表示与Ai的m × n成对距离矩阵。J = d（, qj）这种距离矩阵通常在软件包中计算，并且在学习图像流形、手写识别和多维展开等方面具有应用。为了减小它们的描述大小，我们研究了这类矩阵的低秩逼近。我们的主要结果是表明，对于任何潜在的距离度量d，有可能在亚线性时间内实现加性误差低秩近似。我们注意到对于任意矩阵a，在次线性时间内不可能得到这样的保证，并且我们的证明利用了距离矩阵的特殊性质。提出了一种基于加性投影保成本采样的递归算法。然后我们表明，一般情况下，在亚线性时间内，距离矩阵的相对误差近似是不可能的，即使一个人允许双准则解。此外，我们证明，如果Ƥ = Q和d是欧几里得距离的平方，它不是一个度规，而是一个度规的平方，那么在亚线性时间内可以找到一个相对误差双准则解。最后，我们将我们的算法与奇异值分解（SVD）和输入稀疏时间算法进行了经验比较。我们的算法比SVD快几百倍，在实际数据集和大小为108的合成数据集上，比输入稀疏性方法快8-20倍。在准确性方面，我们的算法只比SVD（最优）和输入稀疏时间算法稍微差一点。
Let Ƥ = {p1, p2, . . .pn} and Q = {q1, q2 . . . qm} be two point sets in an arbitrary metric space. Let A represent the m × n pairwise distance matrix with Ai.j = d(pi, qj). Such distance matrices are commonly computed in software packages and have applications to learning image manifolds, handwriting recognition, and multi-dimensional unfolding, among other things. In an attempt to reduce their description size, we study low rank approximation of such matrices. Our main result is to show that for any underlying distance metric d, it is possible to achieve an additive error low rank approximation in sublinear time. We note that it is provably impossible to achieve such a guarantee in sublinear time for arbitrary matrices A, and our proof exploits special properties of distance matrices. We develop a recursive algorithm based on additive projection-cost preserving sampling. We then show that in general, relative error approximation in sublinear time is impossible for distance matrices, even if one allows for bicriteria solutions. Additionally, we show that if Ƥ = Q and d is the squared Euclidean distance, which is not a metric but rather the square of a metric, then a relative error bicriteria solution can be found in sublinear time. Finally, we empirically compare our algorithm with the singular value decomposition (SVD) and input sparsity time algorithms. Our algorithm is several hundred times faster than the SVD, and about 8-20 times faster than input sparsity methods on real-world and and synthetic datasets of size 108. Accuracy-wise, our algorithm is only slightly worse than that of the SVD (optimal) and input-sparsity time algorithms.