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:eqn2984The 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.

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.

Sample Code Output

Problem Setup

The IRPF algorithm was used to reconstruct the following 512×512, rank-10 matrix from different kinds of sparsely-sampled data.sample_code_01

Matrix Completion Example

In the first example, we consider a standard matrix completion problem where we directly measured 15% of the entries of this matrix, and perturbed these measurements with additive white Gaussian noise. IRPF was used to reconstruct a data-consistent matrix with rank at most 10, yielding the following results (after roughly 14 seconds of computation on our PC):sample_code_02

Random Convolution Example

In the second example, we consider a more complicated data acquisition operator, in which the matrix is circularly convolved with a randomly-generated complex-valued kernel. Subsequently, 7.5% of the entries of the resulting matrix were sampled at random and perturbed by complex additive white Gaussian noise.  IRPF was used to reconstruct a data-consistent matrix with rank at most 10, yielding the following results (after roughly 4 minutes of computation on our PC):



    This code is licensed under the CC Attribution-Noncommercial-Share Alike 3.0 License. Please cite at least the main IRPF reference (and the related references if appropriate) if you use this code or its derivatives in your own work.

    In no event shall the University of Southern California, the Authors, or the Distributors be liable to any party for direct, indirect, special, incidental, or consequential damages, including lost profits, arising out of the use of this software, its documentation, or any derivatives thereof, even if the authors have been advised of the possibility of such damage. The University of Southern California, the Authors, and the Distributors specifically disclaim any warranties, including, but not limited to, the implied warranties of merchantability, fitness for a particular purpose, and non-infringement. This software is provided on an "as is" basis, and the authors and distributors have no obligation to provide maintenance, support, updates, enhancements, or modifications. This software is for research purposes only and has not been approved for clinical use.

    Your Name (required)

    Your Email (required)

    Your Institution (required)

    Pressing the "Send" button below will indicate your acceptance of the license agreement. After clicking "Send," you will receive an e-mail with a personal download link.