\documentclass[11pt,onecolumn]{article}
\usepackage{amssymb, amsmath, amsthm,graphicx, paralist,algpseudocode,algorithm,cancel,url,color}
\usepackage{sectsty}
\usepackage{fancyvrb}
\usepackage{mathrsfs}
\usepackage{multirow}
\usepackage{hhline}
\usepackage{booktabs}
\usepackage[table]{xcolor}
\usepackage{tikz}
% \usepackage[framed,numbered,autolinebreaks,useliterate]{mcode}
\usepackage{listings}
\usepackage{enumitem}
\newcommand{\bvec}[1]{\mathbf{#1}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\tx}{\tilde{x}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\Rn}{\R^{n\times n}}
\newcommand{\Rmn}{\R^{m\times n}}
\newcommand{\Cn}{\C^{n\times n}}
\newcommand{\Cmn}{\C^{m\times n}}
\newcommand{\cO}{\mathcal{O}}
\DeclareMathOperator{\Tr}{Tr}
\DeclareMathOperator{\trace}{trace}
\DeclareMathOperator{\diag}{diag}
\sectionfont{\Large\sc}
\subsectionfont{\sc}
\usepackage[margin=1 in]{geometry}
\begin{document}
\noindent
\textsc{\Large CS 6210: Homework 2}\\
Instructor: Anil Damle\\
Due: September 20, 2023\\
\subsection*{Policies}
You may discuss the homework problems freely with other students, but please
refrain from looking at their code or writeups (or sharing your own).
Ultimately, you must implement your own code and write up your own solution to
be turned in. Your solution, including plots and requested output from your code
should be typeset and submitted via the Gradescope as a pdf file. Additionally, please
submit any code written for the assignment. This can be done
by either including it in your solution as an appendix, or uploading it as a zip
file to the separate Gradescope assignment.\\
\hrule
\vspace{1cm}
\noindent
\subsection*{Question 1:}
Let $V\in\Rmn$ with $m\geq n$ have orthonormal columns, prove the following:
\begin{enumerate}[label=(\alph*)]
\item For any $x\in\R^m,$ $VV^Tx$ is the unique closest point in the range of $V$ to $x.$
\item Prove that the orthogonal projector (also often referred to as the spectral projector) onto the range of $V$ is unique.
\end{enumerate}
\subsection*{Question 2:}
For square or rectangular $A$ with $m\geq n$ and full column rank implement the computation of a (reduced) QR factorization via Householder triangularization. This now gives you a means for solving linear systems and least squares problems.
\begin{enumerate}[label=(\alph*)]
\item Clearly illustrate that your algorithm scales linearly with $m$ and quadratically in $n.$
\item Build a set of square problems that are increasingly ill-conditioned. (These should be general dense matrices and not something explicitly structured, i.e., do not use diagonal matrices.) In particular, they should be built such that you ``know'' the QR factorization; this can be accomplished by generating a random orthogonal matrix $Q$ and upper triangular matrix $R$ with the desired condition number (because $\kappa(A)=\kappa(R)$) followed by setting $A=QR.$
Given matrices generated by this process, use your code to compute a QR factorization of $A$ and call the resulting matrices $\tilde{Q}$ and $\tilde{R}.$ Compute the forward errors $\|Q-\tilde{Q}\|_2$ and $\|R-\tilde{R}\|_2$ and plot the results (recall that a QR factorization is not unique, so be careful in how you do this). What happens as the condition number increases? Also plot the backward errors $\|A-\tilde{Q}\tilde{R}\|_2,$ what behavior do you observe? How do the two errors compare?
\item Using the same set of problems, explore the relationship between the condition number of the problem and your ability to accurately solve $Ax=b$ using your QR factorization routine.
\end{enumerate}
\subsection*{Question 3:}
Say we would like to compute a QR factorization of $A^k$ for some real, square $A$ and (potentially large) integer $k.$
\begin{enumerate}[label=(\alph*)]
\item Even if it is feasible to simply construct $A^k,$ is it be good idea numerically to compute its QR factorization directly? Justify your response.
\item Develop a scheme to compute a QR factorization of $A^k$ via a sequence of $k$ QR factorizations of matrices whose condition number is never larger than that of $A$ itself. As long as you adhere to this constraint, for the purposes of this problem you may assume that computing matrix matrix products with the resulting $Q$ and/or $R$ matrices is fine numerically.
\end{enumerate}
\subsection*{Question 4:}
\begin{enumerate}[label=(\alph*)]
\item Given any $A\in\Rmn$ and $\lambda > 0$ prove that the solution to the regularized least squares problem
\begin{equation}
\min_x \|Ax-b\|_2^2+\lambda\|x\|_2^2
\label{eqn:ls}
\end{equation}
is unique.
\item In practice, we often want to solve~\eqref{eqn:ls} for many values of $\lambda.$ Say we are in a situation where $m\gg n,$ $A$ is full column rank (though potentially ill-conditioned), and we would like to avoid the use of the normal equations. Assume you are given the reduced QR factorization $A=QR.$ Devise a scheme to solve~\eqref{eqn:ls} for $T$ values of $\lambda$ (i.e., $\lambda_1,\ldots,\lambda_T$ with $\lambda_i>0$) that costs at most $\cO(mn+Tn^3).$ Critically, note that the dependence on $T$ only scales with $n$ and not $m.$
\end{enumerate}
\end{document}