Matthew J. Muckley^{1}, Jeffrey A. Fessler^{2}, and Marcelo V. W. Zibetti^{1}

Iterative reconstruction algorithms for non-Cartesian MRI can have slow convergence due to the nonuniform density of k-space samples. Convergence speed can be improved by including the density compensation function into the algorithm, but current techniques for doing so can lead to SNR penalties or algorithm divergence. Here, we combine the use of density compensation with a line search under the MFISTA framework. The method has the convergence guarantees of MFISTA while gaining the speed improvements of using the density compensition function. The algorithm generalizes further to any FISTA algorithm.

Combining non-Cartesian trajectories with sparsity-promoting regularization can significantly accelerate MRI scans. To estimate images from these scans, we solve the following optimization problem:

$$\hat{x}=\underset{x}{argmin}\frac{1}{2}\left\|y-Ax\right\|_2^2+\beta\left\|Rx\right\|_1,$$

where $$$x$$$ is the image, $$$A$$$ is a non-Cartesian system matrix (with sensitivity coils), $$$y$$$ is the k-space data, and $$$R$$$ is a sparsifying transform. FISTA is a popular algorithm for such problems. Generally, FISTA-like algorithms solve at iteration $$$k$$$ the following problem:

$$x^{k+1}=\underset{x}{argmin}\frac{1}{2}\left\|x-b^k\right\|_{M_f}^2+\beta\left\|Rx\right\|_1,$$

where $$$M_f \succeq A'A$$$ is a majorizing matrix and $$$b^k=z^k-M_f^{-1}g^k$$$ comes from the data-fitting part. $$$g^k=A'(Az^k-y)$$$ is the data-fitting gradient at the shifted point $$$z^k=x^k+(t^k-1/t^{k+1})(x^k-x^{k-1})$$$. Typically, FISTA uses $$$M_f=LI$$$, where $$$L$$$ is the maximum eigenvalue of $$$A'A$$$, but other more general matrices are possible. Step sizes for the algorithm are related to $$$M_f^{-1}$$$. In some iterations - particularly early iterations - the $$$M_f^{-1}$$$ step size is conservative, and it is possible to take larger steps, which we will do using a line search. We propose to change the gradient step to

$$b^{k}=z^k-\alpha^kM_f^{-1}g^k,$$

where

$$\alpha^k=\frac{\text{real}\left \{\left< M_f^{-1}g^k,g^k\right >\right \}}{\left\|AM_f^{-1}g^k\right\|_2^2}.$$

This is equivalent to applying a steepest descent line search routine to the $$$M_f^{-1}g^k$$$ search direction for the data-fitting part of the cost function. The denoising subproblem shown above that incorporates the properties of the regularizer can also be accelerated based on $$$\alpha$$$.^{5} Applying this line search can allow the algorithm to take a larger or smaller step, depending on the iteration. We can guarantee convergence of the proposed method by evaluating the cost function at $$$x^k$$$ and guaranteeing monotonicity as in MFISTA.^{6} This can be accomplished with minimal computation by storing a few extra variables in memory.^{7}

We applied the new line search procedure to non-Cartesian image reconstruction with a MOCHA approximate majorizer.^{5} The MOCHA procedure builds a circulant $$$M_f$$$ that is designed to mimic the properties of the density compensation function to speed convergence, but it does not guarantee the FISTA condition of $$$M_f \succeq A'A$$$. The line search helps the algorithm take smaller steps in cases where $$$M_f \succeq A'A$$$ is not satisfied, and we can also guarantee convergence due to the MFISTA cost function checks.

We applied the new algorithm to a 50-spoke radial brain MRI data set with 4 sensitivity coils.^{8}

We tested three algorithms in our numerical experiments. FISTA^{4,6} used $$$M_f=LI$$$, where $$$L$$$ is the Lipschitz constant. MOCHA^{5} used a circulant $$$M_f$$$ designed to emulate the density compensation function. LS-MOCHA is the standard MOCHA with the proposed line search improvements.

Figure 1 shows the images after 5 iterations of each algorithm. FISTA is further from convergence because it doesn't incorporate the k-space sampling density, while MOCHA and LS-MOCHA are closer to convergence due to the circulant majorizer. Figure 2 shows images after 150 iterations of each algorithm. By this point FISTA and LS-MOCHA are qualitatively similar. We do not show MOCHA since MOCHA diverged before reaching this point. Figure 3 shows a convergence plot of the normalized residual,

$$\xi(k)=\frac{\left \|x^k-x^{\infty}\right \|}{\left \|x^{\infty}\right \|},$$

where $$$x^{\infty}$$$ is estimated by running many thousands of iterations of FISTA. After 20 seconds, MOCHA diverges since it failed to design $$$M_f$$$ such that $$$M_f \succeq A'A$$$ for this data set. LS-MOCHA is the fastest method. The results in Figure 3 are confirmed by cost function plots in Figure 4.

We would like to thank K. T. Block et al. for publishing the data used in this abstract.

The authors would like to thank A. R. De Pierro and G. T. Herman for discussions on line search methods.

The authors would also like to thank NIH R01 EB023618 and NIH U01 EB018760 for funding that supported this work.

1. B. P. Sutton, D. C. Noll, & J.A. Fessler. "Fast, iterative image reconstruction for MRI in the presence of field inhomogeneities," *IEEE Trans. Med. Imag.*, vol. 22, pp. 178-188, 2003.

2. B. Mailhe, Q. Wang, R. Grimm, M. D. Nickel, K. T. Block, H. Chandarana, and M. S. Nadar. "Density compensation for iterative reconstruction from under-sampled radial data," in *Proc. Int. Soc. Magn. Res. Med.*, 2015.

3. S. Ramani & J. A. Fessler. "Parallel MR image reconstruction using augmented Lagrangian methods," *IEEE Trans. Med. Imag.*, vol. 30, pp. 694-706, 2011.

4. A. Beck & M. Teboulle. "A fast iterative shrinkage-thresholding algorithm for linear inverse problems," SIAM Jour. Imag. Sci., vol. 2, pp. 183-202, 2009.

5. M. J. Muckley, D. C. Noll, and J. A. Fessler, “Fast, iterative subsampled spiral reconstruction via circulant majorizers,” in *Proc. Int. Soc. Magn. Res. Med.*, 2016.

6. A. Beck & M. Teboulle. "Fast gradient-based algorithms for constrained total variation image denoising and deblurring problems," *IEEE Trans. Imag. Proc.*, vol. 18, pp. 2419-2434, 2009.

7. M. V. Zibetti, E. S. Helou, & D. R. Pipa. "Accelerating Overrelaxed and Monotone Fast Iterative Shrinkage-Thresholding Algorithms With Line Search for Sparse Reconstructions," *IEEE Trans. Imag.* Proc., vol. 26, pp. 3569-3578, 2017.

8. K. T. Block, M. Uecker, & J. Frahm. "Undersampled radial MRI with multiple coils. Iterative image reconstruction using a total variation constraint," *Magn. Res. Med.*, vol. 57, pp. 1086-1098, 2007.

Estimates of the image after five iterations. The MOCHA and LS-MOCHA methods are able to estimate broad image features with significant sharpening due to the circulant majorizer, while FISTA is still blurry since it is converging slower because it does not have any preconditioner related to the nonuniform k-space sampling density.

Estimates of the image after 150 iterations. The LS-MOCHA and FISTA methods are qualitatively similar, although LS-MOCHA has a lower cost function value. No MOCHA image is displayed since MOCHA diverged before reaching 150 iterations.

Plot showing convergence speed of the three algorithms as a function of time. The plot measures $$$\xi(k)$$$, which is the log-scaled, normalized residual to convergence. All three algorithms are similar in very early convergence, with LS-MOCHA being the fastest. MOCHA begins to diverge around 20 seconds of computation time, and its final output is far from the true minimum. LS-MOCHA remains ahead of both other methods despite the time needed to compute its line search.

Plot showing convergence speed of the three algorithms as a function of time. The plot measures the log-scaled cost function. All three algorithms are similar in very early convergence, with LS-MOCHA being the fastest. All algorithms reach a steady cost function state fairly early on, although MOCHA eventually diverges (seen in Figure 3, cut off in these figures).