Per-Scan Optimality Certificates for Accelerated MRI Sampling

An MRI scanner collects raw frequency-domain measurements, called k-space, one line at a time. Collecting fewer lines shortens the scan, so every accelerated scan has to answer a discrete question: which $K$ of the $N$ possible lines should it collect? Current methods answer this with heuristics that come with no guarantee. These include local line-swapping searches, gradient-trained soft masks, and nearest-neighbor lookup. The theory of approximation algorithms offers guarantees, but only worst-case ones, and those are usually too loose to be useful. The one imaging result in this area proves that binary masks can come within a universal factor of about 18.3 dB of the physical limit. In image quality terms that margin is huge.

We propose replacing worst-case ratios with per-scan certificates. For each incoming scan, a cheap convex relaxation of the line-selection problem, solved under a scan-specific Gaussian model of the anatomy, gives a lower bound on the error any $K$-line mask could achieve. Evaluating any concrete mask gives an upper bound. The ratio between the two is a certified optimality gap for that patient. It is measured in decibels on real anatomy rather than on an adversarial worst case. The certificate lets us answer three questions nobody has measured. How hard is k-space selection on real data? Are the existing heuristics already near-optimal? Can the certificate itself decide, patient by patient, when enough lines have been collected?

Core Claim

The approximation-hardness gap for k-space line selection is a property of the instance, and it can be measured on each scan in a few seconds. We hypothesize three things. First, on fastMRI multi-coil data the certified gap for good rounding schemes will be a small fraction of a decibel, much smaller than the 18.3 dB universal constant from Near-optimal Coded Apertures for Imaging via Nazarov's Theorem. Second, the masks that are optimal under the Gaussian surrogate will rank-correlate with deep-reconstructor error well enough to be useful. Third, the certificate supports variable-length scans: each patient stops acquiring once the certified error falls below a target, which shortens the average scan relative to a fixed 8x protocol at equal quality.

The first hypothesis could fail, and a failure would still be informative. A large gap would tell us exactly which patients and which accelerations leave headroom for better selection.

Relation to Prior Work

Three MRI methods supply the heuristics we will certify. SUNO optimizes Cartesian masks per training slice by coordinate-descent line swaps. At test time it retrieves a mask by matching low-frequency k-space, in about 0.85 s, and it has no bound on either the swap search or the retrieval mismatch. Deep Probabilistic Subsampling learns a population mask through a Gumbel-Softmax relaxation. That relaxation is a continuous stand-in for the discrete choice, and nobody has analyzed how much is lost when rounding it back to a hard mask. End-to-end sequential sampling trains an adaptive sampler through straight-through gradients. These papers motivate the proposal: they perform well without anyone knowing how far they are from the best possible mask. We do not replace them. We attach a bound to them.

Three optimization papers supply the method. Randomized greedy sensor selection shows that estimation error under sensor selection is weakly submodular, meaning it nearly has diminishing returns, with the degree controlled by covariance conditioning. It also gives a fast randomized greedy algorithm with recursive covariance updates, which we reuse as a rounding scheme. Dependent randomized rounding shows that swap rounding meets a budget exactly, preserves each item's selection probability, and lowers variance relative to independent sampling. We reuse it to turn fractional line weights into exactly $K$ lines.

The coded-aperture paper plays both roles. It motivates the work, because its constant is loose while its greedy masks track the physical bound empirically. It also constrains the work: its bound applies to one-dimensional, stationary, linear estimation, and our formulation has to leave that setting to say anything about multi-coil MRI.

We are honest about one limitation up front. For single-coil data with a prior that is stationary in frequency, the problem separates across lines. The optimum is then simply the $K$ highest-variance lines, essentially a low-pass mask. That is consistent with low-pass sampling reaching 35.8 dB against DPS's 36.2 dB at 80x in the DPS paper. The combinatorial difficulty, and therefore the interest of a certificate, comes entirely from coil-sensitivity coupling and from priors that are not stationary and are specific to the scan. Our formulation keeps both.

Research Program

The certificate is computed in four steps.

Scan-specific prior. For each scan, we first acquire the low-frequency center, which SUNO already uses as its search key. We use it to retrieve the $n$ most similar training images. From these we build a Gaussian prior with covariance $\Sigma = U U^H + D$. Here $U$ is a rank-$r$ basis spanning the neighbors' images, and $D$ is a diagonal variance in a wavelet basis that captures residual detail.

Relaxed selection problem. Candidate line $i$ contributes an information matrix $F_i = A_i^H A_i / \sigma^2$. Here $A_i$ is the multi-coil forward operator for that line: coil sensitivities, then Fourier transform, then restriction to the line. The noise variance is $\sigma^2$. The relaxed A-optimal design problem is

$$ L^\star = \min_{w \in [0,1]^N,\ \sum_i w_i = K} \ \mathrm{tr}\Big(\big(\Sigma^{-1} + \textstyle\sum_i w_i F_i\big)^{-1}\Big), $$

where $w_i$ is a fractional weight on line $i$, and the trace is the expected squared reconstruction error of the linear posterior-mean estimator. The objective is convex in $w$, so $L^\star$ lower-bounds the error of every integral $K$-line mask under this surrogate. We solve it with Frank-Wolfe, a method that moves toward the best single line at each step, using the low-rank-plus-diagonal structure through the Woodbury identity. The duality gap Frank-Wolfe reports gives a valid lower bound even when the solver stops early.

Rounding. We round $w$ to exactly $K$ lines by top-$K$ selection, by swap rounding, and by randomized greedy started from the relaxation's support. For any mask $S$, including SUNO's, DPS's, or an equispaced mask, the certified gap is

$$ g(S) = 10 \log_{10}\big(E(S) / L^\star\big), $$

where $E(S)$ is the surrogate error of $S$. The gap is expressed in dB, the same units as the 18.3 dB constant.

Budget control. In the variable-budget mode, lines are added in batches. After each batch the relaxation is re-solved with the collected lines fixed, and acquisition stops when $L^\star$ reaches a target. Unlike a heuristic stopping rule, this target is tied to a certified bound.

The analysis has two parts. Empirically, we measure the distribution of $g$ across fastMRI scans and relate it to anatomy, coil count, and acceleration. Theoretically, we compute the weak-submodularity ratio of the multi-coil Fourier objective, following Hashemi et al., to see whether it predicts where greedy selection falls short.

Baselines

The naive reference point is a fixed equispaced mask with a fully sampled center, reconstructed by an E2E-VarNet trained on that mask. End-to-End Variational Networks, an unrolled network alternating data consistency with learned refinement, reports SSIM 0.890 on the fastMRI knee test set at 8x with fixed masks. We will retrain it ourselves on the same splits so every comparison uses identical reconstructor capacity. Every proposed mask must beat this reference in NRMSE and SSIM at the same line count.

The strongest existing competitor is SUNO. It is scan-adaptive, it is fast, and it beats LOUPE, BASS, and sequential sampling on multi-coil fastMRI knee and brain at 4x and 8x. No reported result was found on Lacuna for SUNO's exact PSNR, SSIM, or NRMSE values, so we will reimplement it from the paper's description. It will get the same training library, the same VarNet or MoDL reconstructor, and an equal offline coordinate-descent budget. Beating SUNO means lower mean NRMSE at 8x across scans at comparable online latency. If our quality merely matches SUNO's, the certificate is still the contribution, and we will say so.

The population-learned competitors are DPS and LOUPE, trained under identical conditions. DPS reports 36.2 dB PSNR at 80x on knee data. Sequential sampling reports SSIM 92.91 against LOUPE's 92.44 at 4x with point sampling. These numbers come from different settings, so they serve only as sanity anchors, not as targets.

Two ablations isolate the key ingredients. The first compares the scan-specific prior with a single population prior, which tests whether per-patient structure matters. The second compares swap rounding with top-$K$ rounding of the same fractional $w$, which tests whether dependent rounding contributes beyond the relaxation itself.

Why not just…?

Why not just run greedy line selection and skip the bound? The coded-aperture paper shows greedy bit-flipping tracking the physical limit in one dimension, so greedy may well be near-optimal here too. We expect that result. The point is that currently nobody can know whether it holds on a given scan. The certificate turns the belief into a measurement. If gaps are uniformly tiny, we will report that the approximation-hardness gap is practically irrelevant for Cartesian MRI, and that is a useful negative result. Greedy remains a rounding scheme inside our pipeline, not a rival to it.

Why not just use SUNO? SUNO is a genuine threat on quality alone. Its retrieval, however, gives no signal when a patient differs from every library entry, and that is exactly where hallucination risk lives. We will evaluate SUNO's masks under our certificate, stratified by nearest-neighbor distance. If SUNO's gap grows with retrieval distance while our re-solved masks stay near the bound, the certificate adds value SUNO cannot provide. If SUNO's gap stays flat, SUNO's retrieval is empirically safe, and we will report that.

Why not just train a strong reconstructor on a fixed mask? VarNet at 0.890 SSIM shows that much of the benefit comes from the reconstructor. The reason to certify the mask is that no reconstructor can recover information that was never measured. The pathology-level comparison on fastMRI+ lesion regions tests whether certified masks preserve measured lesion detail that fixed masks lose, even when global SSIM is similar.

Why not just prove a weak-submodularity ratio for k-space? Worst-case ratios for this objective depend on the covariance condition number, which is poor for MRI priors. Such a ratio would likely reproduce the looseness of the 18.3 dB constant. We will compute the ratio anyway and compare it with the observed certified gaps, which directly measures how loose the worst-case analysis is.

Proposed Experiments

We use fastMRI multi-coil knee (1,594 volumes) and brain (6,970 volumes), described in the fastMRI dataset paper, with retrospective Cartesian undersampling at 4x and 8x. The fastMRI+ annotations are used for lesion-region error. Metrics are NRMSE, PSNR, SSIM, lesion-region NRMSE, certified gap in dB, and online wall time.

Three checks decide the project.

Distribution of gaps. We compute the distribution of $g$ for equispaced, DPS, SUNO, greedy, and swap-rounded masks. This tells us how hard the problem is on real anatomy.

Transfer to deep reconstruction. Across roughly fifty candidate masks per scan, we compute the Spearman rank correlation between surrogate error and VarNet NRMSE. If it is weak, the surrogate certificate says little about deep reconstruction, and we will narrow the claims to linear reconstruction accordingly.

Certificate-driven budgets. At matched average line count, variable per-patient budgets should give lower worst-decile VarNet NRMSE than fixed 8x. Equivalently, reaching the same worst-decile quality should take fewer average lines, which is a direct saving in scan time.