\documentclass[11pt]{article}
\usepackage[letterpaper,margin=1in]{geometry}
\usepackage{amsmath,amsbsy,amsfonts,amssymb,amsthm,commath}
\usepackage[round]{natbib}
\usepackage{hyperref}

% math font macros

\def\ddefloop#1{\ifx\ddefloop#1\else\ddef{#1}\expandafter\ddefloop\fi}
% Blackboard fonts: \bbA, \bbB, ...
\def\ddef#1{\expandafter\def\csname bb#1\endcsname{\ensuremath{\mathbb{#1}}}}
\ddefloop ABCDEFGHIJKLMNOPQRSTUVWXYZ\ddefloop
% Calligraphic fonts: \cA, \cB, ...
\def\ddef#1{\expandafter\def\csname c#1\endcsname{\ensuremath{\mathcal{#1}}}}
\ddefloop ABCDEFGHIJKLMNOPQRSTUVWXYZ\ddefloop
% Bold fonts (for vectors, matrices, etc.): \vA, \vB, ..., \va, \vb, ...
\def\ddef#1{\expandafter\def\csname v#1\endcsname{\ensuremath{\boldsymbol{#1}}}}
\ddefloop ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz\ddefloop
% Bold fonts (for vectors, matrices, etc.): \valpha, \vbeta, ...,  \vGamma, \vDelta, ...,
\def\ddef#1{\expandafter\def\csname v#1\endcsname{\ensuremath{\boldsymbol{\csname #1\endcsname}}}}
\ddefloop {alpha}{beta}{gamma}{delta}{epsilon}{varepsilon}{zeta}{eta}{theta}{vartheta}{iota}{kappa}{lambda}{mu}{nu}{xi}{pi}{varpi}{rho}{varrho}{sigma}{varsigma}{tau}{upsilon}{phi}{varphi}{chi}{psi}{omega}{Gamma}{Delta}{Theta}{Lambda}{Xi}{Pi}{Sigma}{varSigma}{Upsilon}{Phi}{Psi}{Omega}{ell}\ddefloop

% other macros

\renewcommand\v[1]{{\ensuremath{\boldsymbol{#1}}}}
\renewcommand\t{{\ensuremath{\scriptscriptstyle{\top}}}}
\newcommand\ip[1]{\langle #1 \rangle} % inner product
\newcommand{\E}{\ensuremath{\mathbb{E}}} % expectation
\newcommand{\unitsphere}[1][d-1]{\ensuremath{S^{#1}}} % unit sphere
\newcommand{\Normal}{\ensuremath{\operatorname{N}}} % normal distribution
\newcommand{\cost}{\ensuremath{\operatorname{cost}}} % cost

% environments

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\theoremstyle{definition}
\newtheorem{problem}{Problem}
\newenvironment{solution}{\noindent\emph{Solution.}}{\hfill$\square$}

%-------------------------------------------------------------------------------

\title{COMS 4772 Fall 2016 Homework 2 \\ Due Friday, October 28}
\author{% TODO put your Full Name and UNI here
  }
\date{%
  }

%-------------------------------------------------------------------------------

\begin{document}
\maketitle

\noindent\textbf{Instructions}:
\begin{itemize}
  \item
    The usual homework policies (\url{http://www.cs.columbia.edu/~djhsu/coms4772-f16/about.html}) are, of course, in effect.

  \item
    Using this \LaTeX\ template will be helpful for grading purposes.

\end{itemize}

\newpage

%-------------------------------------------------------------------------------

\begin{problem}[25 points] \
  Let $\vX$ be a random vector in $\bbR^d$ whose distribution is a mixture of
  $k$ spherical Gaussians:
  \begin{equation*}
    \vX \ \sim \
    \pi_1 \Normal(\vmu_1,\sigma_1^2\vI) + \pi_2 \Normal(\vmu_2,\sigma_2^2\vI) + \dotsb + \pi_k \Normal(\vmu_k,\sigma_k^2\vI)
    \,.
  \end{equation*}
  For any set $C \subset \bbR^d$, define
  \begin{equation*}
    \cost(C) \ := \ \E\sbr{ \min_{\vy \in C} \, \norm{\vX - \vy}_2^2 }
    \,.
  \end{equation*}
  Let $M := \cbr{ \vmu_1, \vmu_2, \dotsc, \vmu_k }$.
  Prove that if $k < e^{d/2}$, then
  \begin{equation*}
    \cost(M) \ \leq \
    \frac1{1 - \frac{2\ln(k)}{d}}
    \cdot
    \min_{\substack{C \subset \bbR^d : \\ |C| \leq k}} \cost(C)
    \,.
  \end{equation*}
\end{problem}

\begin{solution}
% Put solution here.
\end{solution}

\newpage

%-------------------------------------------------------------------------------

\begin{problem}[25 points]
  Suppose $\vA, \vB \in \bbR^{n \times d}$ each have rank $d$.
  Give unambiguous pseudocode for an algorithm that, when given $\vA$ and $\vB$
  as inputs, finds all solutions $\vv \in \unitsphere$ satisfying
  \[
    \exists \lambda \in \bbR \setminus \cbr{0} \ \text{s.t.} \
    \vA^\t\vA \vv \ = \ \lambda \vB^\t \vB \vv
    \,.
  \]
  If there is an entire subspace of solutions, the algorithm just needs to
  return an orthonormal basis for this subspace.
  Your pseudocode can use things like SVD, Gram-Schmidt, etc.~as black-box
  subroutines.
  Prove that the algorithm is correct.
\end{problem}

\begin{solution}
% TODO Put solution here.
\end{solution}

\newpage

%-------------------------------------------------------------------------------

\begin{problem}[25 points]
  Let $\vA \in \bbR^{n \times d}$ be a data matrix whose rows are
  $\va_1, \va_2, \dotsc, \va_n \in \bbR^d$.
%  (You can assume that they are distinct and span all of $\bbR^d$.)
  Let $\vD \in \bbR^{n \times n}$ be the matrix whose $(i,j)$-th entry
  is the squared Euclidean distance $D_{i,j} =
  \norm{\va_i-\va_j}_2^2$.
  Suppose you are given the squared Euclidean distance matrix $\vD$ as
  input, and you are asked to recover the set of original points
  $\cbr[0]{ \va_1, \va_2, \dotsc, \va_n }$ up to some translation.
  \emph{You do not have access to the original data matrix $\vA$.}
  \begin{enumerate}
    \item[(a)]
      Let $\vs \in \bbR^n$ be the vector whose $i$-th entry is
      $\norm{\va_i}_2^2$.
      Prove that $\vD = \vs\v1_n^\t - 2\vA\vA^\t + \v1_n\vs^\t$, where
      $\v1_n \in \bbR^n$ is the all-ones vector.

    \item[(b)]
      Let $\vPi \in \bbR^{n \times n}$ be the orthogonal projector for
      the $(n{-}1)$-dimensional subspace
      \begin{equation*}
        \cbr{ \vx \in \bbR^n : \ip{\v1_n,\vx} = 0 }
        \,.
      \end{equation*}
      Prove that $-(1/2)\vPi\vD\vPi = \vPi\vA\vA^\t\vPi$.

    \item[(c)]
      Explain how to determine points $\vx_1, \vx_2, \dotsc, \vx_n \in \bbR^d$
      from $\vD$ such that:
      \begin{itemize}
        \item
          $D_{i,j} = \norm{\vx_i-\vx_j}_2^2$ for all $i,j \in [n]$;
          and

        \item
          $\sum_{i=1}^n \vx_i = \v0$.

      \end{itemize}
      (You may assume that you are told the original dimension $d$.)

    \item[(d)]
      \emph{Optional}.
      Suppose the matrix $\vD$ is corrupted (say, because your distance
      measuring device is imperfect), so the entries no longer correspond to
      the squared Euclidean distances between the $\va_i$.
      Explain how to determine points $\vx_1, \vx_2, \dotsc, \vx_n \in \bbR^n$
      (yes, $n$ and not $d$) from $\vD$ such that:
      \begin{itemize}
        \item
          $\sum_{i=1}^n \vx_i = \v0$;
        \item
          $\norm{\vx_i - \vx_j}_2^2 \geq D_{i,j}$ for all $i \neq j$; and
        \item
          $\max \cbr{ \frac{ \norm{\vx_i - \vx_j}_2^2 }{D_{i,j}} : 1 \leq i < j \leq n }$ is as small as possible.
      \end{itemize}
      \emph{Hint}: use semidefinite programming.

  \end{enumerate}
\end{problem}

\begin{solution}
% TODO Put solution here.
\end{solution}

\newpage

%-------------------------------------------------------------------------------

\begin{problem}[25 points]
  Exercise 3.25 from BHK.
\end{problem}

\begin{solution}
% TODO Put solution here.
\end{solution}

%\newpage

%-------------------------------------------------------------------------------

%\begin{thebibliography}{1}
%  \bibitem[McAllester and Ortiz(2003)]{McAllesterO03}
%  D.~McAllester and L.~Ortiz.
%  \newblock Concentration inequalities for the missing mass and for histogram rule error.
%  \newblock \emph{Journal of Machine Learning Research}, 4(Oct):895--911, 2003.
%\end{thebibliography}

\end{document}
