Weak-lq thresholding error from an entrywise deviation event

On the event in the Statement, each diagonal error is at most $\lambda \mathrm{/}2$. For an off-diagonal entry that is retained, $\mathrm{\mid }{\sigma }_{jk}\mathrm{\mid }\ge \lambda \mathrm{/}2$ and $\mathrm{\mid }{\widehat{\sigma }}_{jk}-{\sigma }_{jk}\mathrm{\mid }\le \lambda \mathrm{/}2\le \min \{\mathrm{\mid }{\sigma }_{jk}\mathrm{\mid },\lambda \}$. If it is removed, then $\mathrm{\mid }{\sigma }_{jk}\mathrm{\mid }\le \mathrm{\mid }{\widehat{\sigma }}_{jk}^{\ast }-{\sigma }_{jk}\mathrm{\mid }+\mathrm{\mid }{\widehat{\sigma }}_{jk}^{\ast }\mathrm{\mid }<3\lambda \mathrm{/}2$, and its error is $\mathrm{\mid }{\sigma }_{jk}\mathrm{\mid }\le (3\mathrm{/}2)\min \{\mathrm{\mid }{\sigma }_{jk}\mathrm{\mid },\lambda \}$.

For $q=0$, [F1] and step 1.1 bound every off-diagonal column error sum by $(3\mathrm{/}2)c_{n,p}\lambda$. For $0<q<1$, fix a column, put $a_k=\mathrm{\mid }{\sigma }_{-j,j}{\mathrm{\mid }}_{(k)}$, $T=c_{n,p}{\lambda }^{-q}$, and $B_q:={\sum }_{r=0}^{\mathrm{\infty }}{2}^{r(1-1\mathrm{/}q)}=\frac{1}{1-2^{1-1\mathrm{/}q}}<\mathrm{\infty }\mathrm{.}$ The class bound in [F1] gives $a_k\le (c_{n,p}\mathrm{/}k{)}^{1\mathrm{/}q}$. If $T<1$, then ${\sum }_{k=1}^{p-1}\min (a_k,\lambda )\le c_{n,p}^{1\mathrm{/}q}{\sum }_{k=1}^{\mathrm{\infty }}{k}^{-1\mathrm{/}q}\le B_q{c}_{n,p}^{1\mathrm{/}q}\le B_q{c}_{n,p}{\lambda }^{1-q},$ because grouping $2^r\le k<2^{r+1}$ gives at most $2^r(2^r{)}^{-1\mathrm{/}q}$ per block, and $c_{n,p}<{\lambda }^q$. If $T\ge 1$, let $m=\lfloor T\rfloor \ge T\mathrm{/}2$. The first $m$ terms contribute at most $m\lambda \le c_{n,p}{\lambda }^{1-q}$. Grouping the tail into blocks $2^{r}m<k\le 2^{r+1}m$ gives ${\sum }_{k>m}{k}^{-1\mathrm{/}q}\le B_q{m}^{1-1\mathrm{/}q},$ so the tail contributes at most $B_q{c}_{n,p}^{1\mathrm{/}q}{m}^{1-1\mathrm{/}q}\le B_q{2}^{1\mathrm{/}q-1}{c}_{n,p}{\lambda }^{1-q}$; here the exponent $1-1\mathrm{/}q$ is negative and $m\ge T\mathrm{/}2$. Thus for either case each off-diagonal column error sum is at most $C_q{c}_{n,p}{\lambda }^{1-q}$ for a finite constant $C_q$ depending only on $q$. Adding the diagonal error bound $\lambda \mathrm{/}2$ from step 1.1 bounds every row sum by $C_q(c_{n,p}{\lambda }^{1-q}+\lambda )$. For $q=0$, the same total is at most $(3\mathrm{/}2)c_{n,p}\lambda +\lambda \mathrm{/}2\le 2(c_{n,p}\lambda +\lambda )$.

For any unit vector $v$, [F3] identifies the operator norm with the maximum absolute Rayleigh quotient. With $A=\widehat{\mathrm{\Sigma }}-\mathrm{\Sigma }$, symmetry and $2\mathrm{\mid }{v}_j{v}_k\mathrm{\mid }\le v_j^2+v_k^2$ give $\mathrm{\mid }{v}^{\mathsf{T}}(\widehat{\mathrm{\Sigma }}-\mathrm{\Sigma })v\mathrm{\mid }\le {\sum }_{j,k}\mathrm{\mid }{A}_{jk}\mathrm{\mid }\mathrm{\mid }{v}_j\mathrm{\mid }\mathrm{\mid }{v}_k\mathrm{\mid }\le \frac{1}{2}{\sum }_{j,k}\mathrm{\mid }{A}_{jk}\mathrm{\mid }(v_j^2+v_k^2)\le {\max }_j{\sum }_k\mathrm{\mid }{A}_{jk}\mathrm{\mid },$ because $A$ is symmetric, its absolute column sums equal its row sums, and ${\sum }_j{v}_j^2=1$. Taking the maximum over unit $v$ and using step 2.1 yields the claimed operator bound.