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.

Related Blog Posts

This article is part of the “What Is” series, available from https://nhigham.com/category/what-is and in PDF form from the GitHub repository https://github.com/higham/what-is.

This entry was posted in what-is. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s