Efficient Dimension Reduction

Nir Ailon
Google Research

The Johnson-Lindenstrauss dimension reduction idea using random
projections was discovered in the early 80's. Since then many
"computer science friendly" versions were published, offering constant
factor but no big-Oh improvements in the runtime. Two years ago Ailon
and Chazelle showed a nontrivial algorithm with the first asymptotic
improvement, and suggested the question: What is the exact complexity
of J-L computation from d dimensions to k dimensions? An O(d log d)
upper bound is implied by A-C for k up to d^{1/3} (in the L2->L2)
case. In this talk I will show how to achieve this bound for k up to
d^{1/2} combining techniques from the theories of error correcting
codes and probability in Banach spaces. This is based on joint
work with Edo Liberty.

Presentation (PDF File)

Back to Quantitative and Computational Aspects of Metric Geometry