ModFKV low-rank description procedure

Inputs: a nonzero real matrix $A\in {\mathbb{R}}^{m\times n}$ with the exact row/column ℓ2 sample/query interface of ℓ2 sample/query access to vectors and matrices, a threshold $0<\sigma \le \mathrm{\parallel }A{\mathrm{\parallel }}_F$, tolerances $0<ϵ\le 1$ and $0<\eta \le 1$, and an integer sample count $q\ge 1$. The procedure returns a compact description; it does not write all $mn$ entries of the output matrix.

1. Sample $i_1,\dots ,i_q$ independently from the row distribution $D_A$. Form the conceptual matrix $S\in {\mathbb{R}}^{q\times n}$ whose $r$th row is $A_{i_r,\ast }\mathrm{/}\sqrt{q{D}_A(i_r)}$. The entries of $S$ can be queried through the stored row indices; no zero-probability row is selected.
2. Define a column distribution $F$ by choosing $r$ uniformly in $[q]$ and then sampling a column from $D_{S_{r,\ast }}$. Draw $j_1,\dots ,j_q$ independently from $F$. Form $W\in {\mathbb{R}}^{q\times q}$ with $W_{r,c}=S_{r,j_c}\mathrm{/}\sqrt{qF(j_c)}$. A sampled column has $F(j_c)>0$; otherwise return INVALID.
3. Compute a singular value decomposition of $W$. Retain the left singular vectors $u^{(1)},\dots ,u^{(k)}$ whose singular values ${\widehat{\sigma }}_1,\dots ,{\widehat{\sigma }}_k$ are strictly greater than $\sigma$, and set $\widehat{U}=[u^{(1)}\cdots u^{(k)}]$ and $\widehat{\mathrm{\Sigma }}=\mathrm{diag}({\widehat{\sigma }}_1,\dots ,{\widehat{\sigma }}_k)$. If $k=0$, return the zero matrix description. Otherwise return the row indices and the matrices needed to evaluate $D:=A{S}^T\widehat{U}{\widehat{\mathrm{\Sigma }}}^{-2}{\widehat{U}}^{T}S\mathrm{.}$

The sample count $q$, matrix-entry and norm queries, sample operations, arithmetic, SVD, storage, and any finite-precision implementation are charged in the declared access model. Correctness, success probability, approximation error, and the parameter-dependent choice of $q$ are separate claims of ModFKV low-rank approximation supplier.