Faster Least Squares Approximation via Randomized Hadamard Preconditioning

Faster Least Squares Approximation via Randomized Hadamard Preconditioning is a randomized sketch-and-solve algorithm for overconstrained l_2 regression min_{x in R^d} ||b - A x||_2 (with n >> d) introduced by Drineas, Mahoney, Muthukrishnan, and Sarlos (2011) that beats the classical O(n d^2) QR/SVD complexity in O(n d log n + d^3 log^2 n / epsilon) time. Algorithm 1 preconditions the design matrix A and response b by a Randomized Hadamard Transform H D (where D = diag(sigma_1, ..., sigma_n) has i.i.d. Rademacher +/-1 signs and H is the normalized n x n Walsh-Hadamard matrix), uniformly samples and rescales r = O(d log n log(d log n) + d log n / epsilon) rows via S^T, and computes tilde{x}_opt = (S^T H D A)^+ S^T H D b. The analysis decouples the random projection X = S^T H D from the linear-algebraic perturbation via two deterministic structural conditions on the column orthonormal basis U_A of A and orthogonal residual b^perp = b - A x_opt (Equations 8-9): (i) sigma_min^2(X U_A) >= 1/sqrt(2) and (ii) ||U_A^T X^T X b^perp||_2^2 <= epsilon Z^2 / 2 (where Z = ||b^perp||_2), under which Lemma 1 and Lemma 2 prove both the residual bound ||b - A tilde{x}_opt||_2 <= (1 + epsilon) Z and the parameter error bound ||x_opt - tilde{x}_opt||_2 <= sqrt(epsilon) (kappa(A) sqrt(gamma^{-2} - 1)) ||x_opt||_2.