Relative-Error CUR Matrix Decomposition via Subspace Leverage Sampling

Relative-Error CUR Matrix Decomposition via Subspace Leverage Sampling is a randomized low-rank matrix factorization framework introduced by Drineas, Mahoney, and Muthukrishnan (2008) that approximates an arbitrary matrix A in R^{m x n} by actual columns C in R^{m x c} and actual rows R in R^{r x n} of A together with an explicit linking matrix U = W^+ in R^{c x r} so as to achieve a multiplicative (1 + epsilon) relative-error Frobenius norm guarantee ||A - C U R||_F <= (1 + epsilon)||A - A_k||_F. Rather than sampling columns proportionally to raw Euclidean column norms ||A^{(j)}||_2^2 (which permits only additive error bounds), Algorithm 1 samples c = O(k log k / epsilon^2) columns according to the normalized k-right-singular-subspace leverage scores p_j = (1/k)||(V_{A,k})_{(j)}||_2^2 (forming C = A S_C D_C and the optimal CX approximation P_C A = C (C^+ A)), and Algorithm 2 subsequently samples r = O(c log c / epsilon^2) rows of A and C concurrently according to the column-subspace leverage scores q_i = (1/c)||(U_C)_{(i)}||_2^2 of C, setting W = D_R S_R^T C and U = W^+. The analysis reduces column/row projection to generalized l_2 regression via Lemma 1 (Equations 26-27), proving that when sigma_k(S^T U_{A,k}) >= 1/sqrt(2), the rescaled sketch satisfies (S A_k)^+ = V_{A,k} Sigma_{A,k}^{-1} (S U_{A,k})^+ and rank(S A_k) = k.