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?

  • 3
    $\begingroup$ This is a duplicate of math.stackexchange.com/questions/2215359/… $\endgroup$ Feb 12, 2019 at 5:27
  • $\begingroup$ Thanks @BrianBorchers. What I'm looking for is another approach than SVD $\endgroup$
    – JKay
    Feb 12, 2019 at 11:10
  • 2
    $\begingroup$ 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 $\endgroup$ Feb 12, 2019 at 12:05

1 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:


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.


  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.
  • $\begingroup$ thanks! so unless we know more about the structure of our matrix, otherwise there is no algorithm more efficient than SVD in general right? $\endgroup$
    – JKay
    Feb 12, 2019 at 19:27
  • 1
    $\begingroup$ @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. $\endgroup$
    – Anton Menshov
    Feb 12, 2019 at 21:41
  • 1
    $\begingroup$ (by a wider subclass, I meant, compared to low-rank matrices) $\endgroup$
    – Anton Menshov
    Feb 12, 2019 at 22:11
  • $\begingroup$ thanks for your kind opinion. I will have a look more on my matrices $\endgroup$
    – JKay
    Feb 13, 2019 at 12:10

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.