% This is a LaTex file.
% Homework for the course "Scientific Computing",
% Spring semester, 1996, Jonathan Goodman.
% A latex format for making homework assignments.
\documentstyle[10pt]{article}
% The page format, somewhat wider and taller page than in art12.sty.
\topmargin -0.1in \headsep 0in \textheight 8.9in \footskip 0.6in
\oddsidemargin 0in \evensidemargin 0in \textwidth 6.5in
\begin{document}
% Definitions of commonly used symbols.
% The title and header.
\noindent
{\scriptsize Scientific Computing, Spring 1996} \hfill
\begin{center}
\large
Assignment 4.
\normalsize
\end{center}
\noindent
Given February 26, due March 4.
\vspace{.3in}
% The questions!
\noindent
{\bf Objective:} To learn about the Singular Value Decomposition.
\vspace{.5cm}
The singular value decomposition (SVD) is a matrix factorization. If $A$
is an $n \times m$ matrix, then we may write $A$ as a product of
three factors:
\begin{equation}
A = U \Sigma V^* \;\; ,
\end{equation}
where $U$ is an orthogonal $n \times n$ matrix, $V$ is an orthogonal
$m \times m$ matrix, $V^*$ is the transpose of $V$, and $\Sigma$
is an $n \times m$ matrix that has all zeros except for its diagonal
entries, which are nonnegative real numbers. If $\sigma_{ij}$ is
the $i,j$ entry of $\Sigma$, then $\sigma_{ij} = 0$ unless $i=j$
and $\sigma_{ii} = \sigma_i \geq 0$. The $\sigma_i$ are the
``singular values'' and the columns of $u$ and $v$ are respectively
the right and left singular vectors. In these exercises, we always
suppose that the singular values have been ordered so that
\begin{displaymath}
\sigma_1 \geq \sigma_2 \geq \cdots \;\; .
\end{displaymath}
This assignment does not ask you to touch a computer.
\begin{description}
\item[(1)]
Show that if the matrix $A$ is square and symmetric then the singular
values of $A$ are the absolute values of the eigenvalues of $A$ and
that the singular vectors are eigenvectors of $A$.
\item[(2)]
Show that $\left\| A \right\|_2$ = $\sigma_1$. If $A$ is square and
$A^{-1}$ exists, then $\left\|A^{-1}\right\|_2 = \sigma_n^{-1}$.
Show that the
condition number of $A$ (for the 2-norm) is $\sigma_1/\sigma_n$.
\item[(3)]
``Regularization'' is a way to compromise between accurate solution of
a least squares problem and the size of the solution. Regularization
is used to improve the conditioning of ill conditioned least squares
problems. The simplest regularization strategy is to replace the
least squares problem
\begin{displaymath}
\min_{x} \left\| Ax - b\right\|_2
\end{displaymath}
with the ``regularized'' problem
\begin{equation}
\min_x \left\| Ax-b\right\|_2^2 + \epsilon \left\| x \right\|_2^2 \;\; .
\end{equation}
Give an algorithm to solve the regularized least squares problem, (2),
using the SVD of $A$. Your algorithm will involve $1/(\sigma_i+\epsilon)$.
Does this make dimensional sense?
\item[(4)]
Use the SVD to show that the non zero eigenvalues of $A^*A$ are identical
to the non zero eigenvalues of $AA^*$. Note that these matrices have
different dimensions so they have a different number of eigenvalues.
\item[(5)]
The ``polar decomposition'' of a square matrix, $A$, is a decomposition
$A=RQ$ where $R$ is symmetric and positive semi-definite and $Q$ is
orthogonal. This is a generalization of the polar decomposition of
a complex number $z = re^{i\theta}$ into a product of a non negative
real number and a complex number of magnitude 1. The polar decomposition
of matrices is used in elasticity theory. Show how to find the polar
decomposition of a matrix from its SVD.
\end{description}
\end{document}