ModFKV low-rank approximation supplier

Set $t=\overline{ϵ}\mathrm{/}(1000K^2)$. Choose the integer $q=\lceil {10}^6{K}^4{\overline{ϵ}}^{-2}(1+\sqrt{2\log (2\mathrm{/}\delta )}{)}^2\rceil$. This has the asserted $\mathrm{\Theta }$ order, uniformly for $0<\delta <1$, and [F1] gives both Gram errors at most $t{F}^2$ except on an event of probability at most $\delta$. The algorithm's mixture probability equals $\mathrm{\parallel }{S}_{\ast ,j}{\mathrm{\parallel }}^2\mathrm{/}{F}^2$, so a zero-probability column is never drawn and its INVALID branch has probability zero.

Since $K\ge 1$, $\eta \le 1$ and $ϵ\le 1\mathrm{/}4$, $tK\le 1\mathrm{/}2$. On the event in step 1.1, [F2] applies to the actual strictly retained singular values and to $M=S^{T}U{\mathrm{\Sigma }}^{-2}{U}^{T}S$. It gives rank at most $K$ and a threshold-band target with error at most $F(tK+\sqrt{77tK\mathrm{/}\eta })\le F({ϵ}^2\mathrm{/}1000+ϵ\sqrt{77\mathrm{/}1000})\le ϵF$. Empty retention returns zero and is included in [F2]. No gap between actual singular values is assumed.

The $q$ row samples, $q$ mixture samples and the probabilities of the sampled columns can be obtained using at most $O(q^2)$ input queries: each mixture probability sums $q$ known row probabilities and queried squared entries. Forming $W$ uses $q^2$ entries; its exact-arithmetic SVD and the stored matrices require $O(q^3)$ arithmetic. These costs give the stated counts for the description and make no claim to materialize $A$, $S$ or $D$ in full.