2014 ProvableDeterministicLeverageSc

• (Papailiopoulos et al., 2014) ⇒ Dimitris Papailiopoulos, Anastasios Kyrillidis, and Christos Boutsidis. (2014). “Provable Deterministic Leverage Score Sampling.” In: Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2014) Journal. ISBN:978-1-4503-2956-9 doi:10.1145/2623330.2623698

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222014%22+Provable+Deterministic+Leverage+Score+Sampling
• http://dl.acm.org/citation.cfm?id=2623330.2623698&preflayout=flat#citedby

Quotes

Author Keywords

• Deterministic sampling; leverage scores; low-rank matrix approximation; numerical linear algebra; power law distributions; subset selection

Abstract

We explain theoretically a curious empirical phenomenon: “Approximating a matrix by deterministically selecting a subset of its columns with the corresponding largest leverage scores results in a good low-rank matrix surrogate ". In this work, we provide a novel theoretical analysis of deterministic leverage score sampling. We show that such sampling can be provably as accurate as its randomized counterparts, if the leverage scores follow a moderately steep power-law decay. We support this power-law assumption by providing empirical evidence that such decay laws are abundant in real-world data sets. We then demonstrate empirically the performance of deterministic leverage score sampling, which many times matches or outperforms the state-of-the-art techniques.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2014 ProvableDeterministicLeverageSc	Christos Boutsidis Dimitris Papailiopoulos Anastasios Kyrillidis			Provable Deterministic Leverage Score Sampling				10.1145/2623330.2623698		2014