License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.61
URN: urn:nbn:de:0030-drops-112762
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11276/
Go to the corresponding LIPIcs Volume Portal

Jagadeesan, Meena

Simple Analysis of Sparse, Sign-Consistent JL

pdf-format:
LIPIcs-APPROX-RANDOM-2019-61.pdf (0.5 MB)

Abstract

Allen-Zhu, Gelashvili, Micali, and Shavit construct a sparse, sign-consistent Johnson-Lindenstrauss distribution, and prove that this distribution yields an essentially optimal dimension for the correct choice of sparsity. However, their analysis of the upper bound on the dimension and sparsity requires a complicated combinatorial graph-based argument similar to Kane and Nelson's analysis of sparse JL. We present a simple, combinatorics-free analysis of sparse, sign-consistent JL that yields the same dimension and sparsity upper bounds as the original analysis. Our analysis also yields dimension/sparsity tradeoffs, which were not previously known.
As with previous proofs in this area, our analysis is based on applying Markov's inequality to the pth moment of an error term that can be expressed as a quadratic form of Rademacher variables. Interestingly, we show that, unlike in previous work in the area, the traditionally used Hanson-Wright bound is not strong enough to yield our desired result. Indeed, although the Hanson-Wright bound is known to be optimal for gaussian degree-2 chaos, it was already shown to be suboptimal for Rademachers. Surprisingly, we are able to show a simple moment bound for quadratic forms of Rademachers that is sufficiently tight to achieve our desired result, which given the ubiquity of moment and tail bounds in theoretical computer science, is likely to be of broader interest.

BibTeX - Entry

@InProceedings{jagadeesan:LIPIcs:2019:11276,
  author =	{Meena Jagadeesan},
  title =	{{Simple Analysis of Sparse, Sign-Consistent JL}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{61:1--61:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Dimitris Achlioptas and L{\'a}szl{\'o} A. V{\'e}gh},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/11276},
  URN =		{urn:nbn:de:0030-drops-112762},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.61},
  annote =	{Keywords: Dimensionality reduction, Random projections, Johnson-Lindenstrauss distribution, Hanson-Wright bound, Neuroscience-based constraints}
}

Keywords: Dimensionality reduction, Random projections, Johnson-Lindenstrauss distribution, Hanson-Wright bound, Neuroscience-based constraints
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Issue Date: 2019
Date of publication: 17.09.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI