Almost Optimal Unrestricted Fast Johnson-Lindenstrauss Transform

Understand

The problems of random projections and sparse reconstruction have much in common and individually received much attention.

• Surprisingly, until now they progressed in parallel and remained mostly separate.
• Here, we employ new tools from probability in Banach spaces that were successfully used in the context of sparse reconstruction to advance on an open problem in random pojection.
• In particular, we generalize and use an intricate result by Rudelson and Vershynin for sparse reconstruction which uses Dudley's theorem for bounding Gaussian processes.