##
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
eﬀectiveness 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.

Speciﬁcally, 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 diﬀerence between orthogonal and oblique projectors with the same
range.

This is joint work with Jocelyn Chi (UCLA).

North Carolina State University

Email address: ipsen@ncsu.edu