Suppose we are given $m$ vectors $v_1, \dots, v_m$ in $n$-dimensional space $\mathbf R^n$ (or perhaps they are specified up to $b$ bits of precision). I would like to find an orthonormal basis for the subspace perpendicular to $v_1, \dots, v_m$. I could do this by Gram-Schmidt but this would appear to take roughly $(m+n)^3$ time in serial, and cannot be done at all in parallel. Maybe we can assume $m = O(n)$ if this simplifies things.

Are there better algorithms for this? This seems closely related to matrix inversion so one should expect algorithms running in time $n^{\omega}$ (serial) or NC algorithms in time $\log^2 n$ (in parallel). Any references or key words would be greatly appreciated.

  • $\begingroup$ It sounds like you want a QR factorization in $n^\omega$ time. From the matrix pseudoinverse (which I know for sure can be computed in $n^\omega$) you can get a projection matrix for the orthogonal complement of the span of $v_i$. There should be some easy way to get an orthonormal basis from that, but I am not quite seeing it. $\endgroup$ Aug 1, 2014 at 16:11
  • $\begingroup$ I think Schonhage's paper "Fast Schmidt orthogonalization and unitary transformations of large matrices" from 1973 answers your question. But I can't find it. $\endgroup$ Aug 1, 2014 at 16:23


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy