Nystrom approximation of SVD for asymmetric matrices
An answer to this question on the Scientific Computing Stack Exchange.
Question
Suppose I have a symmetric matrix $K$. Subdivide $K$ into pieces as $$K=\begin{pmatrix} K_{11} & K_{12} \ K_{21} & K_{22}\end{pmatrix},$$ where $K_{21}=K_{12}^\top$. Then, the Nystrom approximation of $K$ replaces $K_{22}$ with the approximation $$K_{22}\approx K_{12}^\top K_{11}^{-1}K_{12}.$$ See e.g. this paper for an introduction.
Now, suppose $K$ is asymmetric. Here's my question: If we subdivide $K$ as above, does there exist a "Nystrom-style" approximation of $K_{22}$?
I'm OK with assuming $K_{11}$ is chosen to be square and invertible if that helps. It seems naively that I could use exactly the same formula when $K$ is not square, but of course the proof of the Nystrom approximation no longer holds; I assume an eigenvalue argument has to be replaced with an SVD.
Answer
Nemtsov, Averbuchm, and Schclar's "Matrix compression using the Nyström method" (2016) seems relevant:
The Nyström method is routinely used for out-of-sample extension of kernel matrices. We describe how this method can be applied to find the singular value decomposition (SVD) of general matrices and the eigenvalue decomposition (EVD) of square matrices. [...] Our algorithm is applicable to general matrices whereas previous methods focused on kernel matrices.
In particular, they show that a matrix
$$M= \begin{bmatrix} A_M & B_M \ F_M & C_M \end{bmatrix} $$
can be approximated as:
$$\hat M = \begin{bmatrix} A_M & B_M \ F_M & F_M A_M^+ B_M \end{bmatrix} $$
where $A_M^+$ denotes the pseudo-inverse of $A_M$.
Kumar and Schneider's seemingly thorough "Literature survey on low rank approximation of matrices" (2016) provides a handy bibliography of Nyström method error estimates, ensemble methods, and adaptive sampling techniques. The foregoing is the only paper it cites as applying Nyström to general matrices.