  Random projections have proven extremely useful in many signal processing and
machine learning applications. However, they often require either to store a
very large random matrix, or to use a different, structured matrix to reduce
the computational and memory costs. Here, we overcome this difficulty by
proposing an analog, optical device, that performs the random projections
literally at the speed of light without having to store any matrix in memory.
This is achieved using the physical properties of multiple coherent scattering
of coherent light in random media. We use this device on a simple task of
classification with a kernel machine, and we show that, on the MNIST database,
the experimental results closely match the theoretical performance of the
corresponding kernel. This framework can help make kernel methods practical for
applications that have large training sets and/or require real-time prediction.
We discuss possible extensions of the method in terms of a class of kernels,
speed, memory consumption and different problems.
