Julio A. Oscanoa^{1,2}, Frank Ong^{3}, Zhitao Li^{2,3}, Christopher M. Sandino^{3}, Daniel B. Ennis^{2,4}, Mert Pilanci^{3}, and Shreyas S. Vasanawala^{2}

^{1}Department of Bioengineering, Stanford University, Stanford, CA, United States, ^{2}Department of Radiology, Stanford University, Stanford, CA, United States, ^{3}Department of Electrical Engineering, Stanford University, Stanford, CA, United States, ^{4}Cardiovascular Institute, Stanford, CA, United States

Parallel imaging and compressed sensing reconstruction of large datasets has a high computational cost, especially for 3D non-Cartesian acquisitions. This work is motivated by the success of iterative Hessian sketching methods in machine learning. Herein, we develop Coil Sketching to lower computational burden by effectively reducing the number of coils actively used during iterative reconstruction. Tested with 2D radial and 3D cones acquisitions, our method yields considerably faster reconstructions (around 2x) with virtually no penalty on reconstruction accuracy.

A general approach to decrease computation time is to reduce the number of coils actively used during reconstruction. One class of methods is coil compression

We propose a reconstruction method, denoted Coil Sketching, that combines the best of both approaches. Our method is based on iterative Hessian sketching (IHS)

The general PICS reconstruction problem is:

$$ x^*= \text{argmin}_x \; f(x) := ||Ax-k||^2_2 + \lambda || Wx ||_1 \; \text{[Eq. 1]}$$

where $$$x$$$ represents the image, $$$A$$$ models the MR imaging process, $$$k$$$ is the acquired k-space, and $$$W$$$ is a sparsifying transform. Matrix $$$A$$$ has the following structure:

$$ A=UFC \; \text{[Eq. 2]}$$

where $$$C$$$ represents the voxel-wise multiplication by $$$c$$$ coil sensitivity maps, $$$F$$$ is the coil-wise FFT, and $$$U$$$ is the undersampling operator. The computational cost of solving Eq. 1 is linearly proportional to the number of coils $$$c$$$.

When applying IHS algorithms,

$$x^{t+1} = \text{argmin}_x \; \hat{f}(x) := || A^t_S(x - x^t) ||^2_2 - x^TA^T(k - Ax^t) + \lambda || Wx ||_1 \; \text{[Eq. 3]}$$

We propose a structured sketching matrix $$$S$$$, denoted Eigen-Sketching matrix, that effectively reduces the number of coils in the model matrix A. Similar to CC,

Concretely, multiplication by the proposed Eigen-Sketching matrix $$$S^t$$$ equivalently performs random linear combinations in the coil dimension. As $$$U$$$ and $$$F$$$ are coil-wise linear operations, sketching $$$A$$$ will be equivalent to directly sketching matrix $$$C$$$, which yields a $$$C^t_S$$$ operator with a reduced number $$$\hat{c} < c$$$ of sensitivity maps:

$$A^t_S = S^t = S^t (UFC) = UFC^t_S \; \text{[Eq. 4]}$$

Fig. 2 presents the algorithm pipeline. We empirically selected the number of virtual coils $$$\hat{c} < c$$$ that accumulated at least 80% of the total energy. First, to accelerate convergence, we perform an initialization that runs with the first $$$\hat{c}$$$ virtual coils. This process yields a fast yet inaccurate first estimate of $$$x$$$. Then, we apply our proposed Coil Sketching scheme to iteratively refine $$$x$$$. At each iteration, we calculate $$$A^t_s$$$, and solve Eq. 3. Both reconstructions with coil compression and Coil Sketching use model matrices that effectively work with $$$\hat{c}$$$ coils. Thus, the computational cost is linearly proportional to $$$\hat{c}$$$ instead of the number of coils $$$c$$$.

We tested our method with two retrospectively $$$R=2$$$ undersampled datasets:

- Liver 2D radial acquisition with tiny golden angle, 32 channel cardiac coil, $$$256/512$$$ readouts, image size (256x256)
- Abdominal 3D cones acquisition, 20 phases array torso coil, $$$21136/42272$$$ readouts, image size (297x297x112)

- Reconstruction with all coils
- Reconstruction with coil compression using only the first $$$\hat{c}$$$ virtual coils
- Coil Sketching with $$$\hat{c}$$$ coils ( $$$(\hat{c} - 1)$$$ virtual coils and 1 sketched coil)

1. Lustig, M., Donoho, D. and Pauly, J.M., 2007. Sparse MRI: The application of compressed sensing for rapid MR imaging. Magnetic Resonance in Medicine: An Official Journal of the International Society for Magnetic Resonance in Medicine, 58(6), pp.1182-1195.

2. King, K.F., 2008. Combining compressed sensing and parallel imaging. In Proceedings of the 16th annual meeting of ISMRM, Toronto (Vol. 1488, p. 44).

3. Vasanawala, S.S., Murphy, M.J., Alley, M.T., Lai, P., Keutzer, K., Pauly, J.M. and Lustig, M., 2011, March. Practical parallel imaging compressed sensing MRI: Summary of two years of experience in accelerating body MRI of pediatric patients. In 2011 IEEE international symposium on biomedical imaging: From nano to macro (pp. 1039-1043). IEEE.

4. Zhang, T., Pauly, J.M., Vasanawala, S.S. and Lustig, M., 2013. Coil compression for accelerated imaging with Cartesian sampling. Magnetic resonance in medicine, 69(2), pp.571-582.

5. Buehrer M, Pruessmann K, Boesiger P, Kozerke S. Array compression for MRI with large coil arrays. Magn Reson Med 2007;57:1131–1139.

6. Huang F, Vijayakumar S, Li Y, Hertel S, Duensing G. A software channel compression technique for faster reconstruction with many channels. Magn Reson Imaging 2008;26:133–141.

7. King S, Varosi S, Duensing G. Optimum SNR data compression in hardware using an eigencoil array. Magn Reson Med 2010;63:1346–1356.8.

8. Muckley MJ, Noll DC, Fessler JA. Accelerating SENSE-type MR image reconstruction algorithms with incremental gradients. In: Proceedings of the ISMRM 22nd Annual Meeting, Milan, Italy; March 2014:4400.9.

9. Ong, F., Zhu, X., Cheng, J.Y., Johnson, K.M., Larson, P.E., Vasanawala, S.S. and Lustig, M., 2020. Extreme MRI: Large‐scale volumetric dynamic imaging from continuous non‐gated acquisitions. Magnetic Resonance in Medicine.

10. Pilanci, M. and Wainwright, M. J. Iterative hessian sketch: Fast and accurate solution approximation for constrained least-squares. Journal of Machine Learning Research, 17(53):1–38, 2016.

11. Tang, J., Golbabaee, M. and Davies, M.E., 2017, July. Gradient projection iterative sketch for large-scale constrained least-squares. In International Conference on Machine Learning (pp. 3377-3386). PMLR.

12.Charikar, M., Chen, K. and Farach-Colton, M., 2004. Finding frequent items in data streams. Theoretical Computer Science, 312(1), pp.3-15.

13. Clarkson, K.L. and Woodruff, D.P., 2017. Low-rank approximation and regression in input sparsity time. Journal of the ACM (JACM), 63(6), pp.1-45.

14. Pham, N. and Pagh, R., 2013, August. Fast and scalable polynomial kernels via explicit feature maps. In Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 239-247).

15. Ying, L., & Sheng, J. (2007). Joint image reconstruction and sensitivity estimation in SENSE (JSENSE). Magnetic Resonance in Medicine, 57(6), 1196-1202.