Tuesday, January 21, 2014

Sparse Randomized Kaczmarz for Multiple Measurement Vectors - implementation -

The Kaczmarz algorithm is popular for iteratively solving an overdetermined system of linear equations. However the traditional Kaczmarz algorithm has a linear convergence rate,a randomized version of the Kaczmarz algorithm was shown to converge exponentially. Recently an algorithm for finding sparse solution to a linear system of equations has been proposed based on weighted randomized Kaczmarz algorithm. These algorithms solves single measurement vector problem; however there are applications were multiple-measurements are available. In this work, the objective is to solve a multiple measurement vector problem with common sparse support by modifying the randomized Kaczmarz algorithm. We have also modeled the problem of face recognition from video as the multiple measurement vector problem and solved using our proposed technique. We have compared the proposed algorithm with state-of-art spectral projected gradient algorithm for multiple measurement vectors on both real and synthetic datasets. The Monte Carlo simulations confirms that our proposed algorithm have better recovery and convergence rate than the MMV version of spectral projected gradient algorithm under fairness constraints.
I note from the paper:

The algorithm works for both over-determined and under-determined system of equations.

Isn't it time, we devise a universal phase transition diagram for MMV computations ? At least some people on the experimental side could see if it fits the best that can be achieved numerically.

The implementation is on Matlab Central

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: