Exercise 5.13: Details of Example 5.33

chapter 5

We continue with the results from Exercise 5.11. Assume that \begin{equation} \norm{a} = \norm{b} = \norm{x} = \norm{y} = 1. \end{equation} We then have the equality \begin{equation} \norm{ab^\T - xy^\T}_F^2 = \norm{a - x}^2 + \norm{b - y}^2 - \tfrac12 \norm{a - x}^2\norm{b - y}^2. \end{equation} Denote \begin{equation} \delta^2 = \norm{(a, b) - (x, y)}^2, \quad \beta^2 = \norm{a - x}^2. \end{equation} Then \begin{equation} \norm{ab^\T - xy^\T}_F^2 = \delta^2 - \tfrac12 \beta^2(\delta^2 - \beta^2) \ge \inf_{\beta \ge 0}\,(\delta^2 - \tfrac12 \beta^2(\delta^2 - \beta^2)) = \delta^2 - \tfrac18 \delta^4 \ge \tfrac{31}{32} \delta^2, \end{equation} for $\delta \in (0, \tfrac12)$. Consider $\delta/c$-packings of the unit spheres $\Sb^{n-1}$ and $\Sb^{d-1}$ with $c = \sqrt{2\cdot31/32}\ge 1$, and suppose that \begin{equation} \log M(\delta, \Sb^{n-1}, \norm{\vardot}) \gtrsim n \log(1/\delta). \end{equation} Then \begin{equation} \log M(\delta, \mathbb{M}^{n,d}(1), \norm{\vardot}_F) \gtrsim (n + d) \log(c/\delta) \gtrsim (n + d) \log(1/\delta). \end{equation}