Faster Randomized Kaczmarz

Nick Freris sent me the following recently:

Dear Igor,

[After reading this entry] My friend Juri recommended contacting you to advertise a recent work on Randomized Kaczmarz (algorithms, analysis and applications). I am attaching the slides from a talk I gave at EPFL.

I hope you find this of interest, i will be more than excited to hear from you on this.

best regards,

Nick Freris

Thanks Nick. Of interest is the convergence speed that is tied to the sparsity of the overdetermined matrix. Let us recall that the Kaczmarz algorithm is the same as ART, an algorithm developed by Dick et al for the reconstruction of CT images. Hence it is interesting to find out an algorithm that is somewhat dependent on the sparsity of the measurement matrix which, in CT, happens to be an instantiation of the voxels being crossed by X-rays. In other words, this reconstruction algorithm does take into account the sparsity of the measurement process and one wonders how it could also take advantage of the sparsity of the solution (a feature of compressive sensing). Without further due, here is the presentation: Randomized Kaczmarz

other related papers of interest include: Randomized Extended Kaczmarz for Solving Least-Squares by Anastasios Zouzias, Nikolaos Freris

We present a randomized iterative algorithm that exponentially converges in expectation to the minimum Euclidean norm least squares solution of a given linear system of equations. The expected number of arithmetic operations required to obtain an estimate of given accuracy is proportional to the square condition number of the system multiplied by the number of non-zeros entries of the input matrix. The proposed algorithm is an extension of the randomized Kaczmarz method that was analyzed by Strohmer and Vershynin.

and Fast distributed smoothing for network clock synchronization by Nikolaos M. Freris and Anastasios Zouzias

Abstract— We consider the problem of estimating node variables from noisy relative measurements in a wireless network. In previous work, a distributed smoothing scheme was developed based on the Jacobi algorithm for obtaining leastsquares (LS) estimates. Although the synchronous version of the algorithm was shown to converge exponentially to the optimal estimate, an analysis of the asynchronous scheme is notably missing. In this paper, we design and analyze a new class of distributed asynchronous smoothing algorithms based on Randomized Kaczmarz (RK) algorithm for solving linear systems. One of the proposed schemes applies RK directly to the (generally inconsistent) noisy linear system, whereas the other one operates on the normal equations for LS estimation. We analyze the expected convergence rate of the proposed algorithms depending solely on properties of the network topology. Inspired by the analytical insights, we propose a distributed algorithm for synchronization, namely Randomized Kaczmarz Over-smoothing (RKO) which has demonstrated significant improvement over the state-of-art protocol in numerous experiments, in terms of both convergence speedup and energy savings.

All entries related to the Kaczmarz algorithm are here:

http://nuit-blanche.blogspot.com/search/label/Kaczmarz

also on interest:Sparse-Coding-Based Computed Tomography Image Reconstruction by Sang Min Yoon and Gang-Joon Yoon

Computed tomography (CT) is a popular type of medical imaging that generates images of the internal structure of an object based on projection scans of the object from several angles. There are numerous methods to reconstruct the original shape of the target object from scans, but they are still dependent on the number of angles and iterations. To overcome the drawbacks of iterative reconstruction approaches like the algebraic reconstruction technique (ART), while the recovery is slightly impacted from a random noise (small amount of norm error) and projection scans (small amount of norm error) as well, we propose a medical image reconstruction methodology using the properties of sparse coding. It is a very powerful matrix factorization method which each pixel point is represented as a linear combination of a small number of basis vectors.

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.