Low-rank Fourier interpolation for compressed sensing imaging

Fourier imaging problems (in which unknown signals are recovered from Fourier measurements) are important in many applications. According to classical Nyquist sampling theory, the required Fourier sampling rate must be at least twice that of the signal bandwidth. In the past, this has been considered as the fundamental resolution limit in many imaging problems. However, with the recent theory of compressive sampling (CS),^1–3 it is now possible to overcome the Nyquist limit for the accurate recovery of unknown sparse signals from underdetermined Fourier measurements in various imaging applications, e.g., accelerated magnetic resonance imaging (MRI), low-dose x-ray computed tomography, and optics.

To facilitate more robust reconstruction, recovery algorithms usually take the form of a penalized least squares or a constrained optimization framework (which are dependent on the specific signal representation and discretization scheme, rather than the nature of the original problem in the continuous domain). The Fourier CS problem is also closely related to classical harmonic retrieval problems and the sampling theory of finite rate of innovations (FRI).^4–8 Although these methods do not require any discretization, they are less robust to perturbations in the measurements because the algorithm requires polynomial root findings.

To address this, we recently proposed a drastically different two-step Fourier CS framework. This can be implemented as a Fourier-domain interpolation, after which we can conduct a signal reconstruction by using classical analytic reconstruction methods.^9–14 We believe that our two-step approach—the annihilating filter-based low-rank Hankel (ALOHA) matrix approach—can be used as the missing link between the CS and analytic reconstruction (because the best of the two worlds can be fully exploited in each step of the framework).

The main idea for ALOHA originated from the fundamental duality between the sparsity in the primary space and the low rankness of a structured matrix in the spectral domain.⁹ For example, if the underlying signal is a periodic stream of Diracs, we can calculate the annihilating filter in the Fourier domain and can thus null-out the Fourier series coefficients through the use of discrete convolution. Accordingly, we can construct a rank-deficient Hankel-structured matrix. In general, when the signal belongs to a general class of FRI signals, we can always find the minimum length annihilating filter⁴ for the weighted Fourier data, and the low-rank relationship always holds.⁹ Consequently, if some of the Fourier data for an FRI signal is missing, we can construct an appropriately weighted Hankel matrix with missing elements, and these elements can be recovered based on low-rank matrix completion algorithms.^{9, 17,18}

Our two-layer approach is very useful for real-world applications because the low-rank interpolator can be added as a digital correction filter to existing systems. For example, the application of ALOHA to accelerated MRI problems is illustrated in Figure 1.^10–12 For the case of TV regularization, structural distortion around the image edges can be easily recognized. In contrast, our ALOHA reconstruction provided the best edge structures, without boosting the noise level. We have also used a sparse and low-rank decomposition of our ALOHA matrix to decouple sparse outliers for magnetic resonance artifact removal problems.¹³ Our ALOHA results (see Figure 2) show that the corrupted (from low-intensity impulse noise) image could be decomposed from the down-sampled k-space (the 2D or 3D Fourier transform) data (at an acceleration factor of 5) and produce a clear—close to the original—image.

Figure 1. Illustration of the application of the annihilating filter-based low-rank Hankel (ALOHA) matrix approach to compressed sensing of magnetic resonance imaging (MRI) data (at ×4 acceleration). The original (ORIG) images are shown on the left, the results of a total variation (TV) reconstruction are shown in the center, and the ALOHA results are shown on the right. NMSE: Normalized mean square error.

Figure 2. The ALOHA approach is used to provide a robust decomposition of corrupted MRI data (at ×5 acceleration) with impulse noise. The original image (left) is decomposed into a low-rank component (middle) and an artifact component (right).

Our ALOHA concept is so general that it can also be used for other acquisition scenarios, e.g., in super-resolution microscopy (see Figure 3). For these experiments, the goal was to find the locations of fluorescent probes (Picogreen) within the images. As these fluorescent probes could be modeled as a stream of Diracs, a Hankel matrix from a properly deconvolved spectrum was low-ranked. We therefore estimated the optimal blur kernel from the measurement that gave the lowest ranked Hankel matrix.²⁰ Moreover, after the deconvolution, we achieved true grid-free localization through classical spectral estimation techniques (using only the spectral data).

Figure 3. Results from live cell imaging experiments. The human osteosarcoma (U2OS) cells in these images were labeled with Picogreen (a fluorescent probe). (a) A conventional diffraction-limited wide-field image, constructed by accumulating 2000 raw frames. Three different reconstructions of the image in (a) are shown in (b) to (d). The deconvolution-STORM¹⁵ and FALCON¹⁶reconstruction methods are used for (b) and (c), respectively. The image in (d) was obtained with the ALOHA approach. Scale bars indicate 2μm.

Another application of our ALOHA technique is for image processing. For example, we can use ALOHA for missing data interpolation (known as image inpainting), as illustrated in Figure 4.¹⁴ Our results provide near-perfect interpolation, even in the textured area of the ‘Barbara’ test image. In addition, we use ALOHA to successfully interpolate large missing areas of the test images (see Figure 4). Furthermore, the impulse noise in the images can be considered as sparse outliers. We can thus use the sparse and low-rank decomposition of the ALOHA matrix to decouple the impulse noise.²¹ Indeed, our ALOHA method clearly outperforms existing approaches for impulse noise removal (see Figure 5).

Figure 4. Examples of image inpainting achieved with the ALOHA approach. The original images and images with missing pixels are shown in the left and middle columns, respectively. The results of the ALOHA inpainting are shown on the right.

Figure 5. Comparison of impulse noise removal achieved with ALOHA (bottom right) and the existing total variation L1¹⁹ approach (bottom left). The original image and the impulse noise (30%) level are shown in the top left and right, respectively. PSNR: Peak signal-to-noise ratio.

In summary, we have developed a low-rank Fourier interpolation framework for compressed sensing reconstruction problems. In our ALOHA approach we use a structured low-rank interpolator in the measurement domain before the application of an analytic reconstruction procedure. Compared with existing CS approaches, our new method is quite general and can be easily combined with classical analytic reconstruction techniques for various imaging problems. Indeed, the generality of the ALOHA approach means that it can be used basically for all Fourier imaging applications. In our current work we are thus investigating its application to x-ray computed tomography, ultrasound imaging, and optical diffraction tomography.

This study was supported by the Korea Science and Engineering Foundation (grant NRF-2014R1A2A1A11052491).