4
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • $\begingroup$ 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." $\endgroup$ – Richard Mar 6 '18 at 14:48
  • $\begingroup$ Oh, perfect!! Looks like this paper actually justifies the answer I guessed above, essentially $K_{22}\approx K_{21}K_{11}^+K_{12}$. $\endgroup$ – Justin Solomon Mar 6 '18 at 15:52
  • $\begingroup$ It would help if you wrote explicitly in the question which properties you wish your approximation to have. $\endgroup$ – Federico Poloni Mar 6 '18 at 20:17
  • $\begingroup$ Isn't this just an application of Schur complement? $\endgroup$ – percusse Mar 6 '18 at 20:20
4
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ you're my hero! $\endgroup$ – Justin Solomon Mar 6 '18 at 18:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.