Campus Event Calendar

Event Entry

What and Who

A Generalization of the Johnson-Lindenstrauss Lemma

Michael Kerber
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI  
AG Audience

Date, Time and Location

Tuesday, 12 November 2013
30 Minutes
E1 4


(joint work with R.Sharathkumar, Stanford University)

Computational methods for real-world data sets often suffer from the "curse of dimensionality"; a common approach is to reduce the dimension of the data while preserving its important structure. The Johnson-Lindenstrauss lemma is a celebrated result in this context: it states that a random (scaled) projection into a lower-dimensional space (approximately) preserves the pairwise distances of a point set with constant probability.

We extend this result by showing that random projections preserve more structure: for any set of k points, the radius of their minimum enclosing ball is preserved with constant probability. We show applications of this result for k-center clustering and for the construction of approximate Cech complexes.


Michael Kerber
--email hidden
passcode not visible
logged in users only

Michael Kerber, 10/22/2013 17:53
Michael Kerber, 10/17/2013 18:28 -- Created document.