\documentclass[12pt,a4paper,twoside,notitlepage]{report}%
\pagestyle{plain}
\setcounter{secnumdepth}{0}

\usepackage{amsfonts, amsmath, amssymb, amsthm}
\usepackage{dsfont}
\usepackage{enumerate}
\usepackage[ruled,vlined]{algorithm2e}
\usepackage{color}

\setlength{\topmargin}{-1.0in}
\setlength{\textheight}{9.25in}
\setlength{\oddsidemargin}{0.0in}
\setlength{\evensidemargin}{0.0in}
\setlength{\textwidth}{6.5in}

% Personnal commands
\newcommand{\ux}{{\underline{x}}}
\newcommand{\uz}{{\underline{z}}}
\newcommand{\ue}{{\underline{e}}}
\newcommand{\ua}{{\underline{a}}}
\newcommand{\E}{{\mathbb{E}}}


\title{Graded Homework 3\\CS-526 Learning Theory}
\author{Your name}
\date{}

\begin{document}
\maketitle
\vspace{-0.8cm}\hrule\vspace{0.5cm}
\textcolor{red}{Important: we have left the latex code of the exercises in this template so that you can copy/paste the notations and reduce (a bit) the hassle. PLEASE REMOVE IT AND ONLY KEEP YOUR ANSWERS FOR YOUR SUBMISSION.}

\subsubsection{Problem 1: Comparison of tensor rank and multilinear rank}

Recall that the ``tensor rank'' (usually called ``rank'') is the smallest $R$ such that the multiarray $T^{\alpha\beta\gamma}$ can be decomposed as a sum of rank one terms in the form
$$
T^{\alpha\beta\gamma} = \sum_{j=1}^R a_j^\alpha b_j^\beta c_j^\gamma\qquad  {\rm or\,\, equivalently} \qquad T = \sum_{j=1}^R \vec{a}_j\otimes \vec{b}_j \otimes \vec{c}_j \;.
$$
This is often denoted ${\rm rank}_\otimes(T) = R$.
On the other hand, the multilinear rank is the tuple ${\rm rank}_\boxplus(T) = (R_1, R_2, R_3)$ where $R_1$, $R_2$, $R_3$ are the ranks of the three 
matricizations $T_{(1)}$, $T_{(2)}$, $T_{(3)}$ defined in class.\\
\noindent 1. Show that ${\rm max}\, {\rm rank}_\boxplus(T)\leq {\rm rank}_\otimes(T)$.\\

\noindent 2. Suppose that: (i) the matrices $A=\begin{bmatrix}
\vec{a}_1 & \cdots & \vec{a}_R
\end{bmatrix}$,
$B =\begin{bmatrix}
\vec{b}_1 & \cdots & \vec{b}_R
\end{bmatrix}$,
$C=\begin{bmatrix}
\vec{c}_1 & \cdots & \vec{c}_R
\end{bmatrix}$ have rank $R$, and (ii) $R_1=R_2=R_3 =R$. Argue why there is no need to regularize the ALS algorithm (at least in theory).

\subsubsection{Problem 2}

Let $T = (T^{\alpha\beta\gamma})$, $\alpha=1,\dots I_1$,  $\beta=1,\dots I_2$, $\gamma=1,\dots I_3$ an order-three tensor.
Suppose that its multilinear rank is 
${\rm rank}_\boxplus(T) = (R_1, R_2, R_3)$ which means that $R_1$, $R_2$, $R_3$ are the ranks of the three 
matricizations $T_{(1)}$, $T_{(2)}$, $T_{(3)}$ defined in class.
We have seen in class that any such tensor has a so-called \textit{Tucker decomposition} (also called higher order singular value decomposition):
$$
T = \sum_{p,q,r =1}^{R_1, R_2, R_3} G^{pqr} \, \vec{u}_p \otimes \vec{v}_q \otimes \vec{w}_r
$$ 
where each of the matrices $[\vec{u}_1, \cdots, \vec{u}_{R_1}]$, $[\vec{v}_1, \cdots, \vec{v}_{R_2}]$, $[\vec{w}_1, \cdots, \vec{w}_{R_3}]$ are made of orthogonal unit vectors. $G = (G^{pqr})$ is called the core tensor (and is not diagonal in general).
In this problem you will prove that this decomposition is not unique and, in fact, that there exist an infinity of such decompositions related by orthogonal transformations.

Let $M^{(u)} = (M^{(u)}_{pp^\prime})$, $M^{(v)} = (M^{(v)}_{qq^\prime})$ and $M^{(w)} = (M^{(w)}_{rr^\prime})$ be three orthogonal matrices of dimensions 
$R_1\times R_1$, $R_2\times R_2$ and $R_3\times R_3$. Define the vectors:
$$
\vec{x}_{p^\prime} = \sum_{p=1}^{R_1} M^{(u)}_{p^\prime p} \vec{u}_{p}, \quad
\vec{y}_{q^\prime} = \sum_{p=1}^{R_1} M^{(v)}_{q^\prime q} \vec{v}_{q}, \quad
\vec{z}_{p^\prime} = \sum_{p=1}^{R_1} M^{(w)}_{r^\prime r} \vec{w}_{r}\;.
$$
Show that there exist a core tensor $H =  (H^{pqr})$ of dimension $R_1\times R_2 \times R_3$ such that 
$$
T = \sum_{p, q, r=1}^{R_1, R_2, R_3} H^{pqr} \, \vec{x}_p \otimes \vec{y}_q \otimes \vec{z}_r \;.
$$

\subsubsection{Problem 3}
Consider the tensor 
$$
T = \sum_{i=1}^K \lambda_i \, \vec{\mu}_i\otimes\vec{\mu}_i\otimes\vec{\mu}_i
$$
where $\vec{\mu}_i\in \mathbb{R}^D$ are linearly independent (so $K \leq D$) and $\lambda_i$ are strictly positive. Consider the matrix
$$
M = \sum_{i=1}^K \lambda_i \, \vec{\mu}_i\otimes\vec{\mu}_i = \sum_{i=1}^K \lambda_i \, \vec{\mu}_i\vec{\mu}_i^T \;.
$$
Note that this is a rank-$K$ symmetric positive semi-definite matrix (there are $D-K$ zero eigenvalues).
Denote $d_1 \geq d_2 \geq \cdots \geq d_K$ the strictly positive eigenvalues of $M$
and
$\vec{u}_1, \vec{u}_2,\dots, \vec{u}_K$ the corresponding eigenvectors.
Hence $M = U \mathrm{Diag}(d_1,\dots,d_K) U^T$ where $U = \begin{bmatrix} \vec{u}_1 & \vec{u}_2 & \cdots & \vec{u}_K \end{bmatrix}$. 
Define the $D \times K$ matrix:
$$
W = U {\rm Diag}(d_1^{-1/2},d_2^{-1/2}, \cdots, d_K^{-1/2}) \;.
$$
The whitening of $T$ is defined as the new tensor obtained by the multilinear transform
$$
T(W, W, W) := \sum_{i=1}^K \lambda_i \, (W^T\vec{\mu}_i) \otimes (W^T\vec{\mu}_i) \otimes (W^T\vec{\mu}_i)
= \sum_{i=1}^K \nu_i \, \vec{v}_i\otimes \vec{v}_i\otimes \vec{v}_i
$$
where $\nu_i = \lambda_i^{-1/2}$ and $\vec{v}_i = \sqrt{\lambda_i} \, W^T \vec{\mu}_i$.

\begin{enumerate}
	\item
	Show that $W^T M W = I$ where $I$ is the $K\times K$ identity matrix. Deduce that the $\vec{v}_i$'s are orthonormal, i.e., $V^T V = I$ where $V = \begin{bmatrix}
	\vec{v}_1 & \cdots & \vec{v}_K
	\end{bmatrix}$.
	\item
	Suppose we are given a tensor $T$ and we know for some reason that it is of the form $T = \sum_{i=1}^K \lambda_i \, \vec{\mu}_i\otimes\vec{\mu}_i\otimes\vec{\mu}_i$ where $\vec{\mu}_i\in \mathbb{R}^D$ are linearly independent and $\lambda_i>0$.
	Further assume that the matrix $M=\sum_{i=1}^K \lambda_i \, \vec{\mu}_i\vec{\mu}_i^T $ is known.\\
	Explain how we can use the whitening method to recover the $\lambda_i$'s and $\mu_i$'s using the tensor power method. Give a closed-form formula for the matrix $\mu = \begin{bmatrix}
	\vec{\mu}_1 & \cdots & \vec{\mu}_K
	\end{bmatrix}$ that uses $V$, $\mathrm{Diag}(\nu_1,\dots,\nu_K)$ and $W$.
\end{enumerate}

\subsubsection{\bf Problem 4}
Consider the following Gaussian Mixture Model (GMM):
$$
p(\underline x) = \sum_{i=1}^K w_i\,\frac{1}{(2\pi \sigma^2)^{\frac{D}{2}}} \exp\bigg(-\frac{\Vert \underline x - \underline a_i\Vert^2}{2\sigma^2}\bigg)
$$
where $\underline x \in \mathbb{R}^D$, the matrix $A := \begin{bmatrix} \underline a_1 & \cdots & \underline a_K  \end{bmatrix}$ has full column rank, i.e., its columns are linearly independent, and the weights $w_i \in (0,1]$ satisfy $\sum_{i=1}^K w_i =1$. We suppose that $K < D$.
You can think of the distribution $p(\cdot)$ has $K$ clusters centered at $\underline a_1,\dots, \underline a_K$, and the probability to belong to the cluster centered at $\underline a_r$ is $w_r$.\\ 
You saw in Problem 1 of Homework 6 that the first moment vector, the second moment matrix and the third moment tensor of this distribution are:
\begin{align*}
\mathbb{E}[\underline x] &= \sum_{i=1}^K w_i\,\underline a_i\\
\mathbb{E}[\ux\,\ux^T] &= \sigma^2 I_{D} + \sum_{i=1}^K w_i\,\underline{a}_i \underline{a}_i^T \\
\mathbb{E}[\underline x \otimes \underline x\otimes \underline x]
&= \sum_{i=1}^K w_i \, \ua_i \otimes \ua_i \otimes \ua_i
+ \sigma^2 \sum_{j=1}^{D} \mathbb{E}[\underline x] \otimes \ue_j \otimes \ue_j
+ \ue_j \otimes \mathbb{E}[\underline x] \otimes \ue_j
+ \ue_j \otimes \ue_j \otimes \mathbb{E}[\underline x]
\end{align*}
\end{document}
