Exercise 5.11: Details of Example 5.19
(a)
The inequality follows directly from the Von Neumann trace inequality, and note that $\norm{W}_2$ is achieved by setting $\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{equation} X_\Theta - X_{\Theta’} = \lra{W, \Theta - \Theta’} \in \SG(\norm{\Theta - \Theta’}_F), \end{equation} using that the entries of $W$ are independent and in $\SG(1)$.
(c)
By the Von Neumann trace inequality and using that $\rank(\Sigma - \Sigma’) \le 2$, \begin{equation} \lra{\Gamma - \Gamma’, W} \le (\sigma_1(\Gamma - \Gamma’) + \sigma_2(\Gamma - \Gamma’))\sigma_1(W) \le \sqrt{2} (\sigma_1^2(\Gamma - \Gamma’) + \sigma_2^2(\Gamma - \Gamma’))^{\frac12} \sigma_1(W). \end{equation} Therefore, \begin{equation} \lra{\Gamma - \Gamma’, W} \le \sqrt{2}\norm{\Gamma - \Gamma’}_F \norm{W}_2 \le \sqrt{2} \delta \norm{W}_2. \end{equation}
(d)
Consider $ab^\T$ and $xy^\T$ such that $\norm{a b^\T}_F, \norm{x y^\T}_F \le 1$. Noting that $\norm{a b^\T}_F = \norm{a}\norm{b}$, without loss of generality, assume that $\norm{a} = \norm{y} = 1$ and $\norm{b},\norm{x}\le 1$. Decompose \begin{align} (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 \newline &= 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{align} Then, summing over $i \in [n]$ and $j \in [d]$ and using that $\norm{a} = \norm{y} = 1$, \begin{equation} \norm{ab^\T - xy^\T}_F^2 = \norm{b - y}^2 + \norm{a - x}^2 - 2\parens{1 - \lra{a, x}}\parens{1 - \lra{b, y}} \le \norm{b - y}^2 + \norm{a - x}^2, \end{equation} since $\lra{a, x} \le \norm{x} \le 1$ and similarly $\lra{b, y} \le 1$. Therefore, \begin{equation} \norm{ab^\T - xy^\T}_F \le \norm{(a, b) - (x, y)}, \end{equation} which means that the covering is reduced to a covering of the $\sqrt{2}$-ball of $\R^{n + d}$ ($\norm{(a, b)}^2 = \norm{a}^2 + \norm{b}^2 \leq 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, $\norm{A}_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{align} G := (ab^\top - xy^\top)^\top (ab^\top - xy^\top) = \norm{a}^2 bb^\top + \norm{x}^2 yy^\top - \langle a, x \rangle (by^\top + yb^\top) \, . \end{align} 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 $\rank(G) \leq 2$). With a bit of algebra and w.l.o.g. assuming $\norm{a} = \norm{b} = \norm{x} = \norm{y} = 1$ (since $\norm{ab^\top} = 1$, $\lbrace (ca)(b/c)^\top \rbrace_{c > 0}$ are all equivalent representations of $ab^\top$), we obtain \begin{align} G (y - b) &= (1 + \langle a, x \rangle) (1 - \langle b, y \rangle) (y - b) \, , \newline G (y + b) &= (1 - \langle a, x \rangle) (1 + \langle b, y \rangle) (y + b) \, . \end{align} By the mentioned relation between the eigenvalues and Frobenius norm \begin{align} \norm{ab^\top - xy^\top}_F^2 = (\tfrac{1}{2} \norm{a + x}^2) (\tfrac{1}{2} \norm{b - y}^2) + (\tfrac{1}{2} \norm{a - x}^2) (\tfrac{1}{2} \norm{b + y}^2) \, , \end{align} where used $1 - \langle a, x \rangle = \tfrac{1}{2} \norm{a - x}^2$ by the unit norm assumption (analogously for the other terms). Another application of the unit norm yields $\norm{ab^\top - xy^\top}_F \leq \norm{(a,b) - (x, y)}_2$ as before.
This bound is valid but larger by a $\sqrt{2}$ than what is required!