What Is the CS Decomposition?

The CS (cosine-sine) decomposition reveals close relationships between the singular value decompositions (SVDs) of the blocks an orthogonal matrix expressed in block $2\times 2$ form. In full generality, it applies when the diagonal blocks are not necessarily square. We focus here mainly on the most practically important case of square diagonal blocks.

Let $Q\in\mathbb{R}^{n \times n}$ be orthogonal and suppose that $n = 2p$ is even and $Q$ is partitioned into four equally sized blocks:

$\notag Q = \begin{array}[b]{@{\mskip35mu}c@{\mskip-20mu}c@{\mskip-10mu}c@{}} \scriptstyle p & \scriptstyle p & \\ \multicolumn{2}{c}{ \left[\begin{array}{c@{~}c@{~}} Q_{11}& Q_{12} \\ Q_{21}& Q_{22} \\ \end{array}\right]} & \mskip-12mu\ \begin{array}{c} \scriptstyle p \\ \scriptstyle p \end{array} \end{array}.$

Then there exist orthogonal matrices $U_1,U_2,V_1,V_2\in\mathbb{R}^{p \times p}$ such that

$\notag \begin{bmatrix} U_1^T & 0\\ 0 & U_2^T \end{bmatrix} \begin{bmatrix} Q_{11} & Q_{12}\\ Q_{21} & Q_{22} \end{bmatrix} \begin{bmatrix} V_1 & 0\\ 0 & V_2 \end{bmatrix} = \begin{array}[b]{@{\mskip36mu}c@{\mskip-13mu}c@{\mskip-10mu}c@{}} \scriptstyle p & \scriptstyle p & \\ \multicolumn{2}{c}{ \left[\begin{array}{@{\mskip3mu}rr@{~}} C & S \\ -S & C \end{array}\right]} & \mskip-12mu\ \begin{array}{c} \scriptstyle p \\ \scriptstyle p \end{array} \end{array},$

where $C = \mathrm{diag}(c_i)$ and $S = \mathrm{diag}(s_i)$ with $c_i \ge 0$ , $s_i \ge 0$ , and $c_i^2 + s_i^2 = 1$ for all $i$ . This CS decomposition comprises four SVDs:

$\notag \begin{alignedat}{2} Q_{11} &= U_1CV_1^T, &\quad Q_{12} &= U_1 S V_2^T, \\ Q_{21} &= U_2 (-S) V_1^T, &\quad Q_{22} &= U_2C V_2^T. \end{alignedat}$

(Strictly speaking, for $Q_{21}$ we need to move the minus sign from $S$ to $U_2$ or $V_1$ to obtain an SVD.) The orthogonality ensures that there are only four different singular vector matrices instead of eight, and it makes the singular values of the blocks closely linked. We also obtain SVDs of four cross products of the blocks: $Q_{11}^TQ_{12} = V_1^T CS V_2^T$ , etc.

Note that for $p = 1$ , the CS decomposition reduces to the fact that any $2\times 2$ orthogonal matrix is of the form $\left[\begin{smallmatrix} c & s \\ -s & c \end{smallmatrix}\right]$ (a rotation ) up to multiplication of a row or column by $-1$ .

A consequence of the decomposition is that $Q_{11}$ and $Q_{22}$ have the same 2-norms and Frobenius norms, as do their inverses if they are nonsingular. The same is true for $Q_{12}$ and $Q_{21}$ .

Now we drop the requirement that $n$ is even and consider diagonal blocks of different sizes:

$\notag Q = \begin{array}[b]{@{\mskip33mu}c@{\mskip-16mu}c@{\mskip-10mu}c@{}} \scriptstyle p & \scriptstyle n-p & \\ \multicolumn{2}{c}{ \left[\begin{array}{c@{~}c@{~}} Q_{11}& Q_{12} \\ Q_{21}& Q_{22} \\ \end{array}\right]} & \mskip-12mu\ \begin{array}{c} \scriptstyle p \\ \scriptstyle n-p \end{array} \end{array}, \quad p \le \displaystyle\frac{n}{2}.$

The CS decomposition now has the form

$\notag \begin{bmatrix} U_1^T & 0\\ 0 & U_2^T \end{bmatrix} \begin{bmatrix} Q_{11} & Q_{12}\\ Q_{21} & Q_{22} \end{bmatrix} \begin{bmatrix} V_1 & 0\\ 0 & V_2 \end{bmatrix} = \begin{array}[b]{@{\mskip35mu}c@{\mskip30mu}c@{\mskip-10mu}c@{}c} \scriptstyle p & \scriptstyle p & \scriptstyle n-2p & \\ \multicolumn{3}{c}{ \left[\begin{array}{c@{~}|c@{~}c} C & S & 0 \\ \hline -S & C & 0 \\ 0 & 0 & I_{n-2p} \end{array}\right]} & \mskip-12mu \begin{array}{c} \scriptstyle p \\ \scriptstyle p \\ \scriptstyle n-2p \end{array} \end{array},$

with $U_1$ , $U_2$ , $C$ , and $S$ , and $V_1$ and $V_2$ (both now $(n-p) \times )n-p)$ ), having the same properties as before. The new feature for $p < n/2$ is the identity matrix in the bottom right-hand corner on the right-hand side. Here is an example with $p = 2$ and $n=5$ , with elements shown to two decimal places:

$\notag \begin{aligned} \left[\begin{array}{rr|rrr} 0.71 & -0.71 & 0 & 0 & 0 \\ -0.71 & -0.71 & 0 & 0 & 0 \\\hline 0 & 0 & 0.17 & 0.61 & -0.78 \\ 0 & 0 & -0.58 & -0.58 & -0.58 \\ 0 & 0 & -0.80 & 0.54 & 0.25 \\ \end{array}\right] \left[\begin{array}{rr|rrr} -0.60 & -0.40 & -0.40 & -0.40 & -0.40 \\ 0.40 & 0.60 & -0.40 & -0.40 & -0.40 \\\hline 0.40 & -0.40 & 0.60 & -0.40 & -0.40 \\ 0.40 & -0.40 & -0.40 & 0.60 & -0.40 \\ 0.40 & -0.40 & -0.40 & -0.40 & 0.60 \\ \end{array}\right] \\ \times \left[\begin{array}{rr|rrr} -0.71 & 0.71 & 0 & 0 & 0 \\ -0.71 & -0.71 & 0 & 0 & 0 \\\hline 0 & 0 & 0.17 & 0.58 & -0.80 \\ 0 & 0 & 0.61 & 0.58 & 0.54 \\ 0 & 0 & -0.78 & 0.58 & 0.25 \\ \end{array}\right] = \left[\begin{array}{rr|rrr} 1.00 & 0 & 0 & 0 & 0 \\ 0 & 0.20 & 0 & 0.98 & 0 \\\hline 0 & 0 & 1.00 & 0 & 0 \\ 0 & -0.98 & 0 & 0.20 & 0 \\ 0 & 0 & 0 & 0 & 1.00 \\ \end{array}\right]. \end{aligned}$

We mention two interesting consequences of the CS decomposition.

With $p=1$ : if $q_{11} = 0$ then $Q_{22}$ is singular.
For unequally sized diagonal blocks it is no longer always true that $Q_{11}$ and $Q_{22}$ have the same norms, but their inverses do: $\|Q_{11}^{-1}\|_2 = \|Q_{22}^{-1}\|_2 = 1/\min_ic_i \ge 1$ . When $p = 1$ , this relation becomes $\|Q_{22}^{-1}\|_2 = 1/|q_{11}|$ .

The CS decomposition also exists for a rectangular matrix with orthonormal columns,

$\notag Q = \begin{array}[b]{@{\mskip-25mu}c@{\mskip-20mu}c@{}} \scriptstyle n \\ \multicolumn{1}{c}{ \left[\begin{array}{@{}c@{}} Q_{1}\\ Q_{2} \end{array}\right]} & \mskip-12mu\ \begin{array}{c} \scriptstyle p \\ \scriptstyle q \end{array} \end{array}, \quad p\ge n, \quad q \ge n.$

Now the decomposition takes the form

$\notag \begin{bmatrix} U_1^T & 0\\ 0 & U_2^T \end{bmatrix} \begin{bmatrix} Q_{1}\\ Q_{2} \end{bmatrix} V = \begin{array}[b]{@{\mskip-25mu}c@{\mskip-20mu}c@{}} \scriptstyle n \\ \multicolumn{1}{c}{ \left[\begin{array}{c@{~}} C\\ S \end{array}\right]} & \mskip-12mu\ \begin{array}{c} \scriptstyle p \\ \scriptstyle q \end{array} \end{array},$

where $U_1\in\mathbb{R}^{p\times p}$ , $U_2\in\mathbb{R}^{q\times q}$ , and $V\in\mathbb{R}^{n\times n}$ are orthogonal and $C$ and $S$ have the same form as before except that they are rectangular.

The most general form of the CS decomposition is for an orthogonal matrix with diagonal blocks that are not square. Now the matrix on the right-hand side has a more complicated block structure (see the references for details).

The CS decomposition arises in measuring angles and distances between subspaces. These are defined in terms of the orthogonal projectors onto the subspaces, so singular values of orthonormal matrices naturally arise.

Software for computing the CS decomposition is available in LAPACK, based on an algorithm of Sutton (2009). We used a MATLAB interface to it, available on MathWorks File Exchange, for the numerical example. Note that the output of this code is not quite in the form in which we have presented the decomposition, so some post-processing is required to achieve it.

References

This is a minimal set of references, which contain further useful references within.

Gene Golub and Charles F. Van Loan, Matrix Computations, fourth edition, Johns Hopkins University Press, Baltimore, MD, USA, 2013.
C. C. Paige and M. Wei, History and Generality of the CS Decomposition, Linear Algebra Appl. 208/209, 303–326, 1994.
Brian Sutton, Computing the Complete CS Decomposition, Numer. Algorithms 50(1), 33–65, 2009.

What Is the CS Decomposition?

References

Related Blog Posts

Leave a Reply Cancel reply

References

Related Blog Posts

Share this:

Related

Leave a Reply Cancel reply