COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

University of Cambridge > Talks.cam > Isaac Newton Institute Seminar Series > Rademacher Chaos, Random Eulerian Graphs and The Sparse Johnson-Lindenstrauss Transform

## Rademacher Chaos, Random Eulerian Graphs and The Sparse Johnson-Lindenstrauss TransformAdd to your list(s) Download to your calendar using vCal - Rabani, Y (Hebrew University of Jerusalem)
- Tuesday 11 January 2011, 14:00-15:00
- Seminar Room 1, Newton Institute.
If you have a question about this talk, please contact Mustapha Amrani. Discrete Analysis The celebrated dimension reduction lemma of Johnson and Lindenstrauss has numerous computational and other applications. Due to its application in practice, speeding up the computation of a Johnson-Lindenstrauss style dimension reduction is an important question. Recently, Dasgupta, Kumar, and Sarlos (STOC 2010) constructed such a transform that uses a sparse matrix. This is motivated by the desire to speed up the computation when applied to sparse input vectors, a scenario that comes up in applications. The sparsity of their construction was further improved by Kane and Nelson (ArXiv 2010). We improve the previous bound on the number of non-zero entries per column of Kane and Nelson. We also improve the amount of randomness needed to generate the matrix. Our results are obtained by connecting the moments of an order 2 Rademacher chaos to the combinatorial properties of random Eulerian multigraphs. Estimating the chance that a random multigraph is composed of a given number of node-disjoint Eulerian components leads to a new tail bound on the chaos. Our estimates may be of independent interest, and as this part of the argument is decoupled from the analysis of the coefficients of the chaos, we believe that our methods can be useful in the analysis of other chaoses. Joint work with Vladimir Braverman and Rafail Ostrovsky. This talk is part of the Isaac Newton Institute Seminar Series series. ## This talk is included in these lists:- All CMS events
- Featured lists
- INI info aggregator
- Isaac Newton Institute Seminar Series
- School of Physical Sciences
- Seminar Room 1, Newton Institute
- bld31
Note that ex-directory lists are not shown. |
## Other listsPlant Sciences 'ABC' Seminars Persian Society talks Quantum condensate seminars## Other talksDescription: TIE proteins: chemical harpoons of Gram-positive bacteria White dwarfs as tracers of cosmic, galactic, stellar & planetary evolution Scaling of tissue proportions to body size during vertebrate development Propagation of Very Low Frequency Emissions from Lightning Public Lecture: Development of social behaviour in children from infancy: neurobiological, relational and situational interactions CANCELLED First year PhD student fieldwork seminar |