### Abstract

We give faster algorithms and improved sample complexities for the fundamental problem of estimating the top eigenvector. Given an explicit matrix A € R^{n×d}, we show how to compute an e approximate top eigenvector of A^{T}A in time O (jnnz(A) + • log l/ϵ). Here nnz(A) is the number of nonzeros in A, sr(A) is the stable rank, and gap is the relative eigengap. We also consider an online setting in which, given a stream of i.i.d. samples from a distribution V with covariance matrix E and a vector xq which is an O(gap) approximate top eigenvector for E, we show how to refine xo to an € approximation using O j samples from V. Here v(P) is a natural notion of variance. Combining our algorithm with previous work to initialize xo, we obtain improved sample complexities and runtimes under a variety of assumptions on V. We achieve our results via a robust analysis of the classic shift-and-invert preconditioning method. This technique lets us reduce eigenvector computation to approximately solving a scries of linear systems with fast stochastic gradient methods.

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

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

### 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 'Faster eigenvector computation via shift-and-invert preconditioning'. Together they form a unique fingerprint.

## Cite this

*33rd International Conference on Machine Learning, ICML 2016*(pp. 3886-3894). (33rd International Conference on Machine Learning, ICML 2016; Vol. 6). International Machine Learning Society (IMLS).