Applications of Random Matrices in Spectral Computations and Machine Learning Dimitris Achlioptas UC Santa Cruz This talk Viewpoint: use randomness to “transform” the data This talk Viewpoint: use randomness to “transform” the data Random Projections (cid:122) Fast Spectral Computations (cid:122) Sampling in Kernel PCA (cid:122) The Setting The Setting n d n d n × d The Setting n d n d n × d The Setting n d n d n × d P Output: AP The Johnson-Lindenstrauss lemma The Johnson-Lindenstrauss lemma Algorithm: Projecting onto a random hyperplane (subspace) of dimension succeeds with probability Applications Approximation algorithms (cid:122) [Charikar’02] Hardness of approximation (cid:122) [Trevisan ’97] Learning mixtures of Gaussians (cid:122) [Arora, Kannan ‘01] Approximate nearest-neighbors (cid:122) [Kleinberg ’97] Data-stream computations (cid:122) [Alon et al. ‘99, Indyk ‘00] Min-cost clustering (cid:122) [Schulman ‘00] …. (cid:122) Information Retrieval (LSI) (cid:122) [Papadimitriou et al. ‘97]