ALAFF Why we love unitary matrices

Skip to main content

\usepackagearray\setlength\oddsidemargin−0.0in\setlength\evensidemargin−0.0in\setlength\textheight8.75in\setlength\textwidth6.5in\setlength\topmargin−0.25in

$\usepackage{array} \setlength{\oddsidemargin}{-0.0in} \setlength{\evensidemargin}{-0.0in} \setlength{\textheight}{8.75in} \setlength{\textwidth}{6.5in} \setlength{\topmargin}{-0.25in} \newcommand{\R}{\mathbb R} \newcommand{\Rm}{\mathbb R^m} \newcommand{\Rn}{\mathbb R^n} \newcommand{\Rnxn}{\mathbb R^{n \times n}} \newcommand{\Rmxn}{\mathbb R^{m \times n}} \newcommand{\Rmxm}{\mathbb R^{m \times m}} \newcommand{\Rmxk}{\mathbb R^{m \times k}} \newcommand{\Rkxn}{\mathbb R^{k \times n}} \newcommand{\C}{\mathbb C} \newcommand{\Cm}{\mathbb C^m} \newcommand{\Cmxm}{\mathbb C^{m \times m}} \newcommand{\Cnxn}{\mathbb C^{n \times n}} \newcommand{\Cmxn}{\mathbb C^{m \times n}} \newcommand{\Ckxk}{\mathbb C^{k \times k}} \newcommand{\Cn}{\mathbb C^n} \newcommand{\Ck}{\mathbb C^k} \newcommand{\Null}{{\cal N}} \newcommand{\Col}{{\cal C}} \newcommand{\Rowspace}{{\cal R}} \newcommand{\Span}{{\rm {Span}}} \newcommand{\rank}{{\rm rank}} \newcommand{\triu}{{\rm triu}} \newcommand{\tril}{{\rm tril}} \newcommand{\sign}{{\rm sign}} \newcommand{\FlaTwoByTwo}[4]{ \left( \begin{array}{c | c} #1 \amp #2 \\ \hline #3 \amp #4 \end{array} \right) } \newcommand{\FlaTwoByTwoSingleLine}[4]{ \left( \begin{array}{c c} #1 \amp #2 \\ #3 \amp #4 \end{array} \right) } \newcommand{\FlaTwoByTwoSingleLineNoPar}[4]{ \begin{array}{c c} #1 \amp #2 \\ #3 \amp #4 \end{array} } \newcommand{\FlaOneByTwo}[2]{ \left( \begin{array}{c | c} #1 \amp #2 \end{array} \right) } \newcommand{\FlaOneByTwoSingleLine}[2]{ \left( \begin{array}{c c} #1 \amp #2 \end{array} \right) } \newcommand{\FlaTwoByOne}[2]{ \left( \begin{array}{c} #1 \\ \hline #2 \end{array} \right) } \newcommand{\FlaTwoByOneSingleLine}[2]{ \left( \begin{array}{c} #1 \\ #2 \end{array} \right) } \newcommand{\FlaThreeByOneB}[3]{ \left( \begin{array}{c} #1 \\ \hline #2 \\ #3 \end{array} \right) } \newcommand{\FlaThreeByOneT}[3]{ \left( \begin{array}{c} #1 \\ #2 \\ \hline #3 \end{array} \right) } \newcommand{\FlaOneByThreeR}[3]{ \left( \begin{array}{c | c c} #1 \amp #2 \amp #3 \end{array} \right) } \newcommand{\FlaOneByThreeL}[3]{ \left( \begin{array}{c c | c} #1 \amp #2 \amp #3 \end{array} \right) } \newcommand{\FlaThreeByThreeBR}[9]{ \left( \begin{array}{c | c c} #1 \amp #2 \amp #3 \\ \hline #4 \amp #5 \amp #6 \\ #7 \amp #8 \amp #9 \end{array} \right) } \newcommand{\FlaThreeByThreeTL}[9]{ \left( \begin{array}{c c | c} #1 \amp #2 \amp #3 \\ #4 \amp #5 \amp #6 \\ \hline #7 \amp #8 \amp #9 \end{array} \right) } \newcommand{\diag}[1]{{\rm diag}( #1 )} \newcommand{\URt}{{\sc HQR}} \newcommand{\FlaAlgorithm}{ \begin{array}{|l|} \hline \routinename \\ \hline \partitionings \\ ~~~ \begin{array}{l} \partitionsizes \end{array} \\ {\bf \color{blue} {while}~} \guard \\ ~~~ \begin{array}{l} \repartitionings \end{array} \\ ~~~ \color{red} { \begin{array}{l} \hline \color{black} {\update} \\ \hline \end{array}} \\ ~~~ \begin{array}{l} \moveboundaries \end{array} \\ {\bf \color{blue} {endwhile}} \\ \hline \end{array} } \newcommand{\FlaAlgorithmWithInit}{ \begin{array}{|l|} \hline \routinename \\ \hline \initialize \\ \partitionings \\ ~~~ \begin{array}{l} \partitionsizes \end{array} \\ {\bf \color{blue} {while}~} \guard \\ ~~~ \begin{array}{l} \repartitionings \end{array} \\ ~~~ \color{red} { \begin{array}{l} \hline \color{black} {\update} \\ \hline \end{array}} \\ ~~~ \begin{array}{l} \moveboundaries \end{array} \\ {\bf \color{blue} {endwhile}} \\ \hline \end{array} } \newcommand{\FlaBlkAlgorithm}{ \begin{array}{|l|} \hline \routinename \\ \hline \partitionings \\ ~~~ \begin{array}{l} \partitionsizes \end{array} \\ {\bf \color{blue} {while}~} \guard \\ ~~~ {\bf choose~block~size~} \blocksize \\ ~~~ \begin{array}{l} \repartitionings \end{array} \\ ~~~ ~~~ \repartitionsizes \\ ~~~ \color{red} { \begin{array}{l} \hline \color{black} {\update} \\ \hline \end{array}} \\ ~~~ \begin{array}{l} \moveboundaries \end{array} \\ {\bf \color{blue} {endwhile}} \\ \hline \end{array} } \newcommand{\complexone}{ \begin{array}{|c|}\hline \!\pm\! \\ \hline \end{array}~ } \newcommand{\HQR}{{\rm HQR}} \newcommand{\QR}{{\rm QR}} \newcommand{\st}{{\rm \ s.t. }} \newcommand{\QRQ}{{\rm {\normalsize \bf Q}{\rm \tiny R}}} \newcommand{\QRR}{{\rm {\rm \tiny Q}{\bf \normalsize R}}} \newcommand{\deltaalpha}{\delta\!\alpha} \newcommand{\deltax}{\delta\!x} \newcommand{\deltay}{\delta\!y} \newcommand{\deltaz}{\delta\!z} \newcommand{\deltaw}{\delta\!w} \newcommand{\DeltaA}{\delta\!\!A} \newcommand{\meps}{\epsilon_{\rm mach}} \newcommand{\fl}[1]{{\rm fl( #1 )}} \newcommand{\becomes}{:=} \newcommand{\defrowvector}[2]{ \left(#1_0, #1_1, \ldots, #1_{#2-1}\right) } \newcommand{\tr}[1]{{#1}^T} \newcommand{\LUpiv}[1]{{\rm LU}(#1)} \newcommand{\maxi}{{\rm maxi}} \newcommand{\Chol}[1]{{\rm Chol}( #1 )} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&}$

Subsection 2.2.7 Why we love unitary matrices

fit width

In Subsection 1.4.1, we looked at how sensitive solving

A x = b

$\begin{equation*} A x = b \end{equation*}$

is to a change in the right-hand side

A (x + δ x) = b + δ b

$\begin{equation*} A ( x + \delta\!x) = b + \delta\!b \end{equation*}$

when

A

$A$ is nonsingular. We concluded that

$\begin{equation*} \frac{\| \delta\!x \|}{\| x \|}\leq \begin{array}[t]{c} \underbrace{\| A \| \| A^{-1} \|} \\ \kappa( A ) \end{array} \frac{\| \delta\!b \|}{\| b \|}, \end{equation*}$

when an induced matrix norm is used. Let's look instead at how sensitive matrix-vector multiplication is.

Homework 2.2.7.1.

Let $A \in \Cnxn$ be nonsingular and $x \in \Cn$ a nonzero vector. Consider

$\begin{equation*} y = A x \quad \mbox{and} \quad y + \delta\!y = A ( x + \delta\!x ). \end{equation*}$

Show that

$\begin{equation*} \frac{\| \delta\!y \|}{\| y \|}\leq \begin{array}[t]{c} \underbrace{\| A \| \| A^{-1} \|} \\ \kappa( A ) \end{array} \frac{\| \delta\!x \|}{\| x \|}, \end{equation*}$

where $\| \cdot \|$ is an induced matrix norm.

Since \(x = A^{-1} y \) we know that

\begin{equation*} \| x \| \leq \| A^{-1} \| \| y \| \end{equation*}

and hence

\begin{equation} \frac{1}{\| y \|} \leq \| A^{-1} \| \frac{1}{\| x \|}.\label{chapter03-launch-1}\tag{2.2.1} \end{equation}

Subtracting \(y = A x \) from \(y + \delta\!y = A ( x + \delta\!x ) \) yields

\begin{equation*} \delta\!y = A \delta\!x \end{equation*}

and hence

\begin{equation} \| \delta\!y \| \leq \| A \| \| \delta\!x \|.\label{chapter03-launch-2}\tag{2.2.2} \end{equation}

Combining (2.2.1) and (2.2.2) yields the desired result.

There are choices of

$x$ and

$\delta\!x$ for which the bound is tight.

What does this mean? It means that if as part of an algorithm we use matrix-vector or matrix-matrix multiplication, we risk amplifying relative error by the condition number of the matrix by which we multiply. Now, we saw in Section 1.4 that

$1 \leq \kappa( A ) \text{.}$ So, if there are algorithms that only use matrices for which

$\kappa(A) = 1 \text{,}$ then those algorithms don't amplify relative error.

Remark 2.2.7.1.

We conclude that unitary matrices, which do not amplify the 2-norm of a vector or matrix, should be our tool of choice, whenever practical.