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 (\lvert A\rvert )$ where $\lvert A\rvert =(A^*A)^{1/2}$. We show that $O(n^2\log (1/\left (\det (\lvert A\rvert )\varepsilon \right )))$ iterations suffice to bring ${\det (\lvert A\rvert )}$ above $1-\varepsilon$ with constant probability.