Projection onto the set of Orthogonal matrices

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

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, $$$$M = U \Sigma V^{T} .$$$$ Then we have $$$$Q = UV^{T} .$$$$

Is there any other approach besides this SVD?

• This is a duplicate of math.stackexchange.com/questions/2215359/… – Brian Borchers Feb 12 at 5:27
• Thanks @BrianBorchers. What I'm looking for is another approach than SVD – mortal Feb 12 at 11:10
• Create two orthogonal matrices $Q_L,Q_R$ by QR'ing two random n x n matrices. Then use the formula $M\approx Q_LQ_L^TMQ_RQ_R^T$ to find the projection. This is essentially a change of basis on both the row and column spaces. Unfortunately QR costs the same asymptotically as SVD; orthogonal matrix generation is always gonna be expensive – sssssssssssss Feb 12 at 12:05

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.
• thanks! so unless we know more about the structure of our matrix, otherwise there is no algorithm more efficient than SVD in general right? – mortal Feb 12 at 19:27
• @mortal At least, I am not aware of such an algorithm in general case. There might be some other randomized orthogonalization algorithm that gives decent results/complexity for a general case (or wider subclass of matrices), but I do not know that. Also, the origin of the matrix might be of interest, as some algorithms require and can benefit from the "physics" rather than be purely algebraical. – Anton Menshov Feb 12 at 21:41
• (by a wider subclass, I meant, compared to low-rank matrices) – Anton Menshov Feb 12 at 22:11
• thanks for your kind opinion. I will have a look more on my matrices – mortal Feb 13 at 12:10