A Kaczmarz-Inspired Method for Orthogonalization

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 (\mathrm{\mid }A\mathrm{\mid })$ where $\mathrm{\mid }A\mathrm{\mid }=(A^{\ast }A{)}^{1\mathrm{/}2}$. We show that $O(n^2\log (1\mathrm{/}(\det (\mathrm{\mid }A\mathrm{\mid })\epsilon )))$ iterations suffice to bring $\det (\mathrm{\mid }A\mathrm{\mid })$ above $1-\epsilon$ with constant probability.