Dimensionality Reduction of Massive Sparse Datasets Using Coresets
Dimensionality Reduction of Massive Sparse Datasets Using Coresets
复制标题
使用 Coresets 对海量稀疏数据集进行降维
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
D. Rus
中科院分区：
文献类型：
--
作者：
Dan Feldman;M. Volkov;D. Rus
在本文中，我们针对超大规模稀疏矩阵的降维问题提出了一种具有性能保证的实用解决方案。我们展示了我们的方法在计算任意 $n imes d$ 矩阵的主成分分析 (PCA) 时的应用，使用一次遍历其行流。我们的解决方案使用核心集：$n$ 行的缩放子集，近似于 emph{every} $k$ 维 emph{affine} 子空间的距离平方和。一个开放的理论问题是计算这样一个独立于 $n$ 和 $d$ 的核心集。一个开放的实际问题是在合理的时间内计算非常大但稀疏的数据库（例如维基百科文档术语矩阵）的 PCA 的非平凡近似值。我们对这两个问题的回答都是肯定的。我们的主要技术成果是基于减少流中项目计数问题的确定性核心集构造的新框架。
In this paper we present a practical solution with performance guarantees to the problem of dimensionality reduction for very large scale sparse matrices. We show applications of our approach to computing the Principle Component Analysis (PCA) of any $n imes d$ matrix, using one pass over the stream of its rows. Our solution uses coresets: a scaled subset of the $n$ rows that approximates their sum of squared distances to emph{every} $k$-dimensional emph{affine} subspace. An open theoretical problem has been to compute such a coreset that is independent of both $n$ and $d$. An open practical problem has been to compute a non-trivial approximation to the PCA of very large but sparse databases such as the Wikipedia document-term matrix in a reasonable time. We answer both of these questions affirmatively. Our main technical result is a new framework for deterministic coreset constructions based on a reduction to the problem of counting items in a stream.
DOI：
--
发表时间：
2012
期刊：
--
影响因子：
--
作者：
P. Martinsson;N. Halko
通讯作者：
P. Martinsson;N. Halko