Truncated Power Method for Sparse Eigenvalue and Sparse PCA

Truncated Power Method for Sparse Eigenvalue and Sparse PCA (TPower) is a non-convex iterative hard-thresholding spectral algorithm introduced by Yuan and Zhang (2013) that approximates the k-sparse largest (or smallest) eigenvalue problem max_{x in R^p} x^T A x subject to ||x||_2 = 1 and ||x||_0 <= k for a symmetric positive semidefinite matrix A in R^{p x p}. Starting from a k-sparse unit vector x_0, each iteration t >= 1 computes the power-step vector g_t = A x_{t-1}, restricts g_t to the support F_t = supp(g_t, k) of its k largest-magnitude coordinates via the truncation operator Truncate(g_t, F_t), and normalizes x_t = Truncate(g_t, F_t) / ||Truncate(g_t, F_t)||_2. Under the sparse restricted eigenvalue/condition number ratio gamma_{k+2s} = rho_max(k+2s)/rho_min(k+2s) and a sparsity-over-relaxation factor k >= s (1 + 4/(gamma_{k+2s}-1)^{-2}) when the target eigenvector x_bar has support size |F_bar| = s, TPower monotonically increases the Rayleigh objective x_t^T A x_t and contracts geometrically in directional alignment |x_t^T x_bar| toward the true sparse principal eigenvector.