Volume Sampling for Matrix Approximation and Projective Clustering

Volume Sampling for Matrix Approximation and Projective Clustering is a joint geometric row-subset sampling principle and adaptive low-rank approximation framework introduced by Deshpande, Rademacher, Vempala, and Wang (2006) that selects a subset S subseteq {1, ..., m} of k rows of a matrix A in R^{m x n} with probability p_S = Delta_S^2 / sum_{|T|=k} Delta_T^2 = det(A_S A_S^T) / sum_{|T|=k} det(A_T A_T^T) proportional to the squared k-dimensional simplex volume Delta_S = (1 / k!) sqrt(det(A_S A_S^T)) spanned by {a_i : i in S} and the origin. By combining the base-times-height simplex identity (k+1)^2 Delta_{S cup {j}}^2 = d(a_j, H_S)^2 Delta_S^2 (Lemma 3.1) with the Cauchy-Binet elementary symmetric polynomial identity sum_{|S|=k} (k!)^2 Delta_S^2 = e_k(sigma_1^2, ..., sigma_n^2) (Lemma 3.3, Equation 3.5), Theorem 1.2 proves the exact expected residual formula E_S[||A - pi_{H_S}(A)||_F^2] = (k + 1) e_{k+1}(sigma_1^2, ..., sigma_n^2) / e_k(sigma_1^2, ..., sigma_n^2) <= (k + 1)||A - A_k||_F^2, establishing the first multiplicative row-subset existence bound (matching the asymptotic lower bound of Proposition 4.1) and, when combined with adaptive residual length-squared sampling (Theorem 1.3 & Theorem 1.4), yielding PTAS (1 + epsilon) algorithms for rank-k matrix approximation and projective clustering.