Nyström Gram Matrix Low-Rank Approximation with Diagonal Sampling

Nyström Gram Matrix Low-Rank Approximation with Diagonal Sampling is a randomized low-rank kernel approximation algorithm analyzed by Drineas and Mahoney (2005) that approximates an n x n symmetric positive semidefinite (SPSD) Gram matrix G = X^T X using only c << n sampled columns in O(c^2 n) time and O(c n) space. The algorithm samples c columns of G in i.i.d. trials according to an importance distribution p_i >= beta G_{ii}^2 / sum_{j=1}^n G_{jj}^2, forms the rescaled n x c column sketch C = G S and c x c principal intersection sketch W = S^T G S (where S_{i_t, t} = 1 / sqrt(c p_{i_t})), computes the best rank-k Moore-Penrose pseudoinverse W_k^+ of W, and outputs the rank-k symmetric positive semidefinite approximation tilde{G}_k = C W_k^+ C^T = G S (S^T G S)_k^+ S^T G. Lemma 4 establishes the exact matrix factorization tilde{G}_k = X^T hat{U}_k hat{U}_k^T X where hat{U}_k = X S V_{W,k} Sigma_{W,k}^{-1/2} has orthonormal columns, yielding the norm identities ||G - tilde{G}_k||_2 = ||X - hat{U}_k hat{U}_k^T X||_2^2 and ||G - tilde{G}_k||_F = ||X^T X - X^T hat{U}_k hat{U}_k^T X||_F, while Theorem 3 proves that c = O(k / epsilon^4) columns suffice for ||G - tilde{G}_k||_xi <= ||G - G_k||_xi + epsilon sum_{i=1}^n G_{ii}^2 for both spectral (xi = 2) and Frobenius (xi = F) norms.