0
$\begingroup$

Suppose we have a diagonalizable (possibly positive semidefinite, if it helps. But not symmetric) square matrix $A \in \mathbb{R}^{M\times M}$. We can perform an Eigenvalue decomposition $A = V \Lambda V^{-1}$, with the matrix of Eigenvalues $\Lambda = \text{diag}(\lambda_i)$ and the matrix of Eigenvectors $V$.

Let's say some Eigenvalues are zero, therefore $\text{rank}(A)=N<M$. In similar fashion to the Singular Value decomposition, we can order the Eigenvalues by $|\lambda_i|$ and only keep the nonzero ones, so that we obtain $\tilde \Lambda \in \mathbb{R}^{N\times N}$. We remove the corresponding Eigenvectors of V so that we end up with $\tilde V \in \mathbb{R}^{M\times N}$. Similarly, the corresponding rows in $V^{-1}$ are removed as well (after the inversion) to obtain $\tilde V^{-1}$. Through this procedure, we get the exact result $A = \tilde V \tilde \Lambda \tilde V^{-1}$.

Now my question is: Can this procedure also be used as a low-rank approximation method if $|\lambda_i|\approx 0, i>N$, similar to the SVD? I haven't found this in the literature, so are there any caveats which make this method unreliable?

$\endgroup$

1 Answer 1

0
$\begingroup$

The key issue is that the eigenvalues are not necessarily orthogonal. Consider $$ \begin{bmatrix} 1 & 0 \\ 0 & 1\\ \end{bmatrix} = \begin{bmatrix} 100 & 1 \\ 1 & 0\\ \end{bmatrix} \begin{bmatrix} 1 & 0 \\ 0 & 1\\ \end{bmatrix} ( \begin{bmatrix} 100 & 1 \\ 1 & 0\\ \end{bmatrix} )^{-1} $$ If you try your method, you shall see some entries that are on the order of 100 while the entries of the original matrix are all single digits.

$\endgroup$
4
  • $\begingroup$ That doesn't seem to address my question, I'm afraid. The unit matrix has no $|\lambda_i|\approx 0$. Furthermore I can always normalize the Eigenvectors so the 100 in your example is not really an issue. Could you maybe clarify your answer? $\endgroup$ Aug 24, 2023 at 9:33
  • $\begingroup$ You shall at least first try what you said before commenting. 1. Normalizing the eigenvectors will not change anything. 2. The fact that this approximation fails badly on identity immediately implies it will fail on some examples with small lambda. $\endgroup$ Aug 24, 2023 at 12:07
  • $\begingroup$ If you want a counter-example with concrete numbers, try it out by replacing the second eigenvalue with 0.01, and replacing 100 with a bigger number, like 10000. Then compute the error of the SVD rank 1 approximation and the error of the suggested approximation. You will see a large difference. $\endgroup$ Aug 24, 2023 at 12:17
  • $\begingroup$ Thank you for the clarification, now I understand where the problem lies. $A$ can drastically deviate under the proposed approximation for particular EV decompositions. In order to get a reduced rank EV decomposition, the sensible way would be first performing a truncated SVD $A \approx \hat A = \hat U \hat \Sigma \hat V^T$ up to $N$, and then performing the EV decomp on $\hat A$. Does the truncated SVD guarantee that for $\hat A$ the EVs $\lambda_i=0$ for $i>N$? If so, I could perform my initial procedure on $\hat A$ without further loss of accuracy. $\endgroup$ Aug 24, 2023 at 14:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .