这篇文章的灵感来自N. Higham 的帖子“什么是随机正交矩阵？” .

在这篇文章中，N. Higham 链接到两篇论文：

• GW Stewart，随机正交矩阵的有效生成与条件估计器的应用，SIAM J. Numer。肛门。17(3), 403–409, 1980。
• TW Anderson、I. Olkin 和 LG Underhill，随机正交矩阵的生成，SIAM J. Sci。统计学家。计算。8(4), 625–629, 1987。

说明$\mathcal O\left(\frac{4n^3}{3}\right)$分别基于 Householder 矩阵和 Givens 旋转构建 Haar 分布随机正交矩阵的算法。

1. 是$\mathcal O(N^3)$已证明的复杂性界限？
2. 随机正交矩阵的生成速度是否比$\mathcal O(N^3)$或者至少，$\mathcal O\left(\frac{4n^3}{3}\right)$?

在这篇关于随机正交矩阵的 C++ 生成的帖子中，我找到了F. Mezzardi 的论文预印本的链接，这是一篇有趣的阅读文章，但侧重于随机正交矩阵生成的其他方面（不同的分布，生成矩阵的后续给定的分布）。在这个问题上，我对速度和复杂性更感兴趣。