\documentclass[11pt]{article} 
\usepackage[T1]{fontenc}
\usepackage{amsmath}
\usepackage{amsxtra}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{graphicx}
\usepackage{url}
\usepackage{fancyvrb}
\usepackage{color,hyperref}
\usepackage{enumerate}
\hypersetup{colorlinks,breaklinks,
             linkcolor=blue,urlcolor=blue,
           anchorcolor=blue,citecolor=blue}

\usepackage[margin=3cm]{geometry}

\usepackage{preamble}

\begin{document}

\section*{Math 5490 -- Homework 4: Due March 22 by 11:59pm}
\thispagestyle{empty}

\subsection*{Instructions:}

\begin{itemize}
\item  Complete the problems below, and submit your solutions and Python code by uploading them to the Google form: \url{https://forms.gle/k5HPD8UuPdSRbEtu8}
\item Submit all your Python code in a single .py file using the function templates given in each problem. I will import your functions from this file and test your code.
\item If you use LaTeX to write up your solutions, upload them as a pdf file. Students who use LaTeX to write up their solutions will receive bonus points on the homework assignment (equivalent to 1/3 of a letter grade bump).
\item If you choose to handwrite your solutions and scan them, please either use a real scanner, or use a smartphone app that allows scanning with you smartphone camera. It is not acceptable to submit photos of your solutions, as these can be hard to read.
\end{itemize}


\subsection*{Problems:}


\begin{enumerate}
\item Consider the weighted PCA energy
\[E_\w(V;\x_1,\dots,\x_m)  = \sum_{i=1}^m w_i\dist(\x_i,V)^2,\]
where $\w=(w_1,w_2,\dots,w_m)$ are nonnegative numbers (weights), and $V$ is a linear space.
\begin{enumerate}[(i)]
\item  Show that the weighted energy $E_\w$ is minimized over $k$-dimensional subspaces $V\subset \R^n$ by setting 
\[V = \text{span}\{\q_1,\q_2,\dots,\q_k\},\]
where $\q_1,\q_2,\dots,\q_n$ are the orthonormal eigenvectors of the weighted covariance matrix 
\[M_\w = \sum_{i=1}^mw_i \x_i\x_i^T,\]
with corresponding eigenvalues $\lambda_1\geq \lambda_2 \geq \cdots \geq \lambda_n$.
\item Show that the weighted covariance matrix can also be expressed as
\[M_\w = X^T W X,\]
where $W$ is the $m\times m$ diagonal matrix with diagonal entries $w_1,w_2,\dots,w_m$, and 
\[X = \begin{bmatrix} \x_1 & \x_2 & \cdots & \x_m\end{bmatrix}^T.\]
\item Show that the optimal energy is given by 
\[E_\w(V;\x_1,\dots,\x_m) = \sum_{i=k+1}^n \lambda_i.\]
\item Suppose we minimize $E_\w$ over affine spaces $A = \a+V$, so 
\[E_\w(A;\x_1,\dots,\x_m)  = \sum_{i=1}^m w_i\dist(\x_i,A)^2,\]
Show that an optimal choice for $\a$ is the weighted centroid
\[\a = \frac{\sum_{i=1}^m w_i \x_i}{\sum_{i=1}^m w_i}.\qedhere\]
\end{enumerate}
\item We consider here the $2$-means clustering algorithm in dimension $n=1$. Let $x_1,x_2,\dots,x_m\in \R$ and recall the $2$-means energy is
\[E(c_1,c_2) = \sum_{i=1}^m \min\left\{ (x_i-c_1)^2,(x_i-c_2)^2 \right\}.\]
Throughout the question we assume that the $x_i$ are ordered so that
\[x_1 \leq x_2 \leq \cdots \leq x_m.\]
For $1 \leq j \leq m-1$ we define
\[\mu^-(j) = \frac{1}{j}\sum_{i=1}^j x_i, \ \ \mu^+(j) = \frac{1}{m-j}\sum_{i=j+1}^m x_i,\]
and
\[F(j) =  \sum_{i=1}^j (x_i - \mu^-(j))^2+\sum_{i=j+1}^m (x_i - \mu^+(j))^2.\]
\begin{enumerate}[(i)]
\item Explain how $F(j)$ differs from the $2$-means energy $E(c_1,c_2)$, and why minimizing $F(j)$ over $j=1,\dots,m-1$ and setting $c_1=\mu_-(j_*)$ and $c_2=\mu^+(j_*)$ will give a solution at least as good as the $2$-means algorithm (here, $j_*$ is a minimizer of $F(j)$).
\item By (i) we can replace the $2$-means problem with minimizing $F(j)$. We will now show how to do this efficiently. In this part, show that
\[F(j) = \sum_{i=1}^m x_i^2 - j\mu^-(j)^2 - (m-j)\mu^+(j)^2.\]
Thus, minimizing $F(j)$ is equivalent to maximizing 
\[G(j) = j\mu^-(j)^2 + (m-j)\mu^+(j)^2.\]
\item Show that we can maximize $G$ (i.e., find $j_*$ with $G(j)\leq G(j_*)$ for all $j$) in $O(m\log m)$ computations. Hint: First show that
\[\mu^{-}(j+1) = \frac{j}{j+1}\mu^-(j) + \frac{x_{j+1}}{j+1},\]
and
\[\mu^+(j+1) = \frac{m-j}{m-j-1}\mu^+(j) - \frac{x_{j+1}}{m-j-1}.\]
and explain how these formulas allow you to compute all the values $G(1),G(2),\dots,G(m-1)$ recursively in $O(m\log m)$ operations, at which point the maximum is found by brute force.
\item[(iv)] [Challenge] Implement the method described in the previous three parts in Python. Test it out on some synthetic 1D data. For example, you can try a mixture of two Gaussians with different means. This part of the homework is optional.
\end{enumerate}

\end{enumerate}

\end{document}

