Fetching the paper…

Reading the bibliography…

Dimensionality Reduction of Massive Sparse Datasets Using Coresets · Around

2015

Dimensionality Reduction of Massive Sparse Datasets Using Coresets

Feldman, Dan, Volkov, Mikhail, Rus, Daniela

Original
PDF
Post on X

Understand

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 low rank approximation (reduced SVD) of such matrices.
Our solution uses coresets, which is a subset of $O(k/\eps^2)$ scaled rows from the $n\times d$ input matrix, that approximates the sub of squared distances from its rows to every $k$-dimensional subspace in $\REAL^d$, up to a factor of $1\pm\eps$.
An open theoretical problem has been whether we can compute such a coreset that is independent of the input matrix and also a weighted subset of its rows.

Built on

Coresets, sparse greedy approximation, and the frank-wolfe algorithm
Kenneth L Clarkson · 2010
Earlier work this paper cites.
A unified framework for approximating and clustering data
D. Feldman and M. Langberg · 2010
Earlier work this paper cites.
Phd thesis
Dan Feldman · 2010
Earlier work this paper cites.
Universal ε \varepsilon approximators for integrals
M. Langberg and L. J. Schulman · 2010
Earlier work this paper cites.
The hadoop distributed file system
Konstantin Shvachko, Hairong Kuang, Sanjay Radia, and Robert Chansler · 2010
Earlier work this paper cites.

Similar

Gensim—statistical semantics in python
Radim Ruvrek, Petr Sojka, et al · 2011
Cited alongside, same era.
Twice-ramanujan sparsifiers
Joshua Batson, Daniel A Spielman, and Nikhil Srivastava · 2012
Cited alongside, same era.
Randomized methods for computing low-rank approximations of matrices
Nathan P Halko · 2012
Cited alongside, same era.
On the sensitivity of shape fitting problems
Original
Kasturi Varadarajan and Xin Xiao · 2012
Cited alongside, same era.

Then

Low rank approximation and regression in input sparsity time
Kenneth L Clarkson and David P Woodruff · 2013
Later among the works it cites.
Turning big data into tiny data: Constant-size coresets for k-means, pca and projective clustering
D. Feldman, M. Schmidt, and C Sohler · 2013
Later among the works it cites.
Simple and deterministic matrix sketching
Edo Liberty · 2013
Later among the works it cites.
Frequent directions: Simple and deterministic matrix sketching
Original
Mina Ghashami, Edo Liberty, Jeff M Phillips, and David P Woodruff · 2015
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…