\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage[a4paper, total={6in, 8in}]{geometry}
\usepackage{amsmath, amsfonts}
\usepackage{hyperref, graphicx}

\title{CSCI 145 Problem 4: How Many Iterations Does the Power Method Need?}
\author{} % TODO: Put your name here
\date{\today}

\begin{document}

\maketitle

\subsection*{Submission Instructions}

Please upload your work to Gradescope by \textbf{11:59pm on DATE}. % TODO: date
\begin{itemize}
\item Turn in a single PDF of \textit{handwritten} solutions. Typed (including \LaTeX) solutions will not be accepted.
\item Problems are grouped into three-week \textbf{cycles}. Once per cycle, you will meet with the grader and present the solution to \emph{one} problem from that cycle, selected at random when you arrive --- so bring your work and be ready to explain any of them.
\end{itemize}

\newpage \section*{Problem 4: How Many Iterations Does the Power Method Need? \hfill \textnormal{2 points}}

Let $\mathbf{A}\in\mathbb{R}^{d\times d}$ be symmetric with orthonormal
eigenvectors $\mathbf{v}_1,\ldots,\mathbf{v}_d$ and eigenvalues
$\lambda_1>\lambda_2>0$ and
$\lambda_2\geq\cdots\geq\lambda_d\geq0$.  The power method starts
from the unit vector
$\mathbf{v}^{(0)}=\sum_{i=1}^d c_i\mathbf{v}_i$ with $c_1\neq0$.
Let $\theta_k$ be the angle between $\mathbf{A}^k\mathbf{v}^{(0)}$ and
$\mathbf{v}_1$.

Produce a quantitative guarantee for the number of matrix--vector products
needed to make $\tan\theta_k\leq\epsilon$.  Your guarantee should account for
both the initial alignment $\tan\theta_0$ and the eigengap, and it should be
justified from the eigenbasis expansion rather than asserted from the demo's
plot.  Then evaluate the smallest guaranteed iteration count for
$\epsilon=10^{-6}$ and $\theta_0=45^\circ$ in two cases: the lecture matrix
with $(\lambda_1,\lambda_2)=(3,1)$, and a matrix with
$\lambda_2/\lambda_1=0.99$.  Use the comparison to decide when the power
method is a practical replacement for a full $O(d^3)$ eigendecomposition,
given that each dense matrix--vector product costs $O(d^2)$.

\paragraph{Results you may use.}
Normalization does not change direction, and lecture established
\begin{align*}
    \mathbf{A}^k\mathbf{v}^{(0)}
    =\sum_{i=1}^d\lambda_i^k c_i\mathbf{v}_i.
\end{align*}
For a vector written in this orthonormal eigenbasis, $\tan\theta_k$ is the
norm of its component orthogonal to $\mathbf{v}_1$ divided by the magnitude
of its component along $\mathbf{v}_1$.

%\input{solutions/solution04}

\end{document}
