Principal component projection without principal component analysis

Roy Frosting, Cameron Musco, Christopher Musco, Aaron Sidford

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

    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 - 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

    ASJC Scopus subject areas

    • 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