Exercise 5.11: Details of Example 5.19

chapter 5 incomplete

(a)

The inequality follows directly from the Von Neumann trace inequality, and note that $\Vert W{\Vert }_2$ is achieved by setting $\mathrm{\Theta }$ equal to the outer product of the right and left singular vectors of $W$ corresponding to the largest singular value.

(b)

Simply note that $$\begin{array}{}\text{(1)}& X_{\mathrm{\Theta }}-X_{{\mathrm{\Theta }}^{\prime }}=⟨W,\mathrm{\Theta }-{\mathrm{\Theta }}^{\prime }⟩\in \mathrm{SG}(\Vert \mathrm{\Theta }-{\mathrm{\Theta }}^{\prime }{\Vert }_F),\end{array}$$ using that the entries of $W$ are independent and in $\mathrm{SG}(1)$.

(c)

By the Von Neumann trace inequality and using that $\mathrm{rank}(\mathrm{\Sigma }-{\mathrm{\Sigma }}^{\prime })\le 2$, $$\begin{array}{}\text{(2)}& ⟨\mathrm{\Gamma }-{\mathrm{\Gamma }}^{\prime },W⟩\le ({\sigma }_1(\mathrm{\Gamma }-{\mathrm{\Gamma }}^{\prime })+{\sigma }_2(\mathrm{\Gamma }-{\mathrm{\Gamma }}^{\prime })){\sigma }_1(W)\le \sqrt{2}({\sigma }_1^2(\mathrm{\Gamma }-{\mathrm{\Gamma }}^{\prime })+{\sigma }_2^2(\mathrm{\Gamma }-{\mathrm{\Gamma }}^{\prime }){)}^{\frac{1}{2}}{\sigma }_1(W).\end{array}$$ Therefore, $$\begin{array}{}\text{(3)}& ⟨\mathrm{\Gamma }-{\mathrm{\Gamma }}^{\prime },W⟩\le \sqrt{2}\Vert \mathrm{\Gamma }-{\mathrm{\Gamma }}^{\prime }{\Vert }_F\Vert W{\Vert }_2\le \sqrt{2}\delta \Vert W{\Vert }_2.\end{array}$$

(d)

Consider $a{b}^{\mathsf{\text{T}}}$ and $x{y}^{\mathsf{\text{T}}}$ such that $\Vert a{b}^{\mathsf{\text{T}}}{\Vert }_F,\Vert x{y}^{\mathsf{\text{T}}}{\Vert }_F\le 1$. Noting that $\Vert a{b}^{\mathsf{\text{T}}}{\Vert }_F=\Vert a\Vert \Vert b\Vert$, without loss of generality, assume that $\Vert a\Vert =\Vert y\Vert =1$ and $\Vert b\Vert ,\Vert x\Vert \le 1$. Decompose $$\begin{array}{}\text{(4)}& (a_i{b}_j-x_i{y}_j{)}^2& =(a_i{b}_j-a_i{y}_j+a_i{y}_j-x_i{y}_j{)}^2\text{(5)}& & =a_i^2(b_j-y_j{)}^2+(a_i-x_i{)}^2{y}_j^2+2(a_i^2-a_i{x}_i)(b_j{y}_j-y_j^2).\end{array}$$ Then, summing over $i\in [n]$ and $j\in [d]$ and using that $\Vert a\Vert =\Vert y\Vert =1$, $$\begin{array}{}\text{(6)}& \Vert a{b}^{\mathsf{\text{T}}}-x{y}^{\mathsf{\text{T}}}{\Vert }_F^2=\Vert b-y{\Vert }^2+\Vert a-x{\Vert }^2-2(1-⟨a,x⟩)(1-⟨b,y⟩)\le \Vert b-y{\Vert }^2+\Vert a-x{\Vert }^2,\end{array}$$ since $⟨a,x⟩\le \Vert x\Vert \le 1$ and similarly $⟨b,y⟩\le 1$. Therefore, $$\begin{array}{}\text{(7)}& \Vert a{b}^{\mathsf{\text{T}}}-x{y}^{\mathsf{\text{T}}}{\Vert }_F\le \Vert (a,b)-(x,y)\Vert ,\end{array}$$ which means that the covering is reduced to a covering of the $\sqrt{2}$-ball of ${\mathbb{R}}^{n+d}$ ($\Vert (a,b){\Vert }^2=\Vert a{\Vert }^2+\Vert b{\Vert }^2\le 2$).

This bound is valid but larger by a $\sqrt{2}$ than what is required!

(d) Alternative Solution

We use the equivalent form of the Frobenius norm, $\Vert A{\Vert }_F^2=\sum _i{\sigma }_i^2(A)$, where ${\sigma }_i(A)$ is the $i^{\text{th}}$ singular value of $A$. Square singular values are equal to the eigenvalues of the Gram matrix $$\begin{array}{}\text{(8)}& G:=(a{b}^{\mathrm{\top }}-x{y}^{\mathrm{\top }}{)}^{\mathrm{\top }}(a{b}^{\mathrm{\top }}-x{y}^{\mathrm{\top }})=\Vert a{\Vert }^{2}b{b}^{\mathrm{\top }}+\Vert x{\Vert }^{2}y{y}^{\mathrm{\top }}-⟨a,x⟩(b{y}^{\mathrm{\top }}+y{b}^{\mathrm{\top }}).\end{array}$$ The next step is to show that $y-b$ and $y+b$ are (proportional to) the only two eigenvectors of $G$ associated with non-zero eigenvalues (recall $\mathrm{rank}(G)\le 2$). With a bit of algebra and w.l.o.g. assuming $\Vert a\Vert =\Vert b\Vert =\Vert x\Vert =\Vert y\Vert =1$ (since $\Vert a{b}^{\mathrm{\top }}\Vert =1$, $\{(ca)(b/c{)}^{\mathrm{\top }}{\}}_{c>0}$ are all equivalent representations of $a{b}^{\mathrm{\top }}$), we obtain $$\begin{array}{}\text{(9)}& G(y-b)& =(1+⟨a,x⟩)(1-⟨b,y⟩)(y-b),\text{(10)}& G(y+b)& =(1-⟨a,x⟩)(1+⟨b,y⟩)(y+b).\end{array}$$ By the mentioned relation between the eigenvalues and Frobenius norm $$\begin{array}{}\text{(11)}& \Vert a{b}^{\mathrm{\top }}-x{y}^{\mathrm{\top }}{\Vert }_F^2=(\frac{1}{2}\Vert a+x{\Vert }^2)(\frac{1}{2}\Vert b-y{\Vert }^2)+(\frac{1}{2}\Vert a-x{\Vert }^2)(\frac{1}{2}\Vert b+y{\Vert }^2),\end{array}$$ where used $1-⟨a,x⟩=\frac{1}{2}\Vert a-x{\Vert }^2$ by the unit norm assumption (analogously for the other terms). Another application of the unit norm yields $\Vert a{b}^{\mathrm{\top }}-x{y}^{\mathrm{\top }}{\Vert }_F\le \Vert (a,b)-(x,y){\Vert }_2$ as before.

This bound is valid but larger by a $\sqrt{2}$ than what is required!