Exponential Frobenius concentration for normalized Gram sampling

We first prove a finite bounded-differences estimate. If a centered finite real variable $Y$ lies in an interval of length $c$, let $h(s)=\log \mathbb{E}{e}^{sY}$. Differentiating finite sums shows $h^{\mathrm{\prime }\mathrm{\prime }}(s)$ is the variance under the weights proportional to $e^{sY}$. Any variable in $[a,b]$ has variance at most $\mathbb{E}[(Y-(a+b)\mathrm{/}2{)}^2]\le (b-a{)}^2\mathrm{/}4$. Thus $h^{\mathrm{\prime }\mathrm{\prime }}(s)\le c^2\mathrm{/}4$; since $h(0)=h^{\mathrm{\prime }}(0)=0$, integration gives $\mathbb{E}{e}^{sY}\le e^{s^2{c}^2\mathrm{/}8}$ for all real $s$.

Suppose a real function $f$ of independent finite samples changes by at most $c_j$ if sample $j$ is replaced. Reveal samples in order and let $M_j$ be the finite conditional mean of $f$. For each fixed earlier history, the possible values of $M_j$ lie in an interval of length at most $c_j$, since averaging the future preserves the coordinate oscillation bound. Therefore $M_j-M_{j-1}$ is conditionally centered in an interval of that length. Applying step 1.1 conditionally and summing over successive histories gives $\mathbb{E}{e}^{s(f-\mathbb{E}f)}\le e^{s^2{\sum }_j{c}_j^2\mathrm{/}8}$. Markov applied to this exponential, followed by $s=4u\mathrm{/}{\sum }_j{c}_j^2$, gives $\mathbb{P}(f-\mathbb{E}f\ge u)\le e^{-2u^2\mathrm{/}{\sum }_j{c}_j^2}$ when $u>0$ and the denominator is positive. If all $c_j=0$, $f$ is constant on the product support and its upper tail is zero.

For a finite random vector $X$ with $\mathrm{\parallel }X{\mathrm{\parallel }}^2=L$ identically, set $Z=q^{-1}{\sum }_j{X}_j{X}_j^T$ and $H=\mathbb{E}X{X}^T$. Independence cancels the mixed centered terms, and $\mathrm{\parallel }X{X}^T{\mathrm{\parallel }}_F^2=L^2$, so $\mathbb{E}\mathrm{\parallel }Z-H{\mathrm{\parallel }}_F^2\le L^2\mathrm{/}q$. By [F2], $\mathbb{E}\mathrm{\parallel }Z-H{\mathrm{\parallel }}_F\le L\mathrm{/}\sqrt{q}$. Replacing one $X_j$ changes $\mathrm{\parallel }Z-H{\mathrm{\parallel }}_F$ by at most $2L\mathrm{/}q$, by the triangle inequality. Step 2.1 now gives $\mathbb{P}(\mathrm{\parallel }Z-H{\mathrm{\parallel }}_F>L(1+\sqrt{2\log (2\mathrm{/}\delta )})\mathrm{/}\sqrt{q})\le \delta \mathrm{/}2$.

The row sampling is step 3.1 with $X=A_{i,\ast }^T\mathrm{/}\sqrt{D_A(i)}$ and $L=F^2$. Every row of $S$ has squared norm $F^2\mathrm{/}q$, so $\mathrm{\parallel }S{\mathrm{\parallel }}_F=F$. Its column mixture probability is $\mathrm{\parallel }{S}_{\ast ,j}{\mathrm{\parallel }}^2\mathrm{/}{F}^2$; hence every normalized sampled column of $W$ has squared norm $F^2\mathrm{/}q$, and $\mathrm{\parallel }W{\mathrm{\parallel }}_F=F$. Conditional on every realized $S$, step 3.1 applies to the column sampling with the same $L=F^2$ and failure bound $\delta \mathrm{/}2$. Averaging that bound over the finite row histories and adding the first-stage failure bound proves the assertion. Zero-probability rows and columns are never selected and require no division by zero.