Friday, April 12, 2013

A Q&A with Nikolaos Freris and Anastasios Zouzias: Randomized Extended Kaczmarz - implementation -

Following up on this recent Faster Randomized Kaczmarz entry, I asked Nick Freris the following:


I forgot to ask you. in the initial email, your friend had read about this blog entry ( ) where I noted:
On Andrew Davison's feed, Andrew talks about a new paper solving graph laplacians, I noted that a new algorithm for computing graph laplacians was shown to be a randomized instance of the Kaczmarz algorithm (see section 9, A Simple, Combinatorial Algorithm for Solving SDD Systems in Nearly-Linear Time by Jonathan A. KelnerLorenzo OrecchiaAaron SidfordZeyuan Allen Zhu)

How does your approach compare to the algorithm of Kelner et al if it is at all comparable ?



Nick Freris kindly responded:

Dear Igor,
....The original title of our journal paper was meant to be: "Randomized Kaczmarz for Laplacian systems," so indeed our work is very related. We leverage the special structure of Laplacian to design fast distributed (parallelizable) algorithms for estimation based on measuring differences across edges. I am also copying my co-author, Tasos Zouzias in case you have any further questions about our work.

Thanks once more on your interest.


Then Anastasios (Tassos) added: 

Dear Igor,

Let me add a few comments on your question which may be helpful. Please let me know if you have any further questions.

The main difference of the paper that you mentioned and ours [1,2] is on the model of computation. Kelner et al.'s algorithm works on the usual model of computation (unit-cost RAM) whereas ours works on the distributed model of computation (gossip model).

First of all, I am not familiar with the work of Kelner et al. It looks very interesting and as far as I can tell their algorithm is an instantiation of the (randomized) Kaczmarz method on a *preconditioned* Laplacian system. Computing the preconditioned matrix is not a trivial task (see also Spielman Teng paper). The goal in this area is to get algorithms that work in time O(nnz(L) polylog(n)) where nnz(L) is the number of non-zero entries of the Laplacian and that are "simpler" than Spielman-Teng's solver.

On the other hand, in our case the problem is to design asynchronous distributed algorithms that solve Laplacian systems. More precisely, the problem is to solve Laplacian systems in the gossip model of computation (see [2] for details). In [1,2], the expected number of iterations / rounds of the algorithm depends on the condition number of the Laplacian matrix (~ 1/lambda_2(G)). If you view these distributed algorithms as centralized (for comparison purposes), then the running time here is roughly O(nnz(L) kappa^2(L) ), where kappa^2(L) is the squared condition number of L (which can be arbitrarily large as opposed to Kelnel's et al paper / Spielman-Teng).
We also have an implementation of the Randomized Extended Kaczmarz method under 
which we used in our paper . I am not familiar with the GraphLab framework, so I can not answer your second question. 


Thanks Nick and Tassos ! Looks like this algorithm is ripe for an implementation in the GraphLab framework. Danny just wrote a small entry on the upcoming The GraphLab Workshop and Why Should You Care?

 Image credit: NASA/JPL-Caltech/Univ. of Arizona, This set of images shows what might be hardware from the Soviet Union's 1971 Mars 3 lander, seen in a pair of images from the High Resolution Imaging Science Experiment (HiRISE) camera on NASA's Mars Reconnaissance Orbiter.

Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

No comments: