A STRUCTURAL MATRIX PERTURBATION THEORY FOR RANDOMIZED ALGORITHMS

ILSE C.F. IPSEN

We present a multiplicative matrix perturbation theory as the foundation for the error analysis of randomized algorithms, and in particular those algorithms that achieve their speed by judiciously sampling selected rows or columns of real/complex matrices. The accuracy of the sampled problem is usually analysed in two stages: A structural (deterministic) perturbation theory followed by a probabilistic analysis. Since the sampled problem tends to have much smaller dimension, it cannot be represented as an additive perturbation.

Thus we propose a multiplicative perturbation theory, and demonstrate its effectiveness on real least squares/regression problems that are generalized in two aspects: (i) instead of a single right-hand side, the problem can have multiple right-hand sides, and (ii) instead of the 2-norm, the problem can be expressed in any Schatten \(p\)-norm.

Specifically, our work represents an extension of Maher’s results on Schatten p-norms. We express the exact and perturbed least squares solutions in terms of projectors that have an easy geometric interpretation. We also present a geometric interpretation of the action of the sampling matrix in terms of relevant subspaces. We show that a key quantity for assessing the accuracy of the sampled solution can often be expressed as the tangent of the largest principal angle between two subspaces. We provide additional interpretation of the difference between orthogonal and oblique projectors with the same range.

This is joint work with Jocelyn Chi (UCLA).

North Carolina State University