Lemma 8.3 — entries of $\mathcal F U$ are at most $\sqrt{2\eta\ln(2mn/\delta)}$ w.p. $1-\delta$

Let $n \ge 1$, let $F \in \mathbb{R}^{n\times n}$ be an orthogonal seed matrix with $\eta = \max_{i,j}|F_{ij}|^2$, and let $\mathcal F = FD$ be the random mixing matrix, $D$ diagonal with i.i.d. Rademacher entries. Let $U$ be an $n\times m$ matrix with orthonormal columns ($U^TU = I_m$). Then for every $\delta > 0$, with probability at least $1-\delta$, for all $i$ and $j$,

The mixing matrix thus prevents the entries of an orthonormal matrix from being large: every entry of $\mathcal FU$ is, with high probability, within a logarithmic factor of $\sqrt{\eta}$. The paper imports this lemma from Ailon and Chazelle (2006) and Avron, Maymounkov and Toledo (2010) without proof.

Formalization Note The probability is over the diagonal $d$ of $D$ under signMeasure n; $\mathcal F =$ mixingMatrix F d. The paper writes $\eta = \max|F_{ij}|^2$ for the seed $F$; since $|\mathcal F_{ij}| = |F_{ij}|$ almost surely the two readings agree. For $m = 0$ the claim is vacuous in $i, j$; when $2mn/\delta < 1$ Lean's Real.sqrt of the negative logarithm is $0$, but then $\delta > 2$ and $1 - \delta < 0$, so the claim is trivially true there as on the page.