# 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.^{9} 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^{4} for the weighted Fourier data, and the low-rank relationship always holds.^{9} 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.^{13} 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.

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.^{20} Moreover, after the deconvolution, we achieved true grid-free localization through classical spectral estimation techniques (using only the spectral data).

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.^{14} 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.^{21} Indeed, our ALOHA method clearly outperforms existing approaches for impulse noise removal (see Figure 5).

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).*

Jong Chul Ye is currently a full professor in the Department of Bio and Brain Engineering and an endowed chair professor. He has served as an associate editor of *IEEE Transactions on Image Processing*, and *IEEE Transactions on Computational Imaging*, as well as an editorial board member for *Magnetic Resonance in Medicine*.

*IEEE Trans. Inf. Theory*52, p. 1289-1306, 2006.

*IEEE Trans. Inf. Theory*52, p. 489-509, 2006.

*IEEE Trans. Inf. Theory*51, p. 4203-4215, 2005.

*IEEE Trans. Signal Process.*50, p. 1417-1428, 2002.

*J. École Polytechn. Floréal Plairial*1, p. 24-76, 1795.

*IEEE Trans. Acoust. Speech Signal Process.*38, p. 814-824, 1990.

*IEEE Trans. Signal Process.*55, p. 1741-1757, 2007.

*IEEE Trans. Signal Process.*53, p. 2788-2805, 2005.

*arXiv:1511.08975 [cs.IT]*, 2015.

*arXiv:1504.00532 [cs.IT]*, 2015.

*Magnet. Resonance Med.*, 2016. doi:10.1002/mrm.26081

*Magnet. Resonance Med.*, 2016. doi:10.1002/mrm.26077

*Magnet. Resonance Med.*, in press, 2016.

*IEEE Trans. Image Process.*24, p. 3498-3511, 2015.

*Biophys. J.*102, p. 2391-2400, 2012.

*Sci. Rep.*4, p. 4577, 2014. doi:10.1038/srep04577

*IEEE Trans. Inf. Theory*56, p. 2053-2080, 2010.

*IEEE Trans. Inf. Theory*57, p. 1548-1566, 2011.

*Soc. Indust. Appl. Math. J. Sci. Comp.*31, p. 2842-2865, 2009.

*Proc. SPIE*9597, p. 95970V, 2015. doi:10.1117/12.2187393

*arXiv:1510.05559 [cs.CV]*, 2015.