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.
Copyright. All Rights Reserved.