PaperlayerView exact revision on arXiv

Source-linked AI summary

A general framework for compressed sensing and parallel MRI using annihilating filter based low-rank Hankel matrix

Kyong Hwan Jin, Dongwook Lee, Jong Chul Ye

arXiv:1504.00532v4cs.IT

TL;DR

The paper addresses the separation of pMRI and CS-MRI by proposing ALOHA, a unified k-space interpolation framework based on transform sparsity and low-rank weighted Hankel matrices. It converts both problems into structured matrix completion, generalizes the framework to wavelet-sparse and multichannel data, and reports superior reconstruction performance across static, parallel, and dynamic MRI experiments.

  • Problem

    Existing low-rank k-space theory did not clearly cover broad image models that are sparsified by transforms such as wavelets or total variation.

  • Method

    ALOHA links transform-domain sparsity to annihilating filters and low-rank weighted Hankel matrices, enabling unified structured-matrix k-space interpolation for sparse and multichannel MRI.

  • Results

    Experiments confirmed superior performance over existing compressed-sensing and parallel-imaging methods in single-coil static, static parallel, and dynamic MRI.

  • Takeaways & Limitations

    ALOHA provides a general framework that unifies transform-sparse compressed sensing and parallel MRI reconstruction through low-rank Hankel modeling.

Abstract

from arXiv · show

Parallel MRI (pMRI) and compressed sensing MRI (CS-MRI) have been considered as two distinct reconstruction problems. Inspired by recent k-space interpolation methods, an annihilating filter based low-rank Hankel matrix approach (ALOHA) is proposed as a general framework for sparsity-driven k-space interpolation method which unifies pMRI and CS-MRI. Specifically, our framework is based on the fundamental duality between the transform domain sparsity in the primary space and the low-rankness of weighted Hankel matrix in the reciprocal space, which converts pMRI and CS-MRI to a k-space interpolation problem using structured matrix completion. Using theoretical results from the latest compressed sensing literatures, we showed that the required sampling rates for ALOHA may achieve the optimal rate. Experimental results with in vivo data for single/multi-coil imaging as well as dynamic imaging confirmed that the proposed method outperforms the state-of-the-art pMRI and CS-MRI.

I. INTRODUCTION

The paper develops ALOHA to unify compressed sensing and parallel MRI through a shared k-space interpolation framework based on transform sparsity and low-rank Hankel structure. It addresses calibration and modeling limitations in existing approaches and reports strong reconstruction performance across single-coil, multichannel, and dynamic imaging.

  • Motivation: pMRI exploits receiver-coil sensitivity diversity, while CS-MRI uses transform-domain sparsity to reconstruct images from reduced k-space data.These approaches have traditionally been treated as distinct accelerated MRI reconstruction problems.
  • Limitations of existing methods: Existing parallel-imaging methods such as SENSE and GRAPPA require regularly sampled k-space, often including ACS lines for coil-map or kernel estimation.Accurate coil sensitivity maps or GRAPPA kernels are essential for fully exploiting coil information.
  • Limitations of existing methods: Calibration-less methods such as SAKE use block-Hankel structural constraints, but the origin and single-coil implications of their low rankness were initially unclear.Prior work connected single-coil Hankel low rankness to finite support or slowly varying phase, motivating broader theory.
  • ALOHA framework: ALOHA generalizes low-rank k-space methods to transform-sparse signals by linking transform sparsity to annihilating filters and rank-deficient weighted Hankel matrices.The Hankel rank is determined by transform-domain sparsity, enabling missing weighted k-space recovery through low-rank matrix completion and subsequent unweighting.
  • ALOHA framework: The framework supports wavelet-domain reconstruction through pyramidal, scale-dependent processing and exploits inter-coil annihilating-filter relationships using concatenated Hankel matrices.The multichannel construction is related to multiple-measurement-vector compressed sensing and can exploit coil diversity.
  • Reported results: Experiments reported improved performance over existing compressed-sensing and parallel-imaging approaches, including static single-coil and calibration-free parallel imaging.The paper also reports scattered reconstruction errors rather than systematic edge distortion and potential relevance to clinical applications.

II. FUNDAMENTAL DUALITY BETWEEN SPARSITY AND LOW-RANKNESS

The paper establishes a duality: transform-domain sparsity corresponds to low-rankness of a weighted Hankel matrix, enabling missing k-space recovery through matrix completion.

  • Rank condition: For a signal with k Diracs and annihilating-filter length κ, the Hankel matrix rank satisfies RANK_H(ŷ) ≤ k.The stated condition is n1 − κ + 1 ≥ k.
  • Sparsity–low-rankness duality: Transform-domain sparse signals produce annihilating filters and rank-deficient weighted Hankel matrices in the Fourier domain.The framework extends the finite-rate-of-innovation model beyond minimum-length filters by allowing longer annihilating filters that preserve low-rank structure.
  • K-space interpolation: Missing weighted Fourier samples can be recovered by low-rank matrix completion, followed by division by the weighting filter where its spectrum is nonzero.Samples at spectral filter nulls must instead be acquired directly.
  • Recovery formulation: Nuclear-norm minimization provides a convex recovery formulation for the missing k-space elements.The formulation is paired with a theoretical performance guarantee under random sampling.
  • Sampling guarantee: m > c1µ1κ log^4(n1) samples can enable perfect recovery with probability exceeding 1 − n1^-2 under the theorem’s random-sampling assumptions.The sampling rate is described as nearly optimal because it is proportional to the unknown sparsity up to a log^4(·) factor.
  • Implication: Recasting compressed sensing as low-rank Hankel completion in the measurement domain is stated to incur no expected performance loss.The claim follows from the paper’s reformulation and sampling-rate discussion.

III. ALOHA FOR ACCELERATED MRI

ALOHA is developed for accelerated MRI through two low-rank matrix-completion realizations: pyramidal decomposition for wavelet-sparse signals and a multichannel generalization.

  • Framework: Both realizations are presented as low-rank matrix-completion approaches useful for MR applications.The section frames them as distinct implementations of the same framework.
  • Wavelet-sparse MRI: The accelerated-MRI framework includes a pyramidal decomposition algorithm for wavelet-domain sparse signals.This realization progressively handles scale-dependent structure.
  • Parallel MRI: A second realization generalizes the approach to multichannel MRI.This provides the basis for the parallel-MRI formulation developed later.

A. Recovery of Wavelet Sparse Signals

For wavelet-sparse signals, ALOHA uses scale-dependent weighting and pyramidal decomposition to construct low-rank Hankel completion problems while managing aliasing across scales.

  • Wavelet sparsification: Wavelet transforms can sparsify signals, and a maximally localized smoothing function minimizes the number of nonzero coefficients at each scale.With a unit-support triangle basis, the zeroth-scale sparsity can equal k, the number of Diracs.
  • Properties and scope: The pyramidal structure can reduce computational complexity and is reported to be more robust to noise and model mismatch.The authors explicitly state that the proposed scheme is not claimed to be optimal.
  • Multiscale structure: Dyadic downsampling reduces the scale-dependent sparsity level back to k despite the wavelet support increasing to 2^s.The decimation by 2^s maintains the sparsity level across scales.
  • Hankel construction: The resulting Fourier representation admits annihilating filters and low-rank Hankel matrices because the wavelet coefficients are at most k-sparse.This links wavelet sparsity to the same spectral model used in the fundamental duality.
  • Aliasing management: Aliased, wavelet-weighted spectral copies prevent direct low-rank completion, so ALOHA approximately decouples them using pyramidal decomposition.The method proceeds from the lowest scale s = 0 to the highest scale.
  • Scale-wise reconstruction: Each scale performs k-space extraction, wavelet-spectrum weighting, low-rank Hankel completion, unweighting, and data replacement.Static imaging uses 2-D weighting, whereas dynamic MRI requires one-dimensional weighting along the phase-encoding direction.

B. Generalization to Parallel MRI

ALOHA extends the annihilating-filter framework to parallel MRI by stacking coil-specific Hankel matrices and exploiting inter-coil relationships.

  • pMRI model: Parallel-MRI coil images are modeled as products of a common image and coil-specific sensitivity maps.The Fourier-domain formulation yields an inter-coil annihilating-filter relationship.
  • Multichannel construction: Hankel matrices from the individual channels are concatenated side by side to form an augmented matrix Y.This construction explicitly exploits the inter-coil annihilation property.
  • Rank condition: The concatenated Hankel matrix has rank at most r(2k − r + 1)/2, where k is sparsity and r is the number of coils.The rank condition yields a multichannel low-rank completion formulation.
  • Sampling structure: Parallel acquisition provides mr k-space samples when m locations are sampled simultaneously across r coils.The total sample count is compared with the degrees of freedom of the multichannel signal.
  • Implication: The pMRI ALOHA formulation is described as fully exploiting multichannel diversity without losing the theoretical optimality of the single-coil formulation.The authors connect this formulation to generalizing GRAPPA-type relationships to transform-domain sparse signals.
  • Experimental scope: The resulting single- and multichannel formulations are reported to show superior reconstruction performance in experiments.This statement is presented as an experimental outcome rather than a theoretical guarantee.

IV. IMPLEMENTATION DETAILS

The implementation constructs 2D Hankel matrices from undersampled k-space and enforces annihilation within the valid interior domain. ALOHA differs from related constructions through k-space weighting and side-by-side stacking of multi-coil Hankel matrices.

  • ALOHA construction: ALOHA forms a block Hankel matrix from 2D k-space data using an annihilating filter relation.The construction uses the k-space matrix, a 2D annihilating-filter matrix, and an augmented matrix assembled from r channels.
  • 2D annihilation: 2D annihilation holds only inside the domain after boundary effects are removed from convolution.The valid region is the area where the annihilation property applies.
  • Comparison with related constructions: Figure 2 compares ALOHA, SAKE, and LORAKS block-Hankel constructions, with NR denoting LORAKS’s neighborhood-pixel count.Panel (a) shows the annihilation region, while panels (b)–(d) show the three matrix constructions.
  • Multi-coil construction: In multi-coil data, ALOHA stacks the coil-specific Hankel matrices side by side.This distinguishes its block structure from SAKE’s construction.
  • Key implementation distinction: K-space weighting is the proposed method’s most important construction difference from related Hankel approaches.The paper identifies weighting as the key novelty of the proposed method.

B. Hankel structured matrix completion algorithm

The completion algorithm combines matrix factorization and ADMM to recover a low-rank Hankel matrix while preserving known k-space entries and structure. LMaFit supplies efficient initialization and rank estimation, whereas ADMM imposes the Hankel constraint.

  • Initialization: LMaFit initializes the low-rank factors, estimates rank automatically, and uses QR factorization instead of SVD.Its factorized optimization preserves the known entries of the initialized Hankel matrix.
  • Optimization formulation: ALOHA solves structured rank minimization through a nuclear-norm formulation with matrix-factorization and data-consistency constraints.The ADMM cost includes an indicator enforcing agreement with observed entries.
  • ADMM updates: ADMM alternates updates for the matrix variable, low-rank factors, and the Lagrangian multiplier.The matrix update uses projection and a Hankel pseudo-inverse, while factor updates are obtained separately.
  • Structure enforcement: The Hankel pseudo-inverse averages duplicated structured entries and maps them back to the original k-space coordinates.This step restores the original-coordinate representation from the block-Hankel structure.
  • Computational complexity: Because computational complexity depends on estimated Hankel rank, the large matrix size can remain manageable when that rank is small.The paper reports that the smaller estimated rank significantly reduces overall complexity.
  • Algorithmic limitation: LMaFit alone cannot recover the block-Hankel structure, so an ADMM step is applied afterward.The non-convex factorization is described as converging to a stationary point under the cited analysis.

C. Reconstruction Flow

ALOHA reconstructs undersampled static or dynamic k-space through weighted Hankel completion across a coarse-to-fine pyramid. Wavelet weighting links transform sparsity to low-rank structure before k-space unweighting.

  • Overall flow: ALOHA’s reconstruction flow combines pyramidal decomposition, k-space weighting, Hankel formation, rank estimation, low-rank completion, and unweighting.The same framework supports static, dynamic, and multi-coil acquisition settings.
  • Static reconstruction: Static MRI constructs Hankel matrices from the two downsampled phase-encoding directions, kx and ky.Each finer-to-coarser step retains one-fourth of the previous-scale data around zero frequency.
  • Dynamic reconstruction: Dynamic MRI fully samples the readout direction while undersampling ky over time, so the Hankel matrix is built from ky−t data.The dynamic signal is assumed sparse in spatial wavelets and temporal Fourier coordinates.
  • Pyramidal processing: Each pyramid level uses interpolated lower-scale k-space to initialize completion at the current scale.This accelerates convergence and provides additional refinement of low-frequency samples.
  • Weighting and unweighting: Wavelet weighting is applied before completion and removed pixel-by-pixel afterward by dividing by the weighting function.Static data uses 2D weighting, while dynamic data uses 1D weighting along the phase-encoding direction.
  • 2D weighting: Sequential axis weighting is used in 2D static MRI because separable simultaneous weighting cannot recover components on the ωx=0 or ωy=0 axes.The method applies weighting along one axis and then the other.
  • Unweighting condition: Unweighting avoids division by zero because the DC and some low-frequency k-space values are acquired.This assumption applies to the zero value of the weighting function at DC.

A. Static MR experiments

Across single-coil, parallel, and dynamic MRI experiments, ALOHA produced more accurate reconstructions than the reported comparison methods. Weighting was essential, while the weighted method remained stable as filter size increased.

  • Single-coil compressed sensing: ALOHA was quantitatively superior to l1-wavelet and TV compressed sensing in single-coil brain reconstruction at fourfold acceleration.Its images showed less perceptible distortion and more accurate edges than those methods.
  • Static parallel imaging: GRAPPA’s additional 50 ACS samples reduced its effective downsampling ratio from the nominal eightfold acceleration to 4.785.The comparison therefore used different effective sampling rates for GRAPPA and the other algorithms.
  • Static parallel imaging: ALOHA achieved the most accurate parallel-imaging reconstruction at eightfold acceleration among GRAPPA, SAKE, and SAKE with ESPIRiT.SAKE distorted structures near the inner skull and tissue boundaries, while SAKE with ESPIRiT retained errors around the skull.
  • Runtime: 22.2 sec was the reconstruction time for the preliminary GPU ALOHA implementation, with a fivefold speed-up over its CPU implementation.Reported MATLAB times were 9 s for GRAPPA, 320.4 s for SAKE, and 21.6 s for SAKE with ESPIRiT.
  • Dynamic parallel imaging: At eightfold acceleration with four coils, average NMSE values were 8.75 × 10^-3, 4.983 × 10^-3, and 3.436 × 10^-3 for k-t FOCUSS, SAKE, and ALOHA, respectively.ALOHA also showed reduced residual artifacts and more accurate temporal structures, especially during systole.
  • Dynamic parallel imaging: Average NMSE values for LORAKS and ALOHA were 1.363 × 10^-2 and 1.151 × 10^-2, respectively, confirming lower error for ALOHA.The proposed reconstruction preserved sharper temporal variation than LORAKS and k-t FOCUSS.
  • Weighting ablation: Weighted ALOHA consistently achieved lower NMSE than unweighted ALOHA regardless of annihilating-filter size.Weighted residual errors were also significantly smaller in both brain and dynamic cardiac experiments.
  • Filter-size sensitivity: Unweighted ALOHA diverged as filter size increased, whereas weighted ALOHA converged and remained invariant once filter size exceeded transform-domain sparsity.The same convergence behavior was observed in dynamic cardiac imaging.

B. Hyper-Parameter Estimation

Hyper-parameter choices balance reconstruction quality, computational cost, and noise robustness. The experiments identify scale, filter size, tolerance, and Hankel concatenation direction settings for single- and parallel-coil MRI.

  • Dataset-specific setting: For the reported dataset, the k-space size was 208×512, the annihilating filter was 23×23, and 7×7 low-frequency samples were acquired.These settings determined the maximum usable decomposition scale in the experiment.
  • Decomposition level: The maximum decomposition scale was set to s = 2 because performance gains became negligible for s ≥3.The constraint from the Hankel dimensions gives s ≤2, while Fig. 7 shows increasing gains up to the selected scale.
  • Annihilating filter size: The annihilating filter should exceed the transform sparsity level, although the theoretically optimal 2D size n1^1/2 × m1^1/2 can be computationally burdensome.Experiments therefore reduced filter size when image quality was not degraded; parallel imaging permits smaller filters because of inter-coil annihilating filters.
  • Fitting tolerance: LMaFit tolerances were decreased across scales because high-frequency noise is boosted at lower scales, whereas lower-frequency data require more accurate fitting at higher scales.The tolerance controls fitting accuracy and contributes to determining the initial rank estimate.
  • Hankel concatenation direction: Side-by-side Hankel augmentation outperformed vertical augmentation for parallel MRI reconstruction.The result agrees with the inter-coil annihilating-filter analysis, which requires the Hankel matrices to be stacked side by side.

D. Further Extensions

The paper positions ALOHA as a first step toward broader sparse and low-rank reconstruction models. It reports extensions to non-Cartesian, noisy, off-resonance, dynamic, and alternative sparsity settings while identifying several areas requiring further investigation.

  • Scope and future work: The authors describe this work as a first step toward unifying sparse and low-rank models, leaving room for further development.They specifically identify broader measurement and sparsity models as requiring more extensive investigation.
  • Measurement models: ALOHA can be reformulated for general non-Cartesian imaging and noisy measurements using gridding and an l2 data-fidelity term.The mapping AΩ interpolates non-Cartesian data onto a Cartesian grid, with noise level δ determined by gridding or measurement noise.
  • System non-idealities: An ALOHA extension can remove EPI ghost artifacts by interpolating missing data in a rank-deficient Hankel matrix formed from even- and odd-echo k-space differences.General off-resonance-corrected MR reconstruction remains an open problem.
  • Alternative sparsifying transforms: Using non-decimated redundant wavelets increases the number of non-zero coefficients up to 2^s k, requiring more measurements for coarse-scale recovery.The proposed use of recovered high-frequency samples for coarser interpolation has not been systematically evaluated.
  • Core framework: The framework uses transform-domain sparsity to represent weighted k-space data as a low-rank Hankel matrix, enabling structured matrix completion.For dyadic wavelets, pyramidal decomposition reduces computational complexity and improves noise robustness.
  • Reported validation: Experiments reported superior results for single-coil static MRI, calibration-free static parallel MRI, and accelerated dynamic single- and multi-coil MRI.These findings support the authors’ conclusion that ALOHA unifies compressed sensing and parallel MRI.
Loading 1504.00532v4…