# Nystrom approximation of SVD for asymmetric matrices

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.

• Possibly useful: Matrix Compression using the Nystrom Method: "The Nystrom 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." Mar 6, 2018 at 14:48
• Oh, perfect!! Looks like this paper actually justifies the answer I guessed above, essentially $K_{22}\approx K_{21}K_{11}^+K_{12}$. Mar 6, 2018 at 15:52
• It would help if you wrote explicitly in the question which properties you wish your approximation to have. Mar 6, 2018 at 20:17
• Isn't this just an application of Schur complement? Mar 6, 2018 at 20:20

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.

• you're my hero! Mar 6, 2018 at 18:08