In this talk, I will introduce the famous Johnson-Lindenstrauss (J-L) lemma which yields fast dimensionality reduction through random projections. This lemma has also led to many randomized algorithms to speed up matrix computations. In this work, we extend this idea of random projections to an infinite-dimensional reproducing kernel Hilbert space and obtain a J-L type lemma. This random projection yields computationally fast kernel algorithms with no loss in performance. (Joint work with Samory Kpotufe, Columbia University)