en
0.25
0.5
0.75
1.25
1.5
1.75
2
Provable Deterministic Leverage Score Sampling
Published on Oct 07, 20141682 Views
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
Related categories
Chapter list
Provable Deterministic Leverage Score Sampling00:00
Singular Value Decomposition00:14
The Column Subset Selection Problem (CSSP)01:31
Motivation02:36
Prior work on CSSP03:22
Leverage scores and randomized sampling04:34
Deterministic leverage score sampling - 106:34
Deterministic leverage score sampling - 207:26
Main result08:59
Main result: leverage scores following a power law10:19
Is power law a realistic assumption?12:13
Power law is a realistic assumption13:09
Power-law decaying leverage scores13:44
Nearly-uniform leverage scores15:50
Conclusions15:56