Multi-kernel unmixing and super-resolution using the Modified Matrix Pencil method

Stéphane Chrétien, Hemant TyagiarXiv 2018 · arXiv

Abstract

This paper presents KrUMMP (Kernel Unmixing via Modified Matrix Pencil), a novel algorithm for solving the multi-kernel unmixing super-resolution problem. While traditional super-resolution assumes a uniform blurring kernel, KrUMMP addresses signals composed of multiple groups of spikes, each affected by a distinct point spread function. By strategically sampling the high-frequency "tails" of the signal's Fourier transform, the algorithm sequentially isolates and resolves overlapping spikes from different groups. We provide theoretical error bounds and demonstrate the algorithm's efficacy through synthetic simulations, highlighting its potential for applications in isotope identification and DNA sequencing.

Introduction

Super-resolution (SR) is a fundamental task in signal processing aimed at recovering fine-scale point sources, or "spikes," from blurred, low-resolution observations. Standard SR techniques typically assume that all spikes in a signal are convolved with the same point spread function (PSF). However, in many practical domains, this assumption fails. For instance, in isotope identification, gamma-ray spectra contain peaks with varying widths and shapes depending on the underlying physical processes.

Gamma-ray spectrum of $^{232}Th$ showing various characteristic peaks, illustrating the complexity of isotope identification.

Similarly, in DNA sequencing, fluorescent traces often exhibit overlapping signals from different bases, each potentially subjected to different levels of dispersion or blurring.

DNA sequencing trace from SnapGene Viewer, where overlapping fluorescent signals require precise unmixing and resolution.

The "multi-kernel" challenge requires simultaneously unmixing the contributions of these different kernels and performing super-resolution to pinpoint the locations and amplitudes of the underlying spikes. KrUMMP is designed to tackle this problem even when spikes from different groups overlap significantly.

Methods: The KrUMMP Algorithm

The Kernel Unmixing via Modified Matrix Pencil (KrUMMP) algorithm relies on three core principles:

  1. Fourier Tail Sampling: The algorithm exploits the fact that "sharper" kernels (smaller scales) decay more slowly in the frequency domain than "blunt" kernels. By sampling the signal at high frequencies—the "tails"—the algorithm isolates the contribution of the sharpest kernel, as the influence of broader kernels becomes negligible.
  2. Sequential Estimation (Deflation): KrUMMP operates recursively. It first estimates the parameters (locations and amplitudes) of the group associated with the sharpest kernel. It then "deflates" the signal by subtracting this estimated contribution from the Fourier samples before proceeding to the next sharpest kernel.
  3. Modified Matrix Pencil (MMP): At each stage, the algorithm employs a modified version of the Matrix Pencil method. This technique is used to estimate the parameters of a sum of complex exponentials, which corresponds to the deconvolved Fourier samples in each group.

Results and Analysis

The paper provides rigorous theoretical guarantees for KrUMMP. Theorem 1 and Theorem 2 establish non-asymptotic error bounds for noiseless and noisy settings, respectively. These bounds demonstrate that the estimation error is controlled by the noise level and the separation of spikes within each group.

A key insight from the theoretical analysis is the distinction between intra-group and inter-group separation. Stable recovery primarily depends on the separation of spikes within the same group ($\Delta_l$). Remarkably, spikes from different groups can overlap perfectly, and the algorithm can still distinguish them due to their different blurring scales.

In synthetic Monte Carlo simulations involving $L=4$ groups and varying numbers of spikes ($K \in \{2, 3, 4, 5\}$), KrUMMP achieved high precision. In noiseless trials, recovery was near-exact for the first two groups. Under additive Gaussian noise (standard deviation $5 \times 10^{-5}$), the maximum wrap-around error remained below 0.05 in over 82% of trials for the remaining groups, indicating significant robustness.

Discussion and Future Work

While KrUMMP offers a robust framework for multi-kernel super-resolution, several avenues for future research remain. Currently, the algorithm assumes that the kernel scale parameters ($\mu_l$) are known exactly. Future work could explore methods for joint estimation of kernels and spikes. Additionally, extending the framework from 1D signals to 2D images or 3D volumetric data would broaden its applicability. Finally, addressing the inherent noise sensitivity of tail sampling—where the kernel's Fourier transform is small—could involve integrating more advanced statistical methods like Lepski’s method to enhance stability in high-noise environments.

Summary updated

Abstract

Consider $L$ groups of point sources or spike trains, with the $l^{\text{th}}$ group represented by $x_l(t)$. For a function $g:\mathbb{R} \rightarrow \mathbb{R}$, let $g_l(t) = g(t/μ_l)$ denote a point spread function with scale $μ_l > 0$, and with $μ_1 < \cdots < μ_L$. With $y(t) = \sum_{l=1}^{L} (g_l \star x_l)(t)$, our goal is to recover the source parameters given samples of $y$, or given the Fourier samples of $y$. This problem is a generalization of the usual super-resolution setup wherein $L = 1$; we call this the multi-kernel unmixing super-resolution problem. Assuming access to Fourier samples of $y$, we derive an algorithm for this problem for estimating the source parameters of each group, along with precise non-asymptotic guarantees. Our approach involves estimating the group parameters sequentially in the order of increasing scale parameters, i.e., from group $1$ to $L$. In particular, the estimation process at stage $1 \leq l \leq L$ involves (i) carefully sampling the tail of the Fourier transform of $y$, (ii) a \emph{deflation} step wherein we subtract the contribution of the groups processed thus far from the obtained Fourier samples, and (iii) applying Moitra's modified Matrix Pencil method on a deconvolved version of the samples in (ii).
BibTeX
@misc{chretien2018multi,
  author = {Stéphane Chrétien and Hemant Tyagi},
  title = {{Multi-kernel unmixing and super-resolution using the Modified Matrix Pencil method}},
  year = {2018},
  eprint = {1807.02862},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1807.02862},
}
Figure