⚡ electrical engineering

Functional Multi-Reference Alignment via Deconvolution

This paper establishes a novel connection between multi-reference alignment and deconvolution by extending Kotlarski's formula to higher dimensions and signals with vanishing Fourier transforms, enabling signal estimation from second-order statistics of shifted, noisy observations.

Original authors: Omar Al-Ghattas, Anna Little, Daniel Sanz-Alonso, Mikhail Sweeney

Published 2026-05-19

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Omar Al-Ghattas, Anna Little, Daniel Sanz-Alonso, Mikhail Sweeney

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to reconstruct a beautiful, intricate sculpture, but you only have access to a pile of blurry, scattered photos of it. The problem is that every photo was taken from a different angle, the camera was shaky (adding noise), and you don't know exactly where the camera was positioned for each shot. This is the essence of the Multi-Reference Alignment (MRA) problem: figuring out what the original object looks like when all you have are shifted, noisy copies of it.

This paper introduces a new, powerful way to solve this puzzle by connecting it to a different field of math called deconvolution. Here is a simple breakdown of their approach, their new tools, and what they found.

1. The Core Idea: The "Echo" Trick

Usually, to fix a blurry, shifted image, you might try to guess the shifts and line them up one by one. But in very noisy conditions, this is like trying to hear a whisper in a hurricane; it's nearly impossible.

The authors realized that instead of trying to align the photos individually, you can look at the statistical patterns of the whole pile of photos at once. They discovered a mathematical "echo" effect. If you take all the noisy photos and mix them together in a specific way (looking at their second-order statistics, or how they correlate with each other), the random noise canc itself out, and the hidden pattern of the original signal starts to emerge.

They connected this to a classic math problem called deconvolution, which is like trying to figure out what a sound was before it bounced off a wall. They used a specific mathematical formula (called Kotlarski's formula) that acts like a decoder ring. It allows them to reverse-engineer the original signal directly from the messy data without needing to know the exact shifts first.

2. The New Tools: Handling the "Vanishing" Problem

In the past, these mathematical decoder rings had a strict rule: they only worked if the signal had a "loud" presence at every frequency (like a song that never goes silent). If the signal had a "quiet spot" or a vanishing Fourier transform (a place where the signal's energy drops to zero), the old math would break down.

The authors did two major things to fix this:

Generalized the Formula: They extended the decoder ring to work in multiple dimensions (not just 1D lines, but 2D images and 3D volumes), making it useful for real-world objects like molecules or radar targets.
The "Zero" Hunter: They invented a new step in their algorithm to handle signals that go silent. Imagine trying to find the zeros of a function is like finding the quiet moments in a song. Their new method carefully identifies these "quiet spots" and skips over them, allowing the math to work even when the signal disappears in certain frequencies.

3. The Results: Why It's Better

The paper compares their new "Deconvolution Approach" against older methods that rely on aligning the data point-by-point (like trying to match puzzle pieces one by one).

Robustness: Their method is much more stable when the data is very noisy. While older methods fail when the noise gets too high or the signal gets too long, the new method keeps working.
No "Grid" Assumption: Older methods often assume the shifts happen on a perfect, rigid grid (like moving a photo exactly 1 pixel at a time). The authors' method works with continuous shifts (moving the photo by any amount, like 1.34 pixels), which is much more realistic for things like molecular structures in biology.
Sample Efficiency: They proved mathematically that you don't need an infinite amount of data to get a good picture. They calculated exactly how many samples you need based on how noisy the data is and how smooth the signal is.

4. The "Super Smooth" Advantage

They tested their method on different types of signals. They found that if the signal is "smooth" (like a gentle hill rather than a jagged mountain), the method recovers it incredibly well. Even better, if the signal is "super smooth" (decaying very quickly in frequency), the recovery is even more accurate.

Summary

Think of this paper as upgrading the way we reconstruct a shattered mirror. Instead of trying to glue every shard back together one by one (which fails if the shards are dirty or the glue is wet), the authors developed a method to look at the pile of shards as a whole. By using a special mathematical lens (Kotlarski's formula), they can see the reflection of the original image clearly, even if the shards are scattered, dirty, and some parts of the mirror are missing. This works for complex, multi-dimensional objects and handles the "missing pieces" (vanishing frequencies) that used to break the system.

Technical Summary: Functional Multi-Reference Alignment via Deconvolution

1. Problem Statement

This paper addresses the Functional Multi-Reference Alignment (MRA) problem. The objective is to estimate an unknown, real-valued signal function $f: \mathbb{R}^d \to \mathbb{R}$ from $N$ independent, noisy observations. Each observation $y_n$ is a shifted and corrupted version of the signal:
$y_n(t) = f(t - \zeta_n) + \eta_n(t), \quad t \in D$
where:

$D \subset \mathbb{R}^d$ is a bounded domain.
$\zeta_n$ are independent random shifts drawn from an unknown distribution with compact support.
$\eta_n$ are independent, centered Gaussian processes with a known covariance function $k_\eta$ .

The paper distinguishes this functional formulation from the classical discrete MRA model. In discrete MRA, the signal is a finite vector, shifts are cyclic (modulo the signal length), and noise is often modeled as white (uncorrelated). The functional setting is motivated by applications like cryo-electron microscopy (cryo-EM), where signals represent physical objects (functions) and transformations (translations/rotations) are continuous and non-cyclic. Furthermore, the functional model allows for spatially correlated noise, which is more realistic for high-resolution imaging than the white noise assumption that becomes ill-posed as discretization increases.

2. Methodology: Connection to Deconvolution

The core methodological contribution is establishing a rigorous connection between functional MRA and the statistical problem of deconvolution with replicated measurements.

2.1. Theoretical Foundation: Kotlarski's Identity

In the Fourier domain, the observation model becomes:
$\hat{y}_n(\omega) = e^{-i\omega \cdot \zeta_n} \hat{f}(\omega) + \hat{\eta}_n(\omega)$
The authors analyze the autocorrelation of the non-centered process $\hat{y}$ . They define the function $\Psi(\omega_1, \omega_2)$ based on the second-order statistics (autocorrelation) of the observations:
$\Psi(\omega_1, \omega_2) = \hat{f}(\omega_1)\hat{f}(\omega_2)\hat{p}_\zeta(\omega_1 - \omega_2)$
where $\hat{p}_\zeta$ is the characteristic function of the shift distribution.

The paper demonstrates that $\hat{f}$ can be recovered from $\Psi$ using a generalization of Kotlarski's identity, a classic result in deconvolution that guarantees the identifiability of latent distributions from replicated noisy observations. Specifically, if $\Psi$ is non-vanishing on its diagonal, $\hat{f}$ is determined by a path integral of the gradient of $\Psi$ :
$\hat{f}(\omega) = \exp\left( \int_0^1 \frac{\nabla_1 \Psi(\alpha\omega, \alpha\omega)}{\Psi(\alpha\omega, \alpha\omega)} \cdot \omega \, d\alpha \right)$
This formula allows the estimation of the signal's Fourier transform directly from second-order statistics, bypassing the need for shift synchronization or higher-order moments (e.g., bispectra) typically required in high-noise discrete MRA.

2.2. Algorithmic Framework

The proposed recovery procedure (Algorithm 2.1) consists of three steps:

Estimate $\Psi$ : Compute the sample autocorrelation of the Fourier-transformed observations and subtract the known noise covariance. A regularized estimator is used to handle small values in the denominator.
Estimate $\hat{f}$ : Plug the estimated $\Psi$ into the generalized Kotlarski formula to recover $\hat{f}$ .
Deconvolve: Apply an inverse Fourier transform with a regularization kernel (bandwidth $h$ ) to recover the spatial signal $\hat{f}$ .

2.3. Extension to Vanishing Fourier Transforms

A significant limitation of standard Kotlarski-based approaches is the requirement that $\hat{f}$ be non-vanishing. The paper extends the methodology to handle signals where $\hat{f}$ has zeros (Algorithm 4.1). This involves:

Estimating the locations of the zeros of $\hat{f}$ by analyzing the zeros of the derivative of the empirical power spectrum.
Modifying the Kotlarski integral to exclude neighborhoods around these estimated zeros.
Using a generalized formula that accounts for the sign changes across the zeros.

3. Key Contributions

Functional Formulation and Connection to Deconvolution: The paper formally links functional MRA to deconvolution with replicated measurements, leveraging Kotlarski's identity to provide a new identification result for signal recovery from second-order statistics.
Multivariate Extension: The authors extend Kotlarski's formula (previously established for univariate or specific Hilbert space settings) to arbitrary dimensions $d$ , providing a constructive estimator for multidimensional signals.
Handling Vanishing Frequencies: The paper addresses the case where the signal's Fourier transform vanishes, a scenario where standard spectral methods fail. It provides a stable algorithm (Algorithm 4.1) and theoretical guarantees for this more general class of signals.
Theoretical Recovery Guarantees:
- Error Bounds: The paper derives high-probability error bounds for the estimator in both the Fourier and spatial ( $L_\infty$ ) domains.
- Sample Complexity: The analysis characterizes the sample complexity $N$ in terms of interpretable model parameters: the signal smoothness ( $\beta$ ), noise variance ( $\sigma$ ), and noise correlation lengthscale ( $\lambda$ ).
- High-Noise Regime: In the high-noise regime, the paper shows that $N \gtrsim \sigma^4$ samples are sufficient for recovery, matching the best-known rates for discrete MRA with aperiodic shifts, but without the restrictive assumptions of discrete models.
Robustness to Continuous Shifts: Unlike discrete spectral algorithms that rely on the assumption that shifts occur exactly on a grid (cyclic shifts), the proposed functional approach remains stable when shifts follow a continuous distribution, a common scenario in physical applications like cryo-EM.

4. Results and Numerical Validation

The paper validates the proposed approach through numerical experiments on four signal types:

Ordinary Smooth: Linear and cubic splines (satisfying non-vanishing assumptions).
Super Smooth: Gabor wavelets (exponential decay in frequency).
Vanishing Frequencies: A Gaussian mixture model (satisfying the vanishing Fourier transform assumptions).

Key Findings:

Sample Complexity: The empirical error decay rates align with the theoretical predictions, showing that smoother signals (higher $\beta$ ) allow for faster error decay.
Noise Parameters: The algorithms demonstrate robustness to high noise levels ( $\sigma$ ) and small correlation lengthscales ( $\lambda$ ). The sample complexity scales as $N \sim \sigma^4$ and $N \sim \log(\lambda^{-d})$ , consistent with the theoretical corollaries.
Comparison with Spectral Algorithms: The proposed algorithms significantly outperform the state-of-the-art spectral algorithm (based on second moments) from [2] in several scenarios:
- High Noise: The spectral algorithm's performance degrades rapidly as noise increases, whereas the deconvolution approach remains stable.
- Continuous Shifts: When shifts are drawn from a continuous distribution (violating the discrete cyclic assumption), the spectral algorithm fails, while the proposed method succeeds.
- Vanishing Frequencies: The spectral algorithm cannot theoretically handle signals with vanishing Fourier transforms, whereas Algorithm 4.1 successfully recovers them.

5. Significance and Claims

The paper claims that its primary significance lies in providing a stable, theoretically grounded framework for functional MRA that overcomes the limitations of discrete models. By framing MRA as a deconvolution problem, the authors:

Avoid the "blow-up" of noise variance associated with increasing discretization levels in discrete models.
Enable recovery guarantees for non-bandlimited signals and signals with vanishing Fourier transforms.
Demonstrate that second-order statistics are sufficient for recovery in high-noise regimes without requiring the restrictive structural assumptions (e.g., sparsity or specific algebraic sets) often needed in discrete MRA.

The authors emphasize that while their theoretical rates may be conservative compared to empirical performance, the approach offers a robust alternative to existing methods, particularly in applications involving continuous symmetries and correlated noise, such as structural biology and imaging.