### 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 language | English (US) |
---|---|

Title of host publication | 33rd International Conference on Machine Learning, ICML 2016 |

Editors | Kilian Q. Weinberger, Maria Florina Balcan |

Publisher | International Machine Learning Society (IMLS) |

Pages | 3495-3503 |

Number of pages | 9 |

ISBN (Electronic) | 9781510829008 |

State | Published - Jan 1 2016 |

Event | 33rd International Conference on Machine Learning, ICML 2016 - New York City, United States Duration: Jun 19 2016 → Jun 24 2016 |

### Publication series

Name | 33rd International Conference on Machine Learning, ICML 2016 |
---|---|

Volume | 5 |

### Other

Other | 33rd International Conference on Machine Learning, ICML 2016 |
---|---|

Country | United States |

City | New York City |

Period | 6/19/16 → 6/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

*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).