Nystrom Approximation Step

Problem

Compute the Nystrom low-rank approximation of a kernel matrix K using the selected column indices cols (assume exactly two columns):

K_approx = C * inv(W) * C^T

where C = K[:, cols] and W = K[cols, :][:, cols].

Hint

Nystrom sampling trades accuracy for speed by inverting only a small submatrix of K.

case 1

in: [[[1,0,0],[0,1,0],[0,0,1]],[0,1]]

expected: [[1,0,0],[0,1,0],[0,0,0]]

case 2

in: [[[1,0.5,0.2],[0.5,1,0.3],[0.2,0.3,1]],[0,1]]

expected: [[1,0.5,0.2],[0.5,1,0.3],[0.2,0.3,0.09333333333333331]]

case 3

in: [[[2,1,0],[1,2,1],[0,1,2]],[1,2]]

expected: [[0.6666666666666666,1,0],[1,2,1],[0,1,2]]

case 4

in: [[[1,0],[0,1]],[0,1]]

expected: [[1,0],[0,1]]

Starter codePython

def nystrom_approximation(K, cols):
    # Your code here
    pass

4 test cases · run your code against them in the editor