Leverage Scores: Sensitivity and Applications to Randomized Algorithms.

摘要

In this thesis, we present various results pertaining to a matrix property called leverage scores and their application to randomized row sampling. We begin by investigating three uniform strategies for randomized row sampling from matrices with orthonormal columns (without replacement, with replacement, and Bernoulli sampling). Our analysis is focused on the two-norm condition number of the sampled matrices due to it's applications to the generation of efficient preconditioners for the randomized least squares solver Blendenpik. As part of our analysis, we present probabilistic bounds on the condition number of the sampled matrix in terms of both leverage scores and coherence (the largest leverage score). We also develop algorithms for generating test matrices with specified leverage scores.;Next, we derive leverage score perturbation bounds. These bounds show that the leverage scores of the perturbed matrix are close to the leverage scores of the original matrix if the two norm of the perturbation and the two norm of the left pseudoinverse of the original matrix are small. We also bound the change in the leverage scores in terms of the principal angles between the original matrix and the perturbed matrix.;Finally, we present kappa_SQ, a Matlab software package and GUI designed to run experiments on the two-norm condition number of a sampled matrix and produce paper-ready plots.