Incremented Rank PowerFactorization algorithm - implementation-

Justin Haldar sent me the following:

Hi Igor, 

I just came across your Matrix Factorization Jungle website, and thought you might like to list the Incremented Rank PowerFactorization algorithm that Diego Hernando and I published about a while back:(Rank-Constrained Solutions to Linear Matrix Equations Using PowerFactorization )

It's a fast greedy algorithm that solves a rank-constrained version of the matrix recovery inverse problem, and empirically seems to have advantages over convex-relaxation approaches in a number of settings (previously mentioned on Nuit-Blanche:). It's also been used for sparsely-sampled medical imaging reconstruction problems: See:

• Low-rank approximations for dynamic imaging

• Spatiotemporal imaging with partially separable functions: A matrix recovery approach

• Low rank matrix recovery for real-time cardiac MRI

.....

Here is my response

Justin,

I am torn and you might help me in figuring this thing out.

You may have noticed that the Matrix Factorization Jungle only features implementations that people can download. It is just too difficult to keep track of any and all implementations that are eventually never available (for whatever reason). I would love to feature your solver. Is there anyway you could make something available even if it is at a prototype level (for a small dataset) ? I could then point to you for people who would want something with more strength.

Cheers,

Igor.

If you recall, I had a small rant about this a while back in Nobody Cares About You and Your Algorithm and the argument still stands. Help me help you become a rock star. Some people might not take the message kindly as it goes against some old habit of academia but Justin was not one of these people, he wrote back the next day the following:

Hi Igor,

With your encouragement, I've created a simple stripped-down Matlab implementation that people can download from here:

http://mr.usc.edu/download/irpf

Cheers,

--

Justin

Thanks Justin, it is now on the Matrix Factorization page! The IRPF page starts with:

Incremented Rank PowerFactorization: Sample Code 

This page provides sample code for a basic Matlab implementation of the Incremented Rank PowerFactorization (IRPF) algorithm.  IRPF is a fast greedy algorithm that solves a rank-constrained version of the matrix recovery problem:

The algorithm was originally described in:

J. P. Haldar, D. Hernando.  “Rank-Constrained Solutions to Linear Matrix Equations using PowerFactorization.” IEEE Signal Processing Letters 16:584-587, 2009.

[IEEE link] [PubMed Central link]

Slightly more detail about the algorithm can be found in Chapter 5 of:

J. P. Haldar.  “Constrained Imaging: Denoising and Sparse Sampling.” Ph.D. Dissertation, University of Illinois at Urbana-Champaign, May 2011.

[link]

The dissertation also includes application examples and additional references involving the use of IRPF in the context of spatiotemporal magnetic resonance image reconstruction.  The use of IRPF and related methods in medical imaging applications continues to grow (so keep watching the literature!).

A sample Matlab implementation of IRPF is available at the bottom of the page.  There are many ways to implement IRPF, and different implementations can be more or less efficient depending on the problem context.  This particular version uses the iterative conjugate-gradient algorithm for matrix inversion (rather than direct matrix inversion as was described in the original paper).  Some features of this iterative approach are briefly mentioned in a [conference paper] and in the Ph.D. dissertation referenced above. Other versions are available on request.

Sample results are provided below, which can be recreated using sample code provided alongside the IRPF implementation.

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.