2
$\begingroup$

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?

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

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.
$\endgroup$
  • $\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$ – mortal Feb 12 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 at 21:41
  • 1
    $\begingroup$ (by a wider subclass, I meant, compared to low-rank matrices) $\endgroup$ – Anton Menshov Feb 12 at 22:11
  • $\begingroup$ thanks for your kind opinion. I will have a look more on my matrices $\endgroup$ – mortal Feb 13 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.