Loading...
Please wait, while we are loading the content...
Similar Documents
The Fast Johnson-Lindenstrauss Transform and Applications
| Content Provider | Semantic Scholar |
|---|---|
| Author | Ailon, Nir |
| Copyright Year | 2007 |
| Abstract | Dimension reduction is a highly useful tool in algorithm design, with applications in nearest neighbor searching, clustering, streaming, sketching, learning, approximation algorithms, vision and others. It removes redundancy from data and can be plugged into algorithms suffering from a ”curse of dimensionality”. In my talk, I will describe a novel technique for reducing the dimension of points in Euclidean space, improving a now classic algorithm by Johnson and Lindenstrauss from the mid 80’s. Our technique is the first to offer an asymptotic improvement, and has already been used in design of efficient algorithms for nearest neighbor searching and high dimensional linear algebraic numerical computations. I will present our algorithm, its proof, applications, and interesting open questions. Joint work with Bernard Chazelle. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://www.cs.helsinki.fi/hecse/events/sada07/lectures/ailon-1.pdf |
| Alternate Webpage(s) | http://www.cs.helsinki.fi/hecse/sada07/lectures/ailon-1.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
