Computer Science/Discrete Mathematics Seminar II | |

Topic: | Sparsity Lower Bounds for Dimensionality Reducing Maps |

Speaker: | Jelani Nelson |

Affiliation: | Member, School of Mathematics |

Date: | Tuesday, January 22 |

Time/Room: | 10:30am - 12:30pm/S-101 |

Video Link: | https://video.ias.edu/1213/csdm/0122-JelaniNelson |

Abstract: We give near-tight lower bounds for the sparsity required in several dimensionality reducing linear maps. In particular, we show: (1) The sparsity achieved by [Kane-Nelson, SODA 2012] in the sparse Johnson-Lindenstrauss lemma is optimal up to a log(1/eps) factor. (2) RIP_2 matrices preserving k-space vectors in R^n with the optimal number of rows must be dense as long as k < n / polylog(n). (3) Any oblivious subspace embedding with 1 non-zero entry per column and preserving d-dimensional subspaces in R^n must have Omega(d^2) rows, matching an upper bound of [Nelson-Nguyen, 2012] for constant distortion. Joint work with Huy LĂȘ Nguyen (Princeton).