Singular Value Decomposition using Jacobi Method First time user of the site, so I apologize if my question isn't worded properly.
I'm trying to implement the SVD of a square matrix using Algorithm 6 found on this website: http://www.cs.utexas.edu/users/inderjit/public_papers/HLA_SVD.pdf
I'm getting stuck on the step where it says: "Determine $d_1, d_2, c = \cos(\theta)$, and $s = \sin(\varphi)$ such that.."
How exactly would I determine the values of $d_1, d_2, c$ and $s$? I understand that this step seems very similar to the Givens rotation matrix, so can I calculate $d_1, d_2, c$ and $s$ in the same way I would calculate the Givens rotation matrix?
side-note: To calculate the Givens rotation matrix, using left multiplication I would be saying that $d_1 = \sqrt{a^2 + b^2}, c = \frac{a}{d_1}$, and $s = -\frac{b}{d_1}$; Is this correct?
 A: If your problem is just in how to compute the two-sided Givens rotations, see the Wikipedia article on the Jacobi eigenvalue algorithm.
A: Something is wrong in that page 11/algo 6;
first note the matrix with the summations, the subscript indexes (1,2) and (2,1) are wrong, the summation term for both should be $u_{k,i}*u_{k,j}$ (cause it should do a dot product between rows i,j or j,i - and that's the same).
This matrix should be an $2x2$ whose values are taken at $AA^T$, at positions $<i,i>,<i,j>,<j,i>,<j,j>$ consider this latter $2x2$ matrix as
$
M =\begin{bmatrix}
 X &  W\\ 
 W & Y 
\end{bmatrix}
$
Wanted is a rotation matrix $G$, that turns $
 \begin{bmatrix}
 Ai \\
 Aj
\end{bmatrix}
$
the rows Ai e Aj orthogonal, the same as saying
$
 G^T
 \begin{bmatrix}
 Ai \\
 Aj
 \end{bmatrix} ( G \begin{bmatrix}
 Ai \\
 Aj
\end{bmatrix}
)^T
=
G^T
 \begin{bmatrix}
 Ai \\
 Aj
 \end{bmatrix} 
 \begin{bmatrix}
 Ai \\
 Aj
 \end{bmatrix} ^T
 G
 =
G^T M G =
\begin{bmatrix}
 d1 &  0\\ 
 0 & d2 
\end{bmatrix}
$
$X = Ai\cdot Ai, W=Ai\cdot Aj, Y=Aj\cdot Aj$
pick one of the $equations = 0$ in order to solve c, s, ie:
if $(G^TMG)_{2,1}=0$ follows:
$
c(sX+cW)-s(sW+cY) = 0 \Leftrightarrow \\
csX + c^2 W -s^2 W - cs Y  = 0 \Leftrightarrow \\
W(c^2-s^2) + cs(X-Y) = 0 \Leftrightarrow\\
\frac{cs}{c^2-s^2} = -\frac{W}{X-Y}= \frac{W}{Y-X}
$
until now c, s refered to $cos(\theta)$, $sin(\theta)$; by trignometric equivalence:

*

*$sin(\theta)cos(\theta)       = 1/2 sin(2\theta)$

*$cos^2(\theta)-sin^2(\theta)   = cos(2\theta)$
replacing,
$\frac{sin(2\theta)}{2cos(2\theta)}=\frac{W}{Y-X}$ <=>
$tan(2\theta) = \frac{2W}{Y-X}$
So what your algorithm needs is to

*

*compute W,X,Y (1 dot product and 2 self-dot products; you may resuse X, Y they should saved in a vector, and ultimatelly this would be the vector with the singular values once sqrted).

*Compute atan, and divide the angle by 2 to compute cos, sin. But there are shorcuts for computing c,s at the cost of 2 square roots given that you know the height $b={2W}$ and width $a={Y-X}$ of a triangle.
For that, bisect the (double) angle of this triangle in half, and get a new triangle, as instance:

*(the first sqrt) normalize $[a,b]$ and scale it by $a$; $w=a\frac{a,b}{||a,b||}$

*form a second vector from $w$ to $[a,0]$: $w'=[a,0]-w$
and scale $w'$ to half (this vector with origin in $w$, is normal to, and touches the line bisecting the angle in half)

*now the vector $[a-w'(1),w'(2)]$ forms a new triangle
which s,c can be obtained by dividing by its norm (the 2nd sqrt).

*do before a simplification of this vector by cutting
equal scales between components, because the angle
wouldn't change.

