1
$\begingroup$

Let $A$ be a square $n \times n$ matrix with SVD $A = U \Sigma V^T$. In Numerical Linear Algebra (Trefethen and Bau) it is shown that the symmetric $2n \times 2n$ matrix

$$H = \begin{pmatrix} 0 & A^T \\ A & 0\end{pmatrix}$$

satisfies the eigendecomposition

$$ \begin{pmatrix} 0 & A^T \\ A & 0\end{pmatrix} \begin{pmatrix} V & V \\ U & -U \end{pmatrix} = \begin{pmatrix} V & V \\ U & -U \end{pmatrix} \begin{pmatrix} \Sigma & 0 \\ 0 & -\Sigma \end{pmatrix}. \tag{1} $$

In particular, the singular values of $A$ are the absolute values of the eigenvalues of $H$.

After establishing this the authors seem to imply that by computing an eigendecomposition of $H$, we can compute an SVD of $A$. I fail to see how this is the case. Suppose that we have computed (say by QR iteration) an eigendecomposition $H = Q D Q^T$ where $D$ is a diagonal matrix and $Q$ is an orthogonal $2n \times 2n$ matrix. Since $D$ contains the eigenvalues of $H$, by permuting the columns of $Q$ if necessary we can assume that

$$D = \begin{pmatrix} \Sigma & 0 \\ 0 & -\Sigma \end{pmatrix}.$$

If we write

$$Q = \begin{pmatrix} Q_{11} & Q_{12} \\ Q_{21} & Q_{22} \end{pmatrix}$$

where the $Q_{ij}$'s are $n \times n$ blocks, then our computed eigendecomposition tells us that

$$ \begin{pmatrix} 0 & A^T \\ A & 0\end{pmatrix} \begin{pmatrix} Q_{11} & Q_{12} \\ Q_{21} & Q_{22} \end{pmatrix} = \begin{pmatrix} Q_{11} & Q_{12} \\ Q_{21} & Q_{22} \end{pmatrix} \begin{pmatrix} \Sigma & 0 \\ 0 & -\Sigma \end{pmatrix}. \tag{2} $$

Comparing $(1)$ and $(2)$, it's tempting to conclude that

$$Q_{11}=V=Q_{12}, Q_{21}=U=-Q_{22},$$

but obviously this need not be the case, since eigendecompositions are not unique. Of course, SVDs are not unique either, so perhaps it nevertheless holds that $A=Q_{21} \Sigma Q_{11}^T$. I have tried to prove (or disprove) whether this is the case, but I haven't had any luck. In fact, it's not even clear to me whether the $Q_{ij}$'s are orthogonal matrices.

Does anybody know how this $Q$ matrix can be used to get an SVD for $A$?

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Hy, like you said if we compute the eigenvectors of $H$ nothing ensures that we will get the same $U$, $V$. However if we restrict our eigenvector matrix to be of the form $\begin{pmatrix} X&X\\Y&-Y\end{pmatrix}$ then it should work, if a vector $\begin{pmatrix}x_1\\y_1\end{pmatrix}$ is an eigenvector for $\lambda$, $\begin{pmatrix}x_1\\ -y_1\end{pmatrix}$ is an eigenvector corresponding to $-\lambda$. The matrix is also orthogonal so $X$ and $Y$ are orthogonal.

$\endgroup$
2
  • $\begingroup$ Okay, so I was able to prove that if $Q$ has the form $Q = \begin{pmatrix} X&X\\Y&-Y\end{pmatrix}$, then we necessarily have that $X$ and $Y$ are orthogonal (after scaling by a factor of $\sqrt{2}$), and it follows easily that $A=Y \Sigma X^T$. But what allows for us to ensure that $Q$ has this form in the first place? $\endgroup$
    – A guy
    Commented Jul 27, 2019 at 23:03
  • $\begingroup$ Nevermind. I guess the point of your second sentence is that given $Q = \begin{pmatrix} Q_{11} & Q_{12} \\ Q_{21} & Q_{22} \end{pmatrix}$, we can let $Q'=\begin{pmatrix} Q_{11} & Q_{11} \\ Q_{21} & -Q_{21} \end{pmatrix}$, and then it's not hard to show that $HQ'=Q'D$ and $Q'$ is orthogonal. I'll think this over and accept your answer once I'm confident that this does indeed work. $\endgroup$
    – A guy
    Commented Jul 27, 2019 at 23:27

You must log in to answer this question.

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