How to compute the SVD of a symmetric matrix?

If I have only the upper triangular part of a symmetric matrix $A$, how could I compute the SVD?

$$\begin{pmatrix} 1 & 22 & 13 & 14 \\ & 1 & 45 & 24 \\ & & 1 & 34 \\ & & & 1\end{pmatrix}$$

Does having this upper triangular make the computing easier?

Solution 1:

The SVD for a symmetric matrix $A = U \Sigma V^T$, where $U$ and $V$ are unitary matrices with $U = \left[u_1 | u_2 | \ldots | u_n \right]$, $V = \left[v_1 | v_2 | \ldots | v_n \right]$ and $\Sigma$ is a diagonal matrix with non-negative diagonal entries and $v_i = \pm u_i$

For a symmetric matrix the following decompositions are equivalent to SVD. (Well, almost equivalent if you do not worry about the signs of the vectors).

1. Eigen-value decomposition i.e. $A = X \Lambda X^{-1}$. When $A$ is symmetric, the eigen values are real and the eigenvectors can be chosen to be orthonormal and hence $X^TX = XX^T = I$ i.e. $X^{-1} = X^T$. The only difference is that the singular values are the magnitudes of the eigen values and hence the column of $X$ needs to be multiplied by a negative sign if the eigen value turns out to be negative to get the singular value decomposition. Hence, $U = X$ and $\sigma_i = |\lambda_i|$.

2. Orthogonal decomposition i.e. $A = PDP^T$, where $P$ is a unitary matrix and $D$ is a diagonal matrix. This exists only when matrix $A$ is symmetric and is the same as eigen value decomposition.

3. Schur decomposition i.e. $A = Q S Q^T$, where $Q$ is a unitary matrix and $S$ is an upper triangular matrix. This can be done for any matrix. When $A$ is symmetric, then $S$ is a diagonal matrix and again is the same as the eigen value decomposition and orthogonal decomposition.

I do not remember the cost for each of these operations i.e. I don't remember the coefficients before the leading order $n^3$ term. If my memory is right, the typical algorithm for orthogonal decomposition is slightly cheaper than the other two, though I cannot guarantee.