Ilse Ipsen, North Carolina State University

Abstract

For full-rank least squares regression problems under a Gaussian linear model,  we analyze the uncertainties when the minimum-norm solution is computed by random row-sketching and, in particular random row sampling. Our expressions for the total expectation and variance of the solution - with regard to both model- and algorithm-induced uncertainties - are exact; hold for general sketching matrices; and make no assumptions on the rank of the sketched matrix. They show that expectation and variance are governed by the rank-deficiency and spatial geometry induced by the sketching process, rather than by structural properties of specific sketching or sampling methods.
From a deterministic perspective, our structural perturbation bounds imply that least squares solutions are less sensitive to multiplicative perturbations than to additive perturbations.  From a probabilistic perspective, we show that the differences between the total bias and variance on the one hand, and the model bias and variance on the other hand, are governed by two factors: (i) the expected rank deficiency of the sketched matrix, and (ii) the expected difference between projectors onto the spaces of the  original and the sketched problems.
This is joint work with Jocelyn Chi.