Around the time Curiosity landed on Mars, an Around the blogs in 80 summer hours pointed to Dick Lipton's blog's entry entitled A New Way To Solve Linear Equations where he mentioned a stunning preprint by Prasad Raghavendra. Yesterday, Riccardo Murri commented the following:
Benjamin Jonen and I have implemented some example code in Python for this solver; you can read the source files at:
There’s also an implementation of the algorithm as modified by Fliege (arXiv 1209.3995v1), which works over the reals, and some variants with which we are experimenting.
The second paper is: A Randomized Parallel Algorithm with Run Time $O(n^2)$ for Solving an $n \times n$ System of Linear Equations by Joerg Fliege. The abstract reads:
In this note, following suggestions by Tao, we extend the randomized algorithm for linear equations over prime fields by Raghavendra to a randomized algorithm for linear equations over the reals. We also show that the algorithm can be parallelized to solve a system of linear equations $A x = b$ with a regular $n \times n$ matrix $A$ in time $O(n^2)$, with probability one. Note that we do not assume that $A$ is symmetric.
Several comments here. This is the second time I see a preprint being borne out of a comment on a blog. I wonder how many there are. Second, while the randomized algorithm works for square matrices, I wonder if it still works out for short and fat matrices (underdetermined linear systems of equations) and how easy it is to have a solution from a certain family of vectors. In other words, does it still work if one chooses only vectors that are 5-sparse, that have a bernouilli distribution, I am sure y'all get my drift.
Image Credit: NASA/JPL-Caltech
This image was taken by Navcam: Right A (NAV_RIGHT_A) onboard NASA's Mars rover Curiosity on Sol 172 (2013-01-29 21:21:57 UTC) .
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.