Projection onto the set of Orthogonal matrices

Question

Let $M \in \mathbb{R}^{n \times n}$ and denote the set of Orthogonal matrices by \begin{equation} \mathcal{O}_{n} = \left\lbrace Q \in \mathbb{R}^{n \times n} \colon QQ^{T} = \mathbb{I}_{n} \right\rbrace . \end{equation}

What is an efficient way to find the projection of an arbitrary matrix $M \in \mathbb{R}^{n \times n}$ onto $\mathcal{O}_{n}$.

One approach I can find is to compute the Singular Value Decomposition of $M$, namely, \begin{equation} M = U \Sigma V^{T} . \end{equation} Then we have \begin{equation} Q = UV^{T} . \end{equation}

Is there any other approach besides this SVD?

Answer 1

Some thoughts on a particular case of low-rank matrices ($k=\text{rank}(M)\ll n)$. Here, I can suggest some economical version of SVDs:

Rand-SVD

Here is the R package documentation that also contains references for canonical papers of V. Rokhlin and P. Martinsson on this topic. That should reduce the complexity to $\mathcal O(nk^2+k^3)$ as opposed to $\mathcal O(n^3)$ for dense SVD.

ACA-based

1. Find (or if you start with one) low-rank representation of matrix $M=AB^T$, where $A,B\in\mathbb R^{n\times k}$. This might come from "physics" (if the matrix $M$ comes from the discretization) or, by using a pure linear algebra approach like ACA (adaptive cross approximation) (usually at $\mathcal O(nk^2)$).
2. Find QR of $A$ and $B$ in $\mathcal O(nk^2)$ resulting in $A=Q_AR_A$, $B=Q_BR_B$, where $Q_A, Q_B\in\mathbb R^{n\times k}$ and $R_A,R_B\in\mathbb R^{k\times k}$, upper triangular.
3. Find $P = R_A R_B$ in $\mathcal O(k^3)$.
4. Compute SVD of $P$ in $\mathcal O(k^3)$ resulting in $P=U_P\Sigma V_P^T$. Here, $U_P, \Sigma, V_P \in \mathbb R^{k\times k}$, $\Sigma$ - diagonal. Notice, $\Sigma$ is the matrix of singular values not only for $P$, but for the original $M$, as well.
5. Find $U=Q_AU_P$ and $V=Q_BV_P$ in $\mathcal O(nk^2)$.
6. Now you have an SVD of $M=U\Sigma V^T$ in total of $\mathcal O(nk^2+k^3)$ operations.