ista_simple

// Note: `@` refers to matrix-matrix or matrix-vector multiplication.  `*` refers to elementwise multiplication.

degrees = // vector s.t. degree[i] is the degree of the i'th node in graph G
D       = // diagonal matrix s.t. D[i, i] = degrees[i]
D_inv   = // diagonal matrix s.t. D_inv[i, i] = 1 / sqrt(degrees[i])
q       = // zero matrix of shape (max_iters, num_nodes)

grad = -alpha * D_inv @ s

while k < max_iters do
    for i in num_nodes do
        rad = rho * alpha * sqrt(degrees[i])
        
                      | q[k,i] - (grad[i] + rad) if q[k,i] - grad[i] >= rad
        q[k + 1, i] = | 0                        if -rad < q[k,i] - grad[i] < rad
                      | q[k,i] - (grad[i] - rad) if q[k,i] - grad[i] <= -rad
        
    end for
    grad = D_inv @ (D - (1 - alpha) / 2 * (D + A)) @ D_inv @ q[k + 1] - alpha * D_inv @ s
    k = k + 1
end while

return sqrt(D) @ q[k]

@martinferreira --

• If you're running ISTA for a single seed node, s is a vector of length # of nodes in graph
• So, grad = -alpha * D_inv @ s is a scalar * matrix * vector product, which makes it a vector

Seems like line 18 should be outside the for loop if you compare it with the alghorithm

@martinferreira, yes I think that's right, fixed the gist.

(1 / alpha) should be (1 - alpha) took me a while to figure it out. but i did

the last line should be return sqrt(D) @ q[k]

@martinferreira @W-KE — good catches, updated