A deterministic threshold-band bound for two Gram sketches

Set $H=A^{T}A$, $G=S^{T}S$, $B=S{S}^T$, $C=W{W}^T$, and $a={\sigma }^2$. Since $\mathrm{tr}C=F^2$ and each retained eigenvalue exceeds $a$, $ka<F^2$, so $k<K$. For $k>0$, $T=U^{T}BU\ge {\mathrm{\Sigma }}^2-t{F}^{2}I\ge (a-t{F}^2)I>0$. Therefore $P=S^{T}U{T}^{-1}{U}^{T}S$ is the projection onto the range of $V$. Also $V^{T}V-I={\mathrm{\Sigma }}^{-1}{U}^T(B-C)U{\mathrm{\Sigma }}^{-1}$ has Frobenius norm at most $tK$. By the SVD, the nonzero eigenvalues of $M-P$ are those of $V^{T}V-I$, giving $\mathrm{\parallel }M-P{\mathrm{\parallel }}_F\le tK$. For $k=0$, use $P=M=0$ and the same bounds with empty matrices.

We record the spectral comparisons explicitly. For a symmetric $J$ with decreasing eigenvalues, ${\lambda }_j(J)={\max }_{\dim E=j}{\min }_{x\in E,\mathrm{\parallel }x\mathrm{\parallel }=1}{x}^{T}Jx$: the span of its first $j$ eigenvectors attains the value, and every $j$-dimensional $E$ intersects the span of the eigenvectors numbered $j$ onward. Thus $\mathrm{\mid }{\lambda }_j(J)-{\lambda }_j(J^{\mathrm{\prime }})\mathrm{\mid }\le \mathrm{\parallel }J-J^{\mathrm{\prime }}{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}$. Moreover ${\sum }_{j\le k}{\lambda }_j(J)={\max }_{\mathrm{rank}R=k}\mathrm{tr}(RJ)$ over projections $R$: in an eigenbasis the diagonal entries of $R$ are in $[0,1]$ and sum to $k$, so moving their weight to the first $k$ indices maximizes the sum. By [F2] the top-$k$ sums for $J,J^{\mathrm{\prime }}$ differ by at most $\sqrt{k}\mathrm{\parallel }J-J^{\mathrm{\prime }}{\mathrm{\parallel }}_F$. Pad matrices by zero blocks when dimensions differ. Applying these comparisons to $H,G$ and $B,C$, and using [F1] between $G,B$, gives $\mathrm{\mid }{\lambda }_j(H)-{\lambda }_j(C)\mathrm{\mid }\le 2t{F}^2$ and a top-$k$ sum difference at most $2\sqrt{k}t{F}^2$.

If $k>0$, $U^T{B}^{2}U-T^2=U^{T}B(I-U{U}^T)BU$ is positive semidefinite. Hence $\mathrm{tr}(PG)=\mathrm{tr}[(U^T{B}^{2}U)T^{-1}]\ge \mathrm{tr}T\ge {\sum }_{j\le k}{\lambda }_j(C)-\sqrt{k}t{F}^2$. Also $\mathrm{tr}(PH)\ge \mathrm{tr}(PG)-\sqrt{k}t{F}^2$. Combining these inequalities with the top-$k$ comparisons in step 1.2 gives $\mathrm{\Delta }:={\sum }_{j\le k}{\lambda }_j(H)-\mathrm{tr}(PH)\le 4\sqrt{k}t{F}^2$. The variational formula gives $\mathrm{\Delta }\ge 0$. If $k=0$, $\mathrm{\Delta }=0$.

Let $r$ count eigenvalues of $H$ strictly greater than $a$. Between indices $k$ and $r$, every crossing eigenvalue lies within $2t{F}^2$ of $a$, by step 1.2 and the strict threshold rule for $C$. There are at most $K$ crossing indices: if $r>k$, then $r<K$ since each of its first $r$ eigenvalues exceeds $a$ and $\mathrm{tr}H=F^2$; if $k>r$, then $k<K$. Thus the difference between the sums of the largest $k$ values of ${\lambda }_j(H)-a$ and all positive values of ${\lambda }_j(H)-a$ is at most $2Kt{F}^2$ . Put $p_j=⟨e_j,P{e}_j⟩$ in an eigenbasis of $H$. Since ${\sum }_j{p}_j=k$, the nonnegative threshold deficit is ${\mathrm{\Delta }}_a={\sum }_{{\lambda }_j>a}({\lambda }_j-a)(1-p_j)+{\sum }_{{\lambda }_j\le a}(a-{\lambda }_j)p_j\le \mathrm{\Delta }+2Kt{F}^2\le 6Kt{F}^2\mathrm{.}$ For $k=0$ the same crossing argument applies, and zero eigenvalues can be padded without changing the sums.

Let $P_1,P_2,P_3$ project onto eigenvalues respectively in $[a(1+\eta {)}^2,\mathrm{\infty })$, $[a(1-\eta {)}^2,a(1+\eta {)}^2)$, and $[0,a(1-\eta {)}^2)$. Write $E$ for the part of ${\mathrm{\Delta }}_a$ on the first and third sets, and $L=\mathrm{tr}[P_1(I-P)]+\mathrm{tr}(P_{3}P)$. Both outside gaps from $a$ are at least $\eta a$, so $L\le E\mathrm{/}(\eta a)$ and $E\le 6Kt{F}^2\le 7Kt{F}^2$. This uses no strict separation of eigenvalues within the band.

On the band space, $R=P_{2}P{P}_2$ is a positive contraction. Let $Q$ be its spectral projection onto eigenvalues at least $1\mathrm{/}2$. In an eigenbasis of $R$, $\mathrm{\parallel }{P}_{2}P-Q{\mathrm{\parallel }}_F^2={\sum }_s\min (s,1-s)\le 2{\sum }_{s}s(1-s)=2\mathrm{\parallel }{P}_{2}P(I-P_2){\mathrm{\parallel }}_F^2\le 2L$. For the last inequality, the high cross block satisfies $\mathrm{\parallel }{P}_{2}P{P}_1{\mathrm{\parallel }}_F=\mathrm{\parallel }{P}_2(I-P)P_1{\mathrm{\parallel }}_F\le \mathrm{\parallel }(I-P)P_1{\mathrm{\parallel }}_F$ and the low block satisfies $\mathrm{\parallel }{P}_{2}P{P}_3{\mathrm{\parallel }}_F\le \mathrm{\parallel }P{P}_3{\mathrm{\parallel }}_F$. These squares sum to at most $L$.

Evaluate $\mathrm{\parallel }A(P-P_1-Q){\mathrm{\parallel }}_F^2$ by summing its rows in an eigenbasis of $H$. Its high contribution is ${\sum }_{P_1}{\lambda }_j(1-p_j)\le 2E\mathrm{/}\eta$, because $\lambda \mathrm{/}(\lambda -a)\le 2\mathrm{/}\eta$ there. Its low contribution is at most $aL$, and its band contribution is at most $a(1+\eta {)}^2\mathrm{\parallel }{P}_{2}P-Q{\mathrm{\parallel }}_F^2\le 8aL$. Thus the sum is at most $11E\mathrm{/}\eta \le 77tK{F}^2\mathrm{/}\eta$. By [F3], $A(P_1+Q)$ is a permitted target. Finally $\mathrm{\parallel }A(M-P){\mathrm{\parallel }}_F\le \mathrm{\parallel }A{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\mathrm{\parallel }M-P{\mathrm{\parallel }}_F\le FtK$; the triangle inequality gives the result. The same block formulas cover empty high, band or low spaces, $k=0$, repeated eigenvalues, $\eta =1$, and both endpoint conventions.