Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

If I have only the upper triangular part of a symmetric matrix A

  • How could I compute SVD, having this upper triangle makes easier the computing?

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

share|improve this question
    
Wikipedia provides you with a couple of links to some tutorials. Click and scroll to the bottom. –  lvb Feb 19 '11 at 20:59
1  
Do you want the svd of a symmetric matrix or svd of an upper triangular matrix? –  user17762 Feb 19 '11 at 21:02
    
@Sivaram Ambikasaran, I´d like SDV of a symmetric matrix, but I have only the upper triangular of the matrix –  cMinor Feb 19 '11 at 21:03
    
if you have the upper half of a symmetric matrix, you can calculate the matrix... –  Yuval Filmus Feb 19 '11 at 21:37
    
LAPACK doesn't contain a special subroutine for computing the SVD of a symmetric matrix, so presumably it's not easier. –  Yuval Filmus Feb 19 '11 at 21:38
add comment

2 Answers

up vote 6 down vote accepted

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.

share|improve this answer
    
Do you know any library to test this great idea?, LAPACK, BLAS? –  cMinor Feb 20 '11 at 0:06
    
@darkcminor: I think yes. Check this out. netlib.org/lapack/double –  user17762 Feb 20 '11 at 0:40
    
One more question @Sivaram Ambikasaran, you say if we don´t worry about the signs, could this be a dangerous problem??, How would look like the output of any of this decompositions of the symmetric matrix?? –  cMinor Feb 20 '11 at 1:12
    
@darkcminor: By not worrying about the signs, I mean, that it is easy to keep track of the signs and change it at the end. Further depending on the problem, you might not need an SVD if you are satisfied with eigenvalue decomposition or orthogonal decomposition or Schur decomposition for the problem at hand. –  user17762 Feb 20 '11 at 1:26
    
If I compute Orthogonal decomposition and get PDP^T, an then U \Sigma V^T. the results are similar or the same?? –  cMinor Feb 20 '11 at 1:26
show 10 more comments

A symmetric matrix always has an eigenvalue decomposition (for which there a specialized routines). I'm not really sure for what application one would need the SVD.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.