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

\title{CSCI 145 Problem 15: Compress for the Deployment}
\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; bring your work and be ready to explain any of them.
\end{itemize}

\newpage \section*{Problem 15: Compress for the Deployment \hfill \textnormal{2 points}}

A linear layer $\mathbf{A}\in\mathbb R^{m\times n}$ must be replaced by a matrix $\mathbf{B}$ of rank at most $k$. Two deployment teams disagree about the objective. The safety team minimizes the worst-case error
$$
\sup_{\|\mathbf{x}\|_2=1}\|(\mathbf{A}-\mathbf{B})\mathbf{x}\|_2,
$$
so it uses the truncated SVD $\mathbf{A}_k$. The traffic team instead wants to minimize the average error $\mathbb E\|(\mathbf{A}-\mathbf{B})\mathbf{x}\|_2^2$ for inputs with mean zero and positive-definite covariance $\mathbf{\Sigma}_x$.

Determine and justify an optimal rank-$k$ layer for the traffic team. Your argument should reduce its objective to a low-rank approximation problem to which Eckart--Young--Mirsky applies, and it should make clear why the resulting layer need not equal $\mathbf{A}_k$.

Give an explicit $2\times2$ matrix $\mathbf{A}$, positive-definite covariance $\mathbf{\Sigma}_x$, and $k=1$ for which the two teams choose different compressed layers. Use the example to explain how deployment frequency can outweigh a direction's worst-case error.

\paragraph{Results you may use.}
You may quote the worst-case result $\mathbf{A}_k\in\arg\min_{\operatorname{rank}(\mathbf{B})\leq k}\|\mathbf{A}-\mathbf{B}\|_2$, Eckart--Young--Mirsky in Frobenius norm, and the identity
$$
\mathbb E\| (\mathbf{A}-\mathbf{B})\mathbf{x}\|_2^2
=\| (\mathbf{A}-\mathbf{B})\mathbf{\Sigma}_x^{1/2}\|_F^2,
$$
which holds when $\mathbb E[\mathbf{x}]=\mathbf{0}$ and $\mathbb E[\mathbf{x}\mathbf{x}^\top]=\mathbf{\Sigma}_x$.
Because $\mathbf{\Sigma}_x$ is positive definite, $\mathbf{\Sigma}_x^{1/2}$ is invertible and $\operatorname{rank}(\mathbf{B}\mathbf{\Sigma}_x^{1/2})=\operatorname{rank}(\mathbf{B})$.

%\input{solutions/solution15}
\end{document}
