Randomized block Krylov methods for stronger and faster approximate singular value decomposition

Cameron Musco, Christopher Musco

    Research output: Contribution to journalConference articlepeer-review


    Since being analyzed by Rokhlin, Szlam, and Tygert [1] and popularized by Halko, Martinsson, and Tropp [2], randomized Simultaneous Power Iteration has become the method of choice for approximate singular value decomposition. It is more accurate than simpler sketching algorithms, yet still converges quickly for any matrix, independently of singular value gaps. After Õ(1/∈) iterations, it gives a low-rank approximation within (1 + ∈) of optimal for spectral norm error. We give the first provable runtime improvement on Simultaneous Iteration: a randomized block Krylov method, closely related to the classic Block Lanczos algorithm, gives the same guarantees injust Õ (1/√∈) iterations and performs substantially better experimentally. Our analysis is the first of a Krylov subspace method that does not depend on singular value gaps, which are unreliable in practice. Furthermore, while it is a simple accuracy benchmark, even (1 + ∈) error for spectral norm low-rank approximation does not imply that an algorithm returns high quality principal components, a major issue for data applications. We address this problem for the first time by showing that both Block Krylov Iteration and Simultaneous Iteration give nearly optimal PCA for any matrix. This result further justifies their strength over non-iterative sketching methods.

    Original languageEnglish (US)
    Pages (from-to)1396-1404
    Number of pages9
    JournalAdvances in Neural Information Processing Systems
    StatePublished - 2015
    Event29th Annual Conference on Neural Information Processing Systems, NIPS 2015 - Montreal, Canada
    Duration: Dec 7 2015Dec 12 2015

    ASJC Scopus subject areas

    • Computer Networks and Communications
    • Information Systems
    • Signal Processing


    Dive into the research topics of 'Randomized block Krylov methods for stronger and faster approximate singular value decomposition'. Together they form a unique fingerprint.

    Cite this