Principal component projection without principal component analysis

Roy Frosting, Cameron Musco, Christopher Musco, Aaron Sidford

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 Scopus citations

Abstract

We show how to efficiently project a vector onto the top principal components of a matrix, without explicitly computing these components. Specifically, we introduce an iterative algorithm that provably computes the projection using few calls to any black-box routine for ridge regression. By avoiding explicit principal component analysis (PCA), our algorithm is the first with no runtime dependence on the number of top principal components. We show that it can be used to give a fast iterative method for the popular principal component regression problem, giving the first major runtime improvement over the naive method of combining PCA with regression. To achieve our results, we first observe that ridge regression can be used to obtain a "smooth projection" onto the top principal components. We then sharpen this approximation to true projection using a low-degree polynomial approximation to the matrix step function. Step function approximation is a topic of long-term interest in scientific computing. We extend prior theory by constructing polynomials with simple iterative structure and rigorously analyzing their behavior under limited precision.copyright

Original languageEnglish (US)
Title of host publication33rd International Conference on Machine Learning, ICML 2016
EditorsKilian Q. Weinberger, Maria Florina Balcan
PublisherInternational Machine Learning Society (IMLS)
Pages3495-3503
Number of pages9
ISBN (Electronic)9781510829008
StatePublished - Jan 1 2016
Event33rd International Conference on Machine Learning, ICML 2016 - New York City, United States
Duration: Jun 19 2016Jun 24 2016

Publication series

Name33rd International Conference on Machine Learning, ICML 2016
Volume5

Other

Other33rd International Conference on Machine Learning, ICML 2016
CountryUnited States
CityNew York City
Period6/19/166/24/16

All Science Journal Classification (ASJC) codes

  • Artificial Intelligence
  • Software
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'Principal component projection without principal component analysis'. Together they form a unique fingerprint.

  • Cite this

    Frosting, R., Musco, C., Musco, C., & Sidford, A. (2016). Principal component projection without principal component analysis. In K. Q. Weinberger, & M. F. Balcan (Eds.), 33rd International Conference on Machine Learning, ICML 2016 (pp. 3495-3503). (33rd International Conference on Machine Learning, ICML 2016; Vol. 5). International Machine Learning Society (IMLS).