\documentclass[11pt]{article}
\usepackage{epsfig}
\usepackage{graphicx}
\usepackage{color}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{xypic}
\usepackage{nicematrix}
\usepackage{subcaption}
\usepackage{listings}
\lstset{language=Matlab}
\usepackage{enumitem}

\setlength{\textwidth}{6.5in}
\setlength{\topmargin}{0in}
\setlength{\headsep}{0in}
\setlength{\headheight}{0in}
\setlength{\oddsidemargin}{0in}
\setlength{\textheight}{9in}

\newcommand{\todo}[1]{\textcolor{red}{[#1]}}

\input xy
\xyoption{all}

%% Norm command
\newcommand{\norm}[1]{\left\lVert#1\right\rVert}

%Used to display the marks available in the left margin.
\newcommand{\rmp}{\reversemarginpar\marginpar}

\pagestyle{empty}

\providecommand{\SolutionSVDByHandPartA}{}
\providecommand{\SolutionSVDByHandPartB}{}
\providecommand{\SolutionSVDByHandPartC}{}
\providecommand{\SolutionSVDByHandPartD}{}
\providecommand{\SolutionSVDByHandPartE}{}
\providecommand{\SolutionUsingSVDPartA}{}
\providecommand{\SolutionUsingSVDPartB}{}
\providecommand{\SolutionEigenDecomposition}{}
\providecommand{\SolutionSVDComputationPartA}{}
\providecommand{\SolutionSVDComputationPartB}{}
\providecommand{\SolutionImageCompressionModifiedPartA}{}
\providecommand{\SolutionImageCompressionModifiedPartB}{}
\providecommand{\SolutionConvergenceViaEigenvaluesPartA}{}
\providecommand{\SolutionConvergenceViaEigenvaluesPartB}{}
\providecommand{\SolutionConvergenceViaEigenvaluesPartC}{}
\providecommand{\SolutionConvergenceViaEigenvaluesPartD}{}

\newtheorem{DefinitionPlaceHolder}{Definition}
\newtheorem{TheoremConvergence}[DefinitionPlaceHolder]{Theorem}

\begin{document}

\begin{center}
{\Large {\bf CS 475/675 Spring 2025: Crowdmark Assignment 6}}\\
\end{center}

\noindent
{\bf Due July 30 at 11:59 pm Eastern.} \\
Submit all components of your solutions (written/analytical work, code/scripts, figures,
plots, output, etc.) to CrowdMark in PDF form in the section for each question.\\

\noindent You must also separately submit a single zip file containing any and all code/scripts you
write to the A06 DropBox on LEARN, in runnable format (that is, .m).\\

\noindent \textbf{For full marks, be sure to show all your work!}

\begin{enumerate}

\item \label{QuestionSVDByHand}
Determine reduced SVDs of the following matrices (by hand, not on Matlab) using whatever method you prefer.
Show your work to justify your answers.
\begin{enumerate}
\item \rmp{[2]} $\begin{bmatrix} 3 & 0 \\ 0 & 2 \end{bmatrix}$
\SolutionSVDByHandPartA

\newpage

\item \rmp{[2]} $\begin{bmatrix} 4 & 0 \\ 0 & -1 \end{bmatrix}$
\SolutionSVDByHandPartB

\newpage

\item \rmp{[2]} $\begin{bmatrix} 0 & 3 \\ 0 & 0 \\ 0 & 0 \end{bmatrix}$
\SolutionSVDByHandPartC

\newpage

\item \rmp{[2]} $\begin{bmatrix} 1 & 1 \\ 0 & 0 \end{bmatrix}$
\SolutionSVDByHandPartD

\newpage

\item \rmp{[2]} $\begin{bmatrix} 2 & 2 \\ 2 & 2 \end{bmatrix}$
\SolutionSVDByHandPartE

\end{enumerate}

\newpage

\item \label{QuestionUsingSVD}
Let $A$ be a full rank $m \times n$ matrix (where $m \geq n$).
Suppose you are provided with an SVD of $A$, i.e. suppose that you can write $A = U \Sigma V^{T}$.
Note, as usual, throughout this question we prefer not to compute $A^{-1}$ or $(A^TA)^{-1}$ explicitly!
Describe how to use the $U$, $\Sigma$, $V$ factors to:

\begin{enumerate}
\item \rmp{[5]}
Solve the linear system $Ax=b$, where $m=n$.
\SolutionUsingSVDPartA

\newpage

\item \rmp{[5]}
Solve the least squares problem $Ax=b$, where $m>n$.
\SolutionUsingSVDPartB
\end{enumerate}

\newpage

\item \rmp{[10]} \label{QuestionEigenDecomposition}
Let $A$ be a full rank $m \times n$ matrix (where $m \geq n$).
Consider
\begin{eqnarray*}
H = \begin{bmatrix}
0 & A^T \\
A & 0
\end{bmatrix}.
\end{eqnarray*}
Determine an eigenvalue decomposition of $H$, i.e., find $Q$ such that $HQ=Q\Lambda$, where $\Lambda$ is a diagonal matrix.
How are $Q$ and $\Lambda$ related to the singular vectors and singular values of $A$?
Explain.
(Hint: Consider
\begin{displaymath}
Q = \frac{1}{\sqrt{2}}
\begin{bmatrix}
V       & V        & 0                \\
\hat{U} & -\hat{U} & \sqrt{2} \hat{U}_{m-n}
\end{bmatrix},
\end{displaymath}
where an SVD of $A$ is given by $A = U \Sigma V^T$, and $U = \begin{bmatrix} \hat{U} & \hat{U}_{m-n} \end{bmatrix}$.)
\SolutionEigenDecomposition

\newpage

\item \label{QuestionSVDComputation}
Let $A$ be a full rank $m \times n$ matrix (where $m \geq n$).
Let $w$ be an $n \times 1$ column vector.
Define
\begin{displaymath}
B =
\begin{bmatrix}
A \\ w^T
\end{bmatrix}.
\end{displaymath}

\begin{enumerate}
\item \rmp{[4]}
Show that $\sigma_1(B) \leq \sqrt{\norm{A}_2^2 + \norm{w}_2^2}$.
(Hint: Use the definition $\norm{B}_2 = \max_{\norm{x}_2=1} \norm{Bx}_2$.)
\SolutionSVDComputationPartA

\newpage

\item \rmp{[6]}
Show that $\sigma_n(B) \geq \sigma_n(A)$.
(Hint: Let  $\tilde{B} = \begin{bmatrix} \tilde{A} \\ \tilde{w}^T \end{bmatrix}$ be the best rank $n-1$ approximation of $B$, where $\tilde{A}$ is $m \times n$ and $\tilde{w}$ is $n \times 1$.
Let $\hat{A}$ be the best rank $n-1$ approximation of $A$.
Form $B-\tilde{B}$ and again make use of the definition of the  matrix 2-norm.)
\SolutionSVDComputationPartB
\end{enumerate}

\newpage

\item \label{QuestionImageCompressionModified}
In this question, you will modify the optimal SVD image compression technique which we studied in class, to confirm visually that other choices of which singular values to retain are worse than the optimal choice.
Your input in both parts will be the provided \lstinline!baboon.png! image file.
Work in grayscale throughout.
Retain only the 256 singular values that are specified in each part of the question.
Submit your code, plus a copy of the compressed image that your code produces.

\begin{enumerate}
\item \rmp{[5]}
Develop a Matlab script, \lstinline!SVDGrayscaleImageCompressionLast.m!, to output the compressed image which retains only the \textbf{last} 256 singular values.
\SolutionImageCompressionModifiedPartA

\newpage

\item \rmp{[5]}
Develop a Matlab script, \lstinline!SVDGrayscaleImageCompressionOdd.m!, to output the compressed image which retains only the \textbf{odd-index} singular values.
\SolutionImageCompressionModifiedPartB
\end{enumerate}

\newpage

\item \label{QuestionConvergenceViaEigenvalues}
Recall
\begin{TheoremConvergence} \label{TheoremConvergence}
The iterative method $x^{(k+1)} = x^{(k)} + M^{-1}(b - Ax^{(k)})$ converges for any $x^{(0)}$ and any $b$ if and only if $\rho(I-M^{-1}A) < 1$, where $\rho$ denotes the \textbf{spectral radius}.
\end{TheoremConvergence}

Let
\begin{eqnarray*}
A & = & \begin{bmatrix} 3 & 1 \\ 1 & 5 \end{bmatrix} \textrm{, and} \\
B & = & \begin{bmatrix} 2 & 1 \\ 1 & \frac{1}{4} \end{bmatrix} .
\end{eqnarray*}
Note that, on the mid-term exam, you used Theorem \ref{TheoremConvergence} to proved that Jacobi iteration, with matrix $A$, converges.

\begin{enumerate}
\item \rmp{[6]}
Apply Theorem \ref{TheoremConvergence} to prove that both of Gauss-Seidel (GS) and Successive Over-Relaxation (SOR) with $\omega=\frac{1}{2}$ iterations will converge with matrix $A$.
Do this proof by hand, not using Matlab.
\SolutionConvergenceViaEigenvaluesPartA

\newpage

\item \rmp{[9]}
Apply Theorem \ref{TheoremConvergence} to prove that all of Jacobi, Gauss-Seidel (GS) and Successive Over-Relaxation (SOR) with $\omega=\frac{1}{2}$ iterations will diverge with matrix $B$.
Do this proof by hand, not using Matlab.
\SolutionConvergenceViaEigenvaluesPartB

\newpage

\item \rmp{[15]}
Develop Matlab functions, \lstinline!JacobiConverges.m!, \lstinline!GSConverges.m! and \lstinline!SORConverges.m! to use the criterion provided by Theorem \ref{TheoremConvergence} to indicate (by returning 1 for \lstinline!true! or 0 for \lstinline!false!) whether the respective iteration will or will not converge for the given parameter matrix (or parameter matrix plus additional parameter $\omega$ in the case of SOR).
You may use the built-in Matlab function \lstinline!eigs! to extract the needed eigenvalue(s).

Submit all of your code, plus a diary for each function, witnessing that your function indicates that matrix $A$ (plus parameter $\omega=\frac{1}{2}$ in the case of SOR) makes all three iterative methods converge, and that matrix $B$ (plus parameter $\omega=\frac{1}{2}$ in the case of SOR) makes all three iterative methods diverge.
You may find it helpful to start from the provided \lstinline!JacobiConvergesTemplate.m!, \lstinline!GSConvergesTemplate.m! and \lstinline!SORConvergesTemplate.m! files.

\end{enumerate}

\end{enumerate}

\end{document}