2015 MoreConstraintsSmallerCoresetsC

Subject Headings:

Notes

We suggest a generic data reduction technique with provable guarantees for computing the low rank approximation of a matrix under some [math]\displaystyle{ \mathcal{l}_z }[/math] error, and constrained factorizations, such as the Non-negative Matrix Factorization (NMF). Our main algorithm reduces a given [math]\displaystyle{ n \times d }[/math] matrix into a small, [math]\displaystyle{ \vartheta }[/math]-dependent, weighted subset C of its rows (known as a coreset), whose size is independent of both n and d. We then prove that applying existing algorithms on the resulting coreset can be turned into ([math]\displaystyle{ 1 + \vartheta }[/math]) - approximations for the original (large) input matrix. In particular, we provide the first linear time approximation scheme (LTAS) for the rank-one NMF.

The coreset C can be computed in parallel and using only one pass over a possibly unbounded stream of [row vector]]s. In this sense we improve the result in [4] (Best paper of STOC 2013). Moreover, since C is a subset of these rows, its construction time, as well as its sparsity (number of non-zeroes entries) and the sparsity of the resulting low rank approximation depend on the maximum sparsity of an input row, and not on the actual dimension d. In this sense, we improve the result of Libery [21] (Best paper of KDD-2013) and answer affirmably, and in a more general setting, his open question of computing such a coreset.

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2015 MoreConstraintsSmallerCoresetsC	Dan Feldman Tamir Tassa			More Constraints, Smaller Coresets: Constrained Matrix Approximation of Sparse Big Data				10.1145/2783258.2783312		2015