A Kaczmarz-Inspired Method for Orthogonalization

Abstract

This paper asks if the following iterative procedure approximately orthogonalizes a set of $n$ linearly independent unit vectors while preserving their span: in each iteration, access a random pair of vectors and replace one with the component perpendicular to the other, renormalized to be a unit vector. We provide a positive answer: any given set of starting vectors converges almost surely to an orthonormal basis of their span. We specifically argue that the $n$-volume of the parallelepiped generated by the vectors approaches 1 (i.e. the parallelepiped approaches a hypercube). If $A$ is the matrix formed by taking these vectors as columns, this volume is simply $\det (|A|)$ where $|A|=(A^{\ast }A{)}^{1/2}$. We show that $O(n^2\log (1/(\det (|A|)\epsilon )))$ iterations suffice to bring $\det (|A|)$ above $1-\epsilon$ with constant probability.

arXiv commentA previous version required $O(n^4/{\epsilon }^2)$ additional iterations to achieve convergence over what this version does. The first version used a slightly different potential function than logdet. We made a stronger claim about this potential function than was true; the analogous claim is true for the logdet so the remaining proofs follow with only minor alteration