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