Coil Sketching for fast and memory-efficient iterative reconstruction
Julio A. Oscanoa1,2, Frank Ong3, Zhitao Li2,3, Christopher M. Sandino3, Daniel B. Ennis2,4, Mert Pilanci3, and Shreyas S. Vasanawala2
1Department of Bioengineering, Stanford University, Stanford, CA, United States, 2Department of Radiology, Stanford University, Stanford, CA, United States, 3Department of Electrical Engineering, Stanford University, Stanford, CA, United States, 4Cardiovascular 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.


Parallel imaging and compressed sensing (PICS) reconstruction can substantially reduce acquisition times.1-3 However, long computation time in iterative reconstruction remains a bottleneck for clinical deployment, especially in 3D non-Cartesian acquisitions.

A general approach to decrease computation time is to reduce the number of coils actively used during reconstruction. One class of methods is coil compression4-7(CC) which linearly combines multi-channel data prior to reconstruction. While effective for Cartesian imaging, coil compression inherently loses signal energy, which often results in shading artifacts for non-Cartesian imaging. Another approach8,9 uses the stochastic gradient method, which randomly selects subsets of coil channels for each iteration in reconstruction. While fully leveraging all data, it often requires many iterations for convergence.

We propose a reconstruction method, denoted Coil Sketching, that combines the best of both approaches. Our method is based on iterative Hessian sketching (IHS)10 algorithms, which were recently proposed to obtain accurate solutions for large-scale machine learning.10,11 The basic idea is to iteratively use a randomly generated sketching matrix to project the problem onto a low dimensional space. Then, the smaller problem can be solved faster and with small memory footprint. To adapt to MR reconstruction, we design a structured sketching matrix that preserves the Fourier structure and leverages previous work on coil compression. Tested with 2D radial and 3D cones acquisitions, our method yields considerably faster reconstructions with virtually no penalty on reconstruction accuracy.


PICS reconstruction
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$$$.

Iterative Hessian Sketching
When applying IHS algorithms,10,11 we do not solve directly Eq. 1. Instead, we iterate solving lower-dimensional versions with sketched model matrices $$$A^t_S=S^tA$$$, where $$$S^t$$$ is the randomly generated sketching matrix at iteration $$$t$$$ . For L1-regularized problems, at each iteration, the next estimate $$$x^t$$$ is:
$$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]}$$
Structured sketching matrix S
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,4-7 this matrix considers the high-energy virtual coils, which are extracted from principal components of multi-channel k-space. But unlike CC, the matrix also considers random linear combinations of the remaining low-energy coils. Fig. 1 provides an illustration. This design has two main features: (1) the matrix preserves the Fourier structure and (2) it is adaptive to multi-channel signal energy.
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]}$$


Algorithm pipeline
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)
We calculated the sensitivity maps with JSENSE15 and reconstructed the images using a NVIDIA Titan RTX (24 GB) and L1 Wavelets PICS with:

  1. Reconstruction with all coils
  2. Reconstruction with coil compression using only the first $$$\hat{c}$$$ virtual coils
  3. Coil Sketching with $$$\hat{c}$$$ coils ( $$$(\hat{c} - 1)$$$ virtual coils and 1 sketched coil)
We compared the convergence of the objective function $$$f(x)$$$ and the image quality.


Reconstructions with coil compression and Coil Sketching run considerably faster ($$$\approx 2$$$x) than reconstruction using all coils (Fig. 3). However, reconstruction with coil compression converges to a suboptimal value, whereas the proposed method attains the optimal value. This suboptimality is manifested as significant lower image quality (Fig. 4) and noticeable shading artifacts in the 3D acquisition (Fig. 5).

Conclusion & Discussion

Coil Sketching allows faster reconstruction and improved memory-efficiency, by effectively using fewer sensitivity maps and, therefore, less Fourier transform per iteration. This reduced computational cost could enable reconstruction of larger datasets with higher resolution and dimensionality.


This project was supported by NIH R01 EB026136 and NIH R01 EB009690.


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.


Figure 1. Structure of Eigen-Sketching matrix $$$S^t$$$. Effectively, matrix $$$S^t$$$ sketches the sensitivity map operator $$$C$$$, yielding a reduced sensitivity map operator $$$C^t_S$$$ with less coils. Similar to coil compression4-7(CC) the Eigen-Sketching matrix considers the high-energy virtual coils; but unlike CC, the matrix also considers a sketched coil. This sketched coil is formed by multiplying the remaining coils by “-1” or “+1” with probability 50% each and then summing them together. In sketching literature, this scheme is denoted as CountSketch.10-12

Figure 2. Coil Sketching Algorithm. (A) The algorithm has three main steps: (1) Coil compression, where we estimate the virtual coils; (2) Initialization, where we perform an initial reconstruction with $$$\hat{c}$$$ virtual coils, and (3) Coil Sketching, where we iteratively refine our estimate using the Eigen-Sketched sensitivity maps. (B) shows the algorithm pipeline. Both in (2) and (3) we are effectively working with $$$\hat{c} < c$$$ coils.

Figure 3. Cost Function convergence for (A, B) 2D Radial and (C, D) 3D Cones Acquisition. Reconstructions with coil compression and Coil Sketching run faster than reconstruction with all coils due to their significantly cheaper computational cost (A, C). However, the magnified cost functions (B, D) show that coil compression converges to a suboptimal value. Coil Sketching converges slightly slower but attains the optimal value.

Figure 4. 2D radial reconstruction, with image per computational time, animated for reconstruction with all available $$$c=32$$$ coils, coil compression with $$$\hat{c}=3$$$ , and Coil Sketching with $$$\hat{c}=3$$$. Coil compression with $$$\hat{c}=3$$$ is the fastest to converge but presents significantly lower image quality and more streaking artifacts. Coil Sketching converges almost as fast as coil compression, but with the same quality as the reconstruction with all $$$c=32$$$ coils.

Figure 5. Image comparison of 3D Cones reconstruction for (A) reconstruction with all $$$c=20$$$ coils, (B) coil compression with $$$\hat{c}=4$$$ coils, (C) our proposed Coil Sketching with $$$\hat{c}=4$$$ coils. Coil compression with $$$\hat{c}=4$$$ presents significantly lower image quality and shading artifacts, specially towards the lower borders of the volume. Coil Sketching yields virtually the same image as reconstruction with all $$$c=20$$$ coils.

Proc. Intl. Soc. Mag. Reson. Med. 29 (2021)