Justin P. Haldar^{1} and Daeun Kim^{1}

We propose a novel approach to designing optimal k-space sampling patterns for sparsity-constrained MRI. The new approach, called OEDIPUS (Oracle-based Experiment Design for Imaging Parsimoniously Under Sparsity constraints), is inspired by insights and methods from estimation theory and the statistical design of experiments. Specifically, OEDIPUS combines the oracle-based Cramér-Rao bound for sparsity-constrained reconstruction with sequential greedy algorithms for observation selection. We demonstrate that OEDIPUS can be used to deterministically and automatically generate k-space sampling patterns that are tailored to specific hardware and application contexts, and which lead to better reconstruction performance relative to conventional sampling approaches for sparse MRI.

OEDIPUS
is based on choosing k-space samples that optimize the Cramér-Rao bound (CRB)
for estimating a sparse image. The CRB is a theoretical limit on how accurately an unknown parameter
vector can be estimated using an unbiased estimator^{8}, and is
frequently used as an optimality criterion in the statistical design of
experiments^{9}. While the CRB
has been used to optimize k-space sampling in previous work^{10-12}, we
believe that OEDIPUS is the first method to use the CRB to optimize MRI k-space
sampling under sparsity constraints.

Theoretical
results have shown that the CRB under sparsity constraints is equal to the
oracle estimator^{13}. The oracle estimator
is the simple least squares estimator that is obtained when the positions of
the non-zero coefficients of the sparse representation are known, and all other
coefficients are forced to zero. While
the exact locations of the non-zero coefficients are not generally known in
advance, prior images acquired with the same contrast on the same scanner will
generally have similar sparsity patterns, and can be used as surrogates for the
true sparsity pattern during k-space sampling design.

OEDIPUS
proceeds as follows. First, we form the
matrix $$$\mathbf{E}$$$ representing the mapping between the image and a
fully-sampled k-space dataset. In
addition to Fourier encoding, this matrix can also incorporate any other forms
of image encoding, including coil sensitivities in parallel imaging or RF
encoding. While coil calibration and
other similar information is not generally available *a priori*, OEDIPUS can use the
calibration information from past similar scans as a good approximate surrogate
for the true values. Second, we form the matrix $$$\mathbf{S}$$$ that synthesizes
an image from its coefficients in an appropriately-chosen sparsifying transform
domain. Third, we discard the columns
from $$$\mathbf{S}$$$ corresponding to transform coefficients that had
negligible amplitude in a surrogate reference image acquired with the same
sequence, resulting in a truncated matrix $$$\tilde{\mathbf{S}}$$$. Finally, we use observation selection
algorithms^{14-15} to select the rows of the $$$\mathbf{E}$$$ matrix that, when
discarded to form the subsampled matrix $$$\tilde{\mathbf{E}}$$$, lead to the
smallest degradation of the CRB. The trace measure ("A-optimality"^{9}) of the oracle CRB in this case is $$$\mathrm{Trace}(
(\tilde{\mathbf{S}}^H\tilde{\mathbf{E}}^H\tilde{\mathbf{E}}\tilde{\mathbf{S}})^{-1})$$$. For our results, we use
the greedy sequential backward selection algorithm^{14} to find a local minimum of
this difficult (NP-hard) optimization problem, although many other choices are
available that may lead to even better performance.

The final result of this procedure is a deterministically-generated undersampled k-space sampling mask that has been specifically tailored to have small CRB for a specific application context and a specific coil configuration, and which can be used whenever acquiring similar data on the same hardware in the future.

OEDIPUS was
used to design sampling patterns for two different applications (2D T2-weighted
imaging and 3D T1-weighted imaging) for two different coil configurations
(single-channel and 12-channel) and three different acceleration factors
($$$R=2,3,4$$$). The sampling patterns
were tested using retrospective undersampling of fully sampled datasets, and reconstructed using $$$\ell_1$$$-regularization^{2} of Daubechies-4 wavelet
coefficients. Comparisons were made against uniform^{16,17} and Poisson disc random^{18}
undersampling. Results are shown in
Figs. 1-5.

1.
Liang
Z-P, Haacke EM, Thomas CW. “High-resolution
inversion of finite Fourier transform data through a localized polynomial
approximation.” *Inverse Problems*
5:831-847, 1989.

2.
Lustig
M, Donoho D, Pauly JM. “Sparse MRI: The
application of compressed sensing for rapid MR imaging.” *Magnetic Resonance in Medicine* 58:1182-1195,
2007.

3. Haldar JP, Hernando D, Liang Z-P. “Compressed-Sensing MRI with Random Encoding.” *IEEE Transactions on Medical Imaging* 30:893-903, 2011.

4. Adcock B, Hansen AC, Poon C, Roman B. “Breaking the coherence barrier: a new theory for compressed sensing.” *Preprint*, 2013. arXiv:1302.0561

5. Wang Z, Arce GR. “Variable density compressed image sampling.” * IEEE Transactions on Image Processing* 19:264-270, 2010.

6. Puy G, Vandergheynst P, Wiaux Y. “On variable density compressive sampling.” *IEEE Signal Processing Letters* 18:595-598, 2011.

7. Zijlstra F, Viergever MA, Seevinck PR. “Evaluation of variable density and data-driven k-space undersampling for compressed sensing magnetic resonance imaging.” *Investigative Radiology* 51:410-419, 2016.

8. Kay SM. *Fundamentals of Statistical Signal Processing, Volume I: Estimation Theory*. Upper Saddle River: Prentice Hall, 1993.

9. Pukelsheim F. *Optimal Design of Experiments*. New York: John Wiley & Sons, 1993.

10. Marseille GJ, Fuderer M, de Beer R, Mehlkopf AF, van Ormondt D. “Reduction of MRI scan time through nonuniform sampling and edge-distribution modeling.” *Journal of Magnetic Resonance, Series B* 103:292-295, 1994.

11. Xu D, Jacob M, Liang Z-P. “Optimal Sampling of k-Space with Cartesian Grids for Parallel MR Imaging.” *Proc. ISMRM* 2005, p. 2450.

12. Haldar JP, Hernando D, Liang Z-P. “Super-resolution reconstruction of MR image sequences with contrast modeling.” *Proc. IEEE International Symposium of Biomedical Imaging* 2009, pp. 266-269.

13. Ben-Haim Z, Eldar Y. “The Cramér–Rao bound for estimating a sparse parameter vector.” *IEEE Transactions on Signal Processing* 58:3384-3389, 2010.

14. Reeves SJ, Zhe Z. “Sequential algorithms for observation selection.” *IEEE Transactions on Signal Processing* 47:123-132, 1999.

15. Broughton R, Coope I, Renaud P, Tappenden R. “Determinant and exchange algorithms for observation subset selection.” *IEEE Transactions on Image Processing* 19:2437-2443, 2010.

16. Pruessmann KP, Weiger M, Scheidegger MB, Boesiger P. “SENSE: Sensitvity encoding for fast MRI.” *Magnetic Resonance in Medicine* 42:952-962, 1999.

17. Breuer FA, Blaimer M, Mueller MF, Seiberlich N, Heidemann RM, Griswold MA, Jakob PM. “Controlled aliasing in volumetric parallel imaging (2D CAIPIRINHA).” *Magnetic Resonance in Medicine* 55:549-556, 2006.

18. Nayak KS, Nishimura DG. “Randomized trajectories for reduced aliasing artifact.” *Proc. ISMRM* 1998, p. 670.