This post is inspired by N. Higham post "What is Random Orthogonal matrix?".

In this post, N. Higham links to the two papers:

that illustrate $\mathcal O\left(\frac{4n^3}{3}\right)$ algorithms to construct a Haar distributed random orthogonal matrix based on Householder matrices and Givens rotations, respectively.

  1. Is $\mathcal O(N^3)$ a proven complexity bound?
  2. Is there any progress in the generation of random orthogonal matrices that are faster than $\mathcal O(N^3)$ or, at least, $\mathcal O\left(\frac{4n^3}{3}\right)$?

In this post on C++ generation of Random orthogonal matrices, I found a link to the paper preprint by F. Mezzardi which was an interesting read but was focused on other aspects of the random orthogonal matrix generations (different distributions, following of the generated matrix to the given distribution). In this question, I am more interested in speed and complexity.

  • $\begingroup$ What do you mean by "construct"? I would guess that the Lapack way to store an orthogonal matrix in a lower triangular one allows you to "construct" a random orthogonal in O(N^2), in the sense that it takes O(n^2) to construct the representation and O(n^2) to compute a vector product $Qv$ or $Q^*v$. $\endgroup$ Apr 26, 2020 at 7:55
  • $\begingroup$ Also, surely one can do better than $\Theta(N^3)$, because Strassen and Coppersmith-Winograd and all that business. $\endgroup$ Apr 26, 2020 at 7:56


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.