<p>I have a huge covariance matrix, , with the dimension, e.g., <span class="math-container">$10^8 \times 10^8$</span>. Luckily enough, the number of nonzero eigenpairs, <span class="math-container">$n$</span>, is very small, i.e., <span class="math-container">$n&lt;5$</span>. From the computational prospective, I would like to represent, <span class="math-container">$M$</span>, in Schmidt decompsition as
<span class="math-container">$$
= \sum_{i=1}^n \lambda_i {\bf e}_i^T \otimes {\bf e}_i,
$$</span>
where <span class="math-container">$\lambda_i$</span> and <span class="math-container">${\bf e}_i$</span> are the nonzero eigenvalues and eigenvectors of <span class="math-container">$M$</span>. This equation can be further written as
<span class="math-container">$$
= \sum_{i=1}^n {\bf g}_i^T \otimes {\bf g}_i,
$$</span>
where the vectors <span class="math-container">${\bf g}_i=\sqrt{\lambda_i}{\bf e}_i$</span>. Using this relation, the matrix, <span class="math-container">$M$</span>, can be stored in terms of nonzero <span class="math-container">${\bf g}_i$</span> in computer.</p>
<p>My problem is that the matrix, , is changing at every time snapshot. The update of the matrix, , is given by the following formular,
<span class="math-container">$$
′= \sum_{i=1}^n {\bf g}_i^T \otimes ({\bf g}_i+ \delta {\bf g}_i)+({\bf g}_i+ \delta {\bf g}_i)^T \otimes {\bf g}_i
$$</span>
where <span class="math-container">$\delta {\bf g}_i$</span> is the update of the <span class="math-container">$i$</span>th vector and is small comparing with <span class="math-container">${\bf g}_i$</span>. Due to some dynamical properties/constraints, the updated covariance matrix, <span class="math-container">$M'$</span>, contains the same number of nonzero eigenpairs, <span class="math-container">$n$</span>.</p>
<p>I wonder whether there is a fast algorithm for computing the new nonzero eigenpairs?</p>
<p>Many thanks in advance!</p>

CC BY-SA 4.0
2020-06-23T20:31:11.927Z
You could use an iterative decomposition algorithm (like Lanczos or Arnoldi) with one of the singular vectors of the previous time step as a starting vector for the current time step. This speeds up convergence significantly. I am not aware of any theoretical bounds on number of iterations, but a good place to start might be Saad's books: https://www-users.cs.umn.edu/~saad/books.html
delete000
CC BY-SA 4.0
2020-06-24T08:47:51.753Z
Yes, many thanks for your help. Indeed, this method works.
Juan
CC BY-SA 4.0
2020-06-26T08:24:25.970Z
Cross-posted: https://cstheory.stackexchange.com/q/47056/5038, https://math.stackexchange.com/q/3723906/14578.  Please [do not post the same question on multiple sites](https://meta.stackexchange.com/q/64068).
D.W.
<ds.algorithms><matrices>
Is there a fast algorithm for computing the Schmidt decomposition
Juan
# Is there a fast algorithm for computing the Schmidt decomposition

(Asked by: username_0 on 2020-06-17)

I have a huge covariance matrix, , with the dimension, e.g., $10^8 \times 10^8$. Luckily enough, the number of nonzero eigenpairs, $n$, is very small, i.e., $n<5$. From the computational prospective, I would like to represent, $M$, in Schmidt decompsition as
$$
= \sum\_{i=1}^n \lambda\_i {\bf e}\_i^T \otimes {\bf e}\_i,
$$
where $\lambda\_i$ and ${\bf e}\_i$ are the nonzero eigenvalues and eigenvectors of $M$. This equation can be further written as
$$
= \sum\_{i=1}^n {\bf g}\_i^T \otimes {\bf g}\_i,
$$
where the vectors ${\bf g}\_i=\sqrt{\lambda\_i}{\bf e}\_i$. Using this relation, the matrix, $M$, can be stored in terms of nonzero ${\bf g}\_i$ in computer.

My problem is that the matrix, , is changing at every time snapshot. The update of the matrix, , is given by the following formular,
$$
′= \sum\_{i=1}^n {\bf g}\_i^T \otimes ({\bf g}\_i+ \delta {\bf g}\_i)+({\bf g}\_i+ \delta {\bf g}\_i)^T \otimes {\bf g}\_i
$$
where $\delta {\bf g}\_i$ is the update of the $i$th vector and is small comparing with ${\bf g}\_i$. Due to some dynamical properties/constraints, the updated covariance matrix, $M'$, contains the same number of nonzero eigenpairs, $n$.

I wonder whether there is a fast algorithm for computing the new nonzero eigenpairs?

Many thanks in advance!

**Tags:** ds.algorithms, matrices

> **Comments:**
> **username_1**: You could use an iterative decomposition algorithm (like Lanczos or Arnoldi) with one of the singular vectors of the previous time step as a starting vector for the current time step. This speeds up convergence significantly. I am not aware of any theoretical bounds on number of iterations, but a good place to start might be Saad's books: https://www-users.cs.umn.edu/~saad/books.html  
> **username_0**: Yes, many thanks for your help. Indeed, this method works.  
> **username_2**: Cross-posted: https://cstheory.stackexchange.com/q/47056/5038, https://math.stackexchange.com/q/3723906/14578.  Please [do not post the same question on multiple sites](https://meta.stackexchange.com/q/64068).  

---

## 0 answers

