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

\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}

\providecommand{\SolutionUnnormalizedLaplacianPartA}{}
\providecommand{\SolutionUnnormalizedLaplacianPartB}{}
\providecommand{\SolutionUnnormalizedLaplacianPartC}{}
\providecommand{\SolutionUnnormalizedLaplacianPartD}{}
\providecommand{\SolutionEigenvectorsMatlabPartA}{}
\providecommand{\SolutionEigenvectorsMatlabPartB}{}
\providecommand{\SolutionImageDegmentationMatlabPartA}{}
\providecommand{\SolutionImageDegmentationMatlabPartB}{}

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

\pagestyle{empty}

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

\noindent
{\bf Due July 18 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 A05 DropBox on LEARN, in runnable format (that is, .m).\\

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

\begin{enumerate}%{$\bullet$}{\leftmargin 0.5cm}

\item
In this question you will prove a Theorem which is stated, but not proved, in the Lecture Notes for Lecture 17.
Let $n \geq 1$ be an arbitrary positive integer.
Let $\hat{L}$ be an arbitrary normalized graph Laplacian matrix, of size $n \times n$.
The rest of the notation in this question is as it is in the Lecture Notes.
\begin{enumerate}
\item
For \rmp{[6]}any vector $x = \begin{bmatrix} x_{1} \cdots x_{n} \end{bmatrix}^{T} \in \mathbb{R}^{n}$, prove that
\begin{displaymath}
x^{T} \hat{L} x = \frac{1}{2} \sum \limits_{i,j=1}^{n} w_{ij} \left ( \frac{x_{i}}{\sqrt{d_{i}}}-\frac{x_{j}}{\sqrt{d_{j}}} \right )^{2}.
\end{displaymath}
\SolutionUnnormalizedLaplacianPartA

\newpage

\item
Prove \rmp{[4]}that $\hat{L}$ is symmetric and positive \textbf{semi}-definite.
\SolutionUnnormalizedLaplacianPartB

\newpage

\item
Prove \rmp{[4]}that $\hat{L}$ has $n$ non-negative eigenvalues $0 \leq \lambda_{1} \leq \lambda_{2} \leq \lambda_{3} \leq \cdots \leq \lambda_{n}$.
\SolutionUnnormalizedLaplacianPartC

\newpage

\item
Prove \rmp{[4]}that the smallest eigenvalue of $\hat{L}$ is 0 and the corresponding eigenvector is $D^{\frac{1}{2}} \textbf{1}$.
\SolutionUnnormalizedLaplacianPartD

\end{enumerate}

\newpage

\item
This question is about computing eigenvalues and eigenvectors.

\noindent
Consider the $n \times n$ tridiagonal matrix:
\begin{displaymath}
A =
\begin{bmatrix}
2  &   -1   &        &    \\
-1 &    2   & \ddots &    \\
   & \ddots & \ddots & -1 \\
   &        &   -1   &  2 \\
\end{bmatrix} .
\end{displaymath}
Let $v^{(k)}$ be the $k$-th eigenvector of $A$ and $\lambda^{(k)}$ the corresponding eigenvalue.
Then they are given by:
\begin{displaymath}
v_j^{(k)} = \sin \left( \frac{kj \pi}{n+1} \right)
\hspace{1cm} \mbox{and} \hspace{1cm}
\lambda^{(k)} = 4 \sin^2 \left( \frac{k \pi}{2(n+1)} \right),
\end{displaymath}
where $v_j^{(k)}$ is the $j$-th component of $v^{(k)}$.
Note: $\lambda^{(1)} < \lambda^{(2)} < \cdots < \lambda^{(n)}$.

\begin{enumerate}%{$\bullet$}{\leftmargin 0.7cm}

\item
Implement \rmp{[15]}the following numerical methods: power iteration, Rayleigh quotient iteration,
and QR iteration (without shifts).
Create the following Matlab functions:
\begin{verbatim}
      [v,lambda,iter] = PowerIteration(A,v0,maxiter,tol)
      [v,lambda,iter] = RayleighQuotient(A,v0,maxiter,tol)
      [V,Lambda,iter] = QRIteration(A,maxiter,tol)
\end{verbatim}
The first two Matlab functions take as inputs the matrix $A$, the initial vector $v0$, the maximum number of iterations $maxiter$ and the tolerance
$tol$, and compute the approximate eigenvector $v$, approximate eigenvalue $lambda$, and the number of iterations to convergence, $iter$.
The third Matlab function computes all the eigenvectors and eigenvalues of $A$, using \textbf{simultaneous iteration}.
The approximate eigenvectors are stored in matrix $V$ and eigenvalues are stored in vector $Lambda$.

For \lstinline!RayleighQuotient!, you can use Matlab backslash `$\backslash$' to solve linear systems.
For \lstinline!QRIteration!, use Matlab's built-in function \lstinline!qr! to compute the required QR factorizations.

For all these methods, the stopping criterion is:
\begin{displaymath}
\|A \tilde{v} - \tilde{\lambda} \tilde{v} \|_2 < tol,
\end{displaymath}
where $\tilde{v}$ and $\tilde{\lambda}$ are the approximate eigenvector and eigenvalue, respectively.
For \lstinline!QRIteration!, stop when this criterion is satisfied by \textbf{all} of the individual eigenvalue/eigenvector pairs.
Submit all of your code.
\SolutionEigenvectorsMatlabPartA

\newpage

\item
Next, \rmp{[15]}you will compute some eigenvectors and eigenvalues of $A$ using the above methods for the case $n=100$.
Set the maximum iteration number, $maxiter=10000$, and the tolerance, $tol=10^{-4}$.
Create a Matlab program, \lstinline!EigenMethods.m!, which performs the following:
\begin{enumerate}%[label=(\roman*)]%{$\bullet$}{\leftmargin 0.7cm}
\item
Use \lstinline!PowerIteration! to compute the largest eigenvalue of $A$ and its associated eigenvector.
Use $v0 = [1, 0, \ldots , 0]^{T}$ for the initial vector.
\item
Use \lstinline!RayleighQuotient! to compute an eigenvector and eigenvalue of $A$.
The initial vector $v0 = [1, 1, \ldots , 1]^T$.
\item
Use \lstinline!QRIteration! to compute all eigenvectors and eigenvalues of $A$.
\end{enumerate}
For \lstinline!PowerIteration!, make a plot of the computed eigenvector.
Display the value of the computed eigenvalue and the number of iterations on the title of the plot.
Do the same for \lstinline!RayleighQuotient!.
For \lstinline!QRIteration!, use its output to make a plot of all eigenvalues, titled ``Eigenvalues of A''.
Also, create separate plots of the column vectors $v^{(20)}$, $v^{(40)}$, $v^{(60)}$, $v^{(80)}$ of $V$.
Title these plots with the corresponding eigenvalue, its index, and number of
iterations \lstinline!QRIteration! used. 

\textbf{Be careful: Our eigenvalue/vector numbering convention above has the eigenvalues in ascending
order, so make sure your plots are consistent with that ordering.}
You may find the Matlab commands \lstinline!fliplr!/\lstinline!flipud! useful.
Submit all of your code and plots.
\SolutionEigenvectorsMatlabPartB
\end{enumerate}

\newpage

\item
This question is about spectral clustering image segmentation.
\begin{enumerate}
\item
Create \rmp{[15]}the Matlab function:
\begin{verbatim}
            NL = CreateImageGraph(U)
\end{verbatim}
where \lstinline!U! is an $m \times n$ image and \lstinline!NL! is the corresponding (sparse) normalized graph Laplacian matrix of size $mn \times mn$.
Use $\sigma_{dist}^{2}=150$ for the distance weighting, and $\sigma_{int}^2=0.002$ for the intensity weighting.
Consider the 8 surrounding neighbour pixels when constructing the weighted graph data.
Submit your code.
\SolutionImageDegmentationMatlabPartA

\newpage

\item
The \rmp{[15]}incomplete Matlab program \lstinline!CellSegment.m!\ reads a block from a cell image file \lstinline!cellimage.tif!, computes the normalized graph Laplacian matrix (using \lstinline!CreateImageGraph! above), performs normalized spectral clustering image segmentation, and displays the final segmentation results.
You should complete the missing part of the program as indicated in the code, i.e., implement normalized spectral clustering.
This will involve extracting the appropriate eigenvectors from $NL$, normalizing the rows of the eigenvector matrix, and performing K-means to cluster them.

You may use the Matlab command \lstinline!eigs! to extract the required (subset of) eigenvectors from the sparse matrix (careful: \lstinline!eigs! default behavior returns eigenpairs for a few of the \textbf{largest} magnitude eigenvalues).
Similarly, you can perform K-means clustering using the Matlab command \lstinline!kmeans!, to determine the cluster indices for the output variable \lstinline!index! found in the code.
(For \lstinline!kmeans!, use the additional parameter \lstinline!replicates!, set to 20, to run K-means 20 times and return the best result.)
Use $K=9$ for the K-means process.

Submit all your code.
Also submit a copy of Figure 1 generated by the program (i.e., containing the original
image and the segmentation results).
\SolutionImageDegmentationMatlabPartB

\end{enumerate}

\end{enumerate}

\end{document}