Carlos Castillo-Passi^{1,2}, Claudia Prieto^{1,2,3}, Gabriel Varela-Mattatall^{1,2}, Carlos Sing-Long^{2,4,5}, and Pablo Irarrazaval^{1,2,5}

Under-sampling acquisition is oftenly used to reduce the scan time. Compressed Sensing allows the reconstruction of these data by solving a convex optimization problem. This is done to exploit the sparsity of the signals using the ℓ1-norm. We propose to use the Gini Index as a sparsity measure. In this work we demonstrate that this index allow to further increase the under-sampling factor. Interestingly this non-linear index can be computed by solving iteratively reweighted ℓ1 problems, without excessive computational load.

Faster imaging is achieved by under-sampling the acquisition in $$$k$$$-space. Images can be recovered assuming sparsity by a Compressed Sensing^{1,2} reconstruction which can be expressed as^{3,4}$$ \min_{\vec{x}\in\mathbb{C}^{N}}\quad\,\left\Vert \vec{x}\right\Vert _{1}\quad\quad\quad[1]\\s.t.\quad\left\Vert \Phi\Psi\vec{x}-\vec{y}\right\Vert _{2}\leq\epsilon,$$with $$$ \Psi\in\mathbb{C}^{N\times N}$$$ the basis of a dictionary, $$$ \Phi\in\mathbb{C}^{M\times N}$$$ the matrix to represent the measure domain and $$$ \vec{y}\in\mathbb{C}^{M}$$$ the acquired data. Using the ℓ1-norm is a practical way to measure sparsity, we propose to use another that satisfies desirable properties to measure sparsity^{5 }and also is affordable computationally. The Gini Index (GI)^{6,7} is a measure that has all the desirable properties^{5}. Furthermore, a simple formulation can be achieved if a sorting operation is performed beforehand. Thus, if $$$ \left|x_{\left[1\right]}\right|\leq\left|x_{\left[2\right]}\right|\leq\dots\leq\left|x_{\left[N\right]}\right|$$$ then we can represent the GI as a weighted ℓ1^{8}$$\mathrm{GI}\left(\vec{x}\right) =1-2\sum_{n=1}^{N}\underbrace{\left(\frac{N-n+\frac{1}{2}}{N}\right)}_{w_{n}}\frac{\left|x_{\left[n\right]}\right|}{\left\Vert \vec{x}\right\Vert _{1}}\\ =1-2\left\Vert \frac{\vec{w}^{\mathrm{T}}}{\left\Vert \vec{x}\right\Vert _{1}}\cdot\left(\mathcal{P}\vec{x}\right)\right\Vert _{1}\\ =1-2\left\Vert \vec{W}_{\vec{x}}^{\mathrm{T}}\cdot\vec{x}\right\Vert _{1}\quad\,\,[2],$$Where $$$ \mathcal{P}$$$ is a permutation matrix that represent the sorting unitary operator and $$$ \vec{W}_{\vec{x}}=\mathcal{P}^{\mathrm{T}}\vec{w}/\left\Vert \vec{x}\right\Vert _{1}$$$. Because of this, the use in inverse problems has been explored by replacing the ℓ1-norm by the weighted ℓ1^{9}.

The GI is a good sparsity measure that satisfies many desirable properties^{5}. The proposed method performed well in the numerical phantom with less or equal NMRSE than the ℓ1-norm even achieving perfect reconstruction at higher USFs, replicating already existing studies^{7,9}. The in-vivo results are also better, although not significant for the particular case we tested. In summary, the GI improves the reconstruction for under-sampled acquisitions and we believe it must be further explored for MRI reconstruction or other ℓ1-based problems.

1. Lustig M, Donoho D, Pauly JM. Sparse MRI: The application of compressed sensing for rapid MR imaging. Magnetic Resonance in Medicine 2007; 58:1182–1195.

2. Candès EJ, Wakin MB. An Introduction To Compressive Sampling. IEEE Signal Processing Magazine 2008;25:21–30.

3. Candès EJ, Romberg J, Tao T. Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Transactions on Information Theory 2006; 52:489–509.

4. Candès EJ, Romberg JK, Tao T. Stable signal recovery from incomplete and inaccurate measurements. Communications on Pure and Applied Mathematics 2006;59:1207–1223.

5. Hurley N, Rickard S. Comparing Measures of Sparsity. IEEE Transactions on Information Theory 2009;55:4723–4741.

6. Damgaard C, Weiner J. Describing Inequality in Plant Size or Fecundity. Ecology 2000; 81:1139–1142.

7. Zonoobi D, Kassim AA, Venkatesh YV. Gini Index as Sparsity Measure for Signal Reconstruction from Compressive Samples. IEEE Journal of Selected Topics in Signal Processing 2011; 5:927–932.

8. Huang XL, Shi L, Yan M. Nonconvex sorted ℓ1 minimization for sparse approximation. Journal of the Operations Research Society of China 2015; 3:207–229.

9. Feng C, Xiao L, Wei ZH. Compressive Sensing Inverse Synthetic Aperture Radar Imaging Based on Gini Index Regularization. International Journal of Automation and Computing 2014; 11:441–448.

10. Ochs P, Dosovitskiy A, Brox T, Pock T. On iteratively reweighted algorithms for nonsmooth nonconvex optimization in computer vision. SIAM Journal on Imaging Sciences 2015; 8:331–372.

11. Candès EJ, Wakin MB, Boyd SP. Enhancing Sparsity by Reweighted l1 Minimization. Journal of Fourier Analysis and Applications 2008; 14:877–905.

12. Bogdan M, van den Berg E, Sabatti C, Su W, Candès EJ. Slope adaptive variable selection via convex optimization. The annals of applied statistics 2015; 9:1103–1140.

13. van den Berg E, Friedlander MP. SPGL1: A solver for large-scale sparse reconstruction, June 2007,http://www.cs.ubc.ca/labs/scl/spgl1.

14. van den Berg E, Friedlander M. Probing the Pareto Frontier for Basis Pursuit Solutions. SIAM Journal on Scientific Computing 2008; 31:890–912.

Figure 1: Comparison in phantom between L1 and GI sparsity measures at different Under Sampling Factors (USFs) and SNRs. The results suggest that the GI gives greater or equal performance at SNRs higher than 10 db.

Figure 2: Phantom (zoom) with an USF of 5.5 and noise-free. The GI is capable of achieving perfect reconstruction at higher USFs than the L1 norm.

Figure 3: Brain (zoom) with USF of 4.5 at SNR≈ 16 dB.