Householder QR Factorization: Adding Randomization for Column Pivoting

Getting to the core of linear algebra with randomized techniques, woohoo !  

Householder QR Factorization: Adding Randomization for Column Pivoting. FLAME Working Note #78  by Per-Gunnar Martinsson, Gregorio Quintana-Orti, Nathan Heavner, Robert van de Geijn

A fundamental problem when adding column pivoting to the Householder QR factorization is that only about half of the computation can be cast in terms of high performing matrix-matrix multiplication, which greatly limits the benefits of so-called blocked algorithms. This paper describes a technique for selecting groups of pivot vectors by means of randomized projections. It is demonstrated that the asymptotic flop count for the proposed method is 2mn2−(2/3)n3 for an m×n matrix with m≥n, identical to that of the best classical Householder QR factorization (with or without pivoting). Experiments demonstrate improvements in speed of substantial integer factors (between a factor of 3 and 5) relative to LAPACK's geqp3 implementation on a modern CPU.

Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page 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.