2
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\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$ – Federico Poloni Apr 26 '20 at 7:55
  • $\begingroup$ Also, surely one can do better than $\Theta(N^3)$, because Strassen and Coppersmith-Winograd and all that business. $\endgroup$ – Federico Poloni Apr 26 '20 at 7:56

Your Answer

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

Browse other questions tagged or ask your own question.