CS: Heuristics for Rank Proxy and how it changes everything....

Work is steadily expanding from compressive sensing into low rank matrix decomposition and showing up on different approaches such as the ones dealing with time issues ( Low Rank and Compressive Imaging by Gonzalo Arce's group ) but they are not the only ones.  Recently, for instance, I mentioned the work on sub-wavelength imaging via quadratic compressive sensing at the Technion. Surely enough, this type of approach is really going beyond traditional signal processing and it requires us to learn new things.

As an aside, while the heuristics of the nuclear norm (replacing the rank functional) seems to have gotten a lot of interest in the recent algorithm development work, one should also remember that this is not the only one as shown in the recent Quadratic Compressive Sensing work and more pointedly in this 2003 paper entitled: Log-det heuristic for matrix rank minimization with applications to Hankel and Euclidean distance matrices by Maryam Fazell, Haitham Hindi, Stephen P. Boyd. I asked Yonina Eldar why they used the log-det heuristics (using CVX), and she responded that it worked better than the nuclear norm proxy. So as one can see, it looks like we are going to have a rich set of solvers in the next upcoming years, aren't we lucky, uh ? As it turns out, today we have four papers using nuclear norm heuristics to deal  with time dependent MRI and Computed Tomography. Enjoy!

An algorithm for sparse MRI reconstruction by Schatten p-norm minimization by Angshul Majumdar, Rabab K. Ward. The abstract reads:

In recent years, there has been a concerted effort to reduce the MR scan time. Signal processing research aims at reducing the scan time by acquiring less K-space data. The image is reconstructed from the subsampled K-space data by employing compressed sensing (CS)-based reconstruction techniques. In this article, we propose an alternative approach to CS-based reconstruction. The proposed approach exploits the rank deficiency of the MR images to reconstruct the image. This requires minimizing the rank of the image matrix subject to data constraints, which is unfortunately a nondeterministic polynomial time (NP) hard problem. Therefore we propose to replace the NP hard rank minimization problem by its nonconvex surrogate — Schatten p-norm minimization. The same approach can be used for denoising MR images as well. Since there is no algorithm to solve the Schatten p-norm minimization problem, we derive an efficient first-order algorithm. Experiments on MR brain scans show that the reconstruction and denoising accuracy from our method is at par with that of CS-based methods. Our proposed method is considerably faster than CS-based methods

Accelerating multi-echo T2 weighted MR imaging: Analysis prior group-sparse optimization by Angshul Majumdar, Rabab K. Ward. The abstract reads:

This works addresses the problem of reconstructing multi-echo T2 weighted MR images from partially sampled K-space data. Previous studies in reconstructing MR images from partial samples of the K-space used Compressed Sensing (CS) techniques to exploit the spatial correlation of the images (leading to sparsity in transform domain). Such techniques can be employed to reconstruct the individual T2 weighted images. However, in the current context, the different images are not independent; they are images of the same cross section, and hence are highly correlated. In this work, we not only exploit the spatial correlation within the image, but also the correlation between the images to achieve even better reconstruction results.

For individual MR images, CS based techniques lead to a sparsity promoting optimization problem in a transform domain. In this paper, we show how to extend the same framework in order to incorporate correlation between images leading to group sparsity promoting optimization. Group sparsity promoting optimization is popularly formulated as a synthesis prior problem. The synthesis prior formulation for group sparsity leads to superior reconstruction results compared to ordinary sparse reconstruction. However, in this paper we show that when group sparsity is framed as an analysis prior problem the reconstruction results are even better for proper choice of the sparsifying transform. An interesting observation of this work is that when the same sampling pattern is used to sample the K-space for all the T2 weighted echoes, group sparsity does not yield any noticeable improvement, but when different sampling patterns are used for different echoes, our proposed group sparsity promoting formulation yields significant improvement (in terms of Normalized Mean Squared Error) over previous CS based techniques.

Joint reconstruction of multiecho MR images using correlated sparsity by Angshul Majumdar, Rabab K. Ward. The abstract reads:

This works addresses the problem of reconstructing multiple T1- or T2-weighted images of the same anatomical cross section from partially sampled K-space data. Previous studies in reconstructing magnetic resonance (MR) images from partial samples of the K-space used compressed sensing (CS) techniques to exploit the spatial correlation of the images (leading to sparsity in wavelet domain). Such techniques can be employed to reconstruct the individual T1- or T2-weighted images. However, in the current context, the different images are not really independent; they are images of the same cross section and, hence, are highly correlated. We exploit the correlation between the images, along with the spatial correlation within the images to achieve better reconstruction results than exploiting spatial correlation only. For individual MR images, CS-based techniques lead to a sparsity-promoting optimization problem in the wavelet domain. In this article, we show that the same framework can be extended to incorporate correlation between images leading to group/row sparsity-promoting optimization. Algorithms for solving such optimization problems have already been developed in the CS literature. We show that significant improvement in reconstruction accuracy can be achieved by considering the correlation between different T1- and T2-weighted images. If the reconstruction accuracy is considered to be constant, our proposed group sparse formulation can yield the same result with 33% less K-space samples compared with simple sparsity-promoting reconstruction. Moreover, the reconstruction time by our proposed method is about two to four times less than the previous method.

Robust principle component analysis based four-dimensional computed tomography by Hao Gao, Jian-Feng Cai,  Zuowei Shen, and Hongkai Zhao. The abstract reads:

The purpose of this article for four-dimensional (4D) computed tomography (CT) is threefold. (1) A new spatiotemporal model is presented from matrix perspective with the row dimension in space and the column dimension in time, namely, Robust PCA based 4DCT model (Robust Principle Component Analysis based 4D CT). That is, instead of viewing the 4D object as a temporal collection of three-dimensional (3D) images and looking for local coherence in time or space independently, we perceive it as a mixture of low-rank matrix and sparse matrix to explore the maximum temporal coherence of spatial structure among phases. Here the low-rank matrix corresponds to the “background” or reference state, which is stationary over time or similar in structure; the sparse matrix stands for the “motion” or time-varying component, e.g., heart motion in cardiac imaging, which is often either approximately sparse itself or can be sparsified in the proper basis. Besides 4D CT, this Robust PCA based 4DCT model should be applicable in other imaging problems for motion reduction or/and change detection with the least amount of data, such as multi-energy CT, cardiac MRI, and hyperspectral imaging. (2) A dynamic strategy for data acquisition, i.e., a temporally spiral scheme, is proposed that can potentially maintain the similar reconstruction accuracy with much fewer projections of the data. The key point of this dynamic scheme is to reduce the total number of measurements and hence the radiation dose, by acquiring complementary data in different phases while reducing redundant measurements of the common background structure. (3) An accurate, efficient, yet simple-to-implement algorithm based on split Bregman method is developed for solving the model problem with the sparse representation in tight frames.