Home / Curated / Algorithms / Randomized Block Krylov Iteration for Gap-Independent Approximate SVD and Principal Component Analysis

Randomized Block Krylov Iteration for Gap-Independent Approximate SVD and Principal Component Analysis

Algorithms AIMech:RandomizedBlockKrylovMethodsForApproximateSingularValueDecomposition DRAFT

Aliases: Musco-Musco Randomized Block Krylov Iteration, Gap-Independent Randomized Block Lanczos SVD, Chebyshev-Accelerated Randomized Subspace Iteration for SVD and PCA

Randomized Block Krylov Iteration for Gap-Independent Approximate SVD and Principal Component Analysis is a randomized matrix-decomposition algorithm introduced and analyzed by Cameron Musco and Christopher Musco (2015) that computes an approximate rank-k singular value decomposition of any matrix A in R^{n x d} by drawing a random sketching matrix Pi ~ N(0, 1)^{d x k}, explicitly forming the block Krylov subspace K = [A Pi, (A A^T) A Pi, ..., (A A^T)^q A Pi] in R^{n x (q+1)k} for q = Theta(log(d) / sqrt(epsilon)) iterations, orthonormalizing the columns of K into Q in R^{n x (q+1)k}, computing the top k singular vectors U_bar_k of the projected matrix M = Q^T A A^T Q, and returning Z = Q U_bar_k, achieving (1 + epsilon) spectral-norm and Frobenius-norm low-rank approximation error as well as epsilon * sigma_{k+1}^2 per-vector principal component variance accuracy in O(nnz(A) k log(d) / sqrt(epsilon)) gap-independent time.

Identity Notes & Concept Scope Distinct from generic PrincipalComponentAnalysis (AIO:PrincipalComponentAnalysis) and DimensionalityReduction (AIO:DimensionalityReduction), which do not specify randomized block Krylov subspace construction or Chebyshev polynomial spectral tail suppression. Distinct from AIMech:CountSketchInputSparsitySubspaceEmbeddingAndRegression (Round 331) and AIMech:RelativeErrorCURMatrixDecompositionViaSubspaceLeverageSampling (Round 332), which are non-iterative input-sparsity sketching and column-row subset selection methods providing Frobenius-norm low-rank approximation rather than gap-independent O(log(d)/sqrt(epsilon)) spectral-norm and per-vector PCA variance bounds. Also distinct from AIMech:ShiftAndInvertPreconditioningForFasterEigenvectorComputation (Round 354), which accelerates top-1 eigenvector computation under an explicit relative eigengap via SVRG linear system solves on (lambda I - A)^{-1} rather than gap-independent rank-k block Krylov subspace projection.

Claims & Grounded Evidence

3 Claims

Mechanism #r355-claim-chebyshev-minimizing-polynomial-and-subspace-error-lemma

For any threshold alpha > 0, gap gamma in (0, 1], and odd degree q >= 1, the rescaled Chebyshev polynomial p(x) = (1 + gamma)*alpha * T_q(x/alpha) / T_q(1 + gamma) contains only odd-degree monomials and satisfies p((1+gamma)alpha) = (1+gamma)alpha, p(x) >= x for all x >= (1+gamma)alpha, and |p(x)| <= alpha / 2^{q*sqrt(gamma) - 1} for all x in [0, alpha] (Lemma 5), which implies that with probability 99/100 over Pi ~ N(0, 1)^{d x k}, the rank-l Frobenius residual error E(Z_l, A) = ||A_l||_F^2 - ||Z_l Z_l^T A||_F^2 of Block Krylov Iteration (Algorithm 2) after q = Theta(log(d/epsilon)/sqrt(epsilon)) iterations satisfies (1) E(Z_l, A) <= (epsilon/2) * sigma_{k+1}^2 for all l <= m (where m is the count of singular values >= (1+epsilon/2)sigma_{k+1}), (2) E(Z_l, A) <= E(Z_{l-1}, A) + 3*epsilon*sigma_{k+1}^2 for all l <= k, and (3) E(Z_l, A) <= (w + 1)*3*epsilon*sigma_{k+1}^2 where w counts singular values in [sigma_k/(1+epsilon/2), sigma_k) (Lemma 9).

supports Source: Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decomposition · Locator: Section 2.1, Algorithm 2, p. 3; Section 4.4, Lemma 5, p. 8; Section 6.1, Definition 8 and Lemma 9, pp. 10-14; Appendix A, pp. 19-21

Mechanism #r355-claim-gap-independent-spectral-frobenius-and-per-vector-pca-bounds

With probability at least 99/100, Randomized Block Krylov Iteration (Algorithm 2) in q = O(log(d)/sqrt(epsilon)) iterations and total runtime O(nnz(A) k log(d)/sqrt(epsilon) + n k^2 log^2(d)/epsilon + k^3 log^3(d)/epsilon^{3/2}) (Theorem 7) returns orthonormal columns Z = [z_1, ..., z_k] simultaneously achieving gap-independent (1 + epsilon) spectral-norm error ||A - Z Z^T A||_2 <= (1 + epsilon)||A - A_k||_2 (Theorem 10), (1 + epsilon) Frobenius-norm error ||A - Z Z^T A||_F <= (1 + epsilon)||A - A_k||_F (Theorem 11), and per-vector principal component variance accuracy |u_i^T A A^T u_i - z_i^T A A^T z_i| <= epsilon * sigma_{k+1}^2 for every i in {1, ..., k} (Theorem 12).

supports Source: Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decomposition · Locator: Section 2.3, Theorem 1, p. 4; Section 5.2, Theorem 7, pp. 9-10; Section 6.2, Theorems 10, 11, and 12, pp. 14-15; Appendix A, Lemma 15, pp. 21-22

Mechanism #r355-claim-oversampled-gap-dependent-convergence-with-spectral-decay

When initialized with an oversampled Gaussian matrix Pi ~ N(0, 1)^{d x p} for any p >= k, Block Krylov Iteration achieves all three approximation guarantees (1), (2), and (3) with probability at least 99/100 in q = Theta(log(d/epsilon) / sqrt(min{1, sigma_k / sigma_{p+1} - 1})) iterations (Theorem 13), replacing dependence on the adjacent singular value gap sigma_k / sigma_{k+1} - 1 with the larger oversampled spectral decay ratio sigma_k / sigma_{p+1} - 1.

supports Source: Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decomposition · Locator: Section 7, Theorem 13, pp. 15-16

⚠️ Curated Limitations & Negative Results

Requires storing and orthonormalizing an n x (q k) Krylov basis Q in memory (O(n k log(d)/sqrt(epsilon)) space) and performing block reorthogonalization at each iteration to maintain numerical stability (Section 5.2, p. 9).

Artificial Intelligence Ontology (AIO) Grounding

Mapped AIO Classes

AIO Target Class	Mapping Relation	Mapping Rationale
`AIO:PrincipalComponentAnalysis` Principal Component Analysis	related_match	Computes provably accurate top-k principal components with per-vector variance guarantees.
`AIO:DimensionalityReduction` Dimensionality Reduction	related_match	Constructs rank-k subspace projections minimizing spectral and Frobenius reconstruction error.

Evidence Sources & Primary Literature

3 Sources

Source ID	Publication / Document	Type / Access	Reference & Checksum
`r355-primary-pdf`	Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decomposition Cameron Musco, Christopher Musco	primary paper full_text	ID: https://dblp.org/rec/conf/nips/MuscoM15.xml sha256:3a18b5d13eaf…
`r355-arxiv-abs`	Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decomposition (arXiv abstract) Cameron Musco, Christopher Musco	primary paper abstract_only	ID: https://arxiv.org/abs/1504.05477 sha256:2d8cd5a1f911…
`r355-metadata-cr`	Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decomposition (Crossref metadata) Cameron Musco, Christopher Musco	primary paper abstract_only	ID: https://dblp.org/rec/conf/nips/MuscoM15.xml sha256:0b8fa245406a…

Ontology & Grounding Topology

Open in interactive network graph →

Curation Provenance

Curator: Antigravity

Method: ai_assisted

Model: Gemini

Created: 2026-10-19T07:18:00Z

Updated: 2026-10-19T07:18:00Z

Source File: data/curated/RandomizedBlockKrylovMethodsForApproximateSingularValueDecomposition.yaml · Schema: curated_concept.yaml

Explore across X-Mech

Related computational & biological Mechs: Embedding Map Network Graph ProteinTraitsMech (ESM-2 pLM) DUFMech (Domain pLM) TraitMech CultureMech All 14 X-Mech Repositories