Abstract
We consider the solution of full-rank column regression problems, arising from Gaussian linear models, by randomized (row-wise sampling and sketching) algorithms. Motivated by the ground breaking work of Ma, Mahoney and Yu, we analyze expectation and variance of the minimum-norm solution with regard to both, model- and algorithm-induced uncertainties. Our expressions are exact, hold for general sketching matrices, and make no assumptions on the rank of the sketched matrix. We show that the relative differences between the total bias and variance, compared to the model bias and variance, respectively, are governed by two factors: (i) the expected rank deficiency of the sketched matrix, and (ii) the expected difference between projectors associated with the original and the sketched problems. The structural perturbation bounds imply that least squares problems are less sensitive to multiplicative perturbations than to additive perturbations. This is joint work with Jocelyn Chi.