Functional Multi-Reference Alignment via Deconvolution

O. Al-Ghattas, A. Little, D. Sanz-Alonso, M. Sweeney · 2025

Read Functional Multi-Reference Alignment via Deconvolution by O. Al-Ghattas, A. Little, D. Sanz-Alonso, M. Sweeney (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-12201.txt.

Introduction

Omar Al-Ghattas and three co-authors solve a signal alignment problem through an unexpected link to noise removal, in a 2025 paper. The task is to recover a signal from many shifted, noisy copies. Shifts are unknown, which makes direct averaging fail. Their functional framing exposes a bridge to a classic deconvolution formula. That formula recovers signals from second-order statistics of repeated measures.

The team extends the formula to higher dimensions. Signals whose spectra vanish in places get special treatment. New algorithms for alignment grow out of the bridge. Theory and numerical tests both support the approach. The work also adds to the deconvolution literature itself. Alignment problems arise in imaging and cryo-microscopy, where many noisy views of one object must be combined. A fresh route to the problem may widen the toolbox for such fields.

Catalog record

CREATORO. Al-Ghattas, A. Little, D. Sanz-Alonso, M. Sweeney
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE126 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-12201

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Functional Multi-Reference Alignment via Deconvolution O. Al-Ghattas, A. Little, D. Sanz-Alonso, M. Sweeney Abstract This paper studies the multi-reference alignment (MRA) problem of estimating a signal function from shifted, noisy observations. Our functional formulation reveals a new connection between MRA and deconvolution: the signal can be estimated from second-order statistics via Kotlarski’s formula, an important identification result in deconvolution with replicated measurements. To design our MRA algorithms, we extend Kotlarski’s formula to general dimension and study the estimation of signals with vanishing Fourier transform, thus also contributing to the deconvolution literature. We validate our deconvolution approach to MRA through both theory and numerical experiments. keywords Multi-reference alignment, deconvolution, Kotlarski’s formula, signal processing † † runningheads: Functional Multi-Reference Alignment via Deconvolution / O. Al-Ghattas, A. Little, D. Sanz-Alonso, and M. Sweeney MSC 62G05, 62M20, 92C55 1 Introduction 1.1 Aim This paper studies the functional multi-reference alignment (MRA) problem of estimating a signal function from shifted, noisy observations. We introduce two algorithms rooted in a new connection between MRA and deconvolution: in the Fourier domain, the signal can be estimated from second-order statistics via Kotlarski’s formula, a well-known identification result in deconvolution with replicated measurements [ 41 , 40 , 22 , 39 ] . In the process of developing our algorithms, we extend Kotlarski’s formula to multidimensional settings and investigate the estimation of signals with vanishing Fourier transform. To validate our deconvolution approach to MRA, we analyze the estimation error in both Fourier and spatial domains, studying the sample complexity in terms of interpretable model parameters, such as the variance and the lengthscale of the observation noise. As illustrated in Figure 1 , our algorithms can successfully recover a wide range of signals from highly noisy observations. Figure 1 : Performance of our algorithms in four illustrative examples. True signal (thick blue), representative observations (shadowed blue, drawn from a full sample of size 10^{5} ), and signal estimates (red). See Section 5 and Remark 35 for implementation details. 1.2 Literature review 1.2.1 Discrete MRA In the discrete formulation of the MRA problem, the goal is to recover an unknown signal vector f\in\mathbb{R}^{J} from N noisy, randomly shifted observations: \displaystyle y_{n}[j] \displaystyle=f\big[j-\zeta_{n}]+\eta_{n}[j],\qquad 1\leq j\leq J,\quad 1\leq n\leq N, (1) where translations of indices are defined modulo J . Each shift \zeta_{n} is drawn independently from a probability distribution on \{0,1,\ldots,J-1\} , and the noise vectors \eta_{1},\ldots,\eta_{N} are independent, isotropic Gaussian vectors with variance \sigma^{2} . The MRA model arises in a variety of applications, including structural biology and image processing [ 24 , 44 , 45 , 50 , 52 , 56 , 18 , 29 , 60 ] . In particular, it serves as a simplified model for cryo-electron microscopy (cryo-EM), where the goal is to reconstruct a molecular structure from noisy, randomly rotated projections. As noted in [ 9 ] , “[MRA] … represents a special case of cryo-EM, corresponding to the scenario in which the molecule’s axis of rotation is known, but its rotation angle is not.” More broadly, MRA belongs to a class of models where a latent signal is transformed by a group action and possibly projected or downsampled [ 10 , 3 , 16 ] . Numerous algorithmic strategies have been developed to solve MRA. When the noise level is moderate, synchronization -based methods —which estimate the shifts and then align the observations— are often effective [ 8 , 10 , 11 , 12 , 17 , 19 , 20 , 47 , 54 , 59 ] . However, synchronization fails in the high-noise regime, motivating alternative approaches such as expectation-maximization (EM) [ 2 , 23 , 7 ] , the method of moments [ 32 , 37 , 53 , 1 ] , and the method of invariants [ 8 , 14 , 21 , 35 , 34 ] . The identifiability and sample complexity of discrete MRA depend critically on the properties of the shift distribution. If the distribution is aperiodic , the signal f can be recovered from the first and second empirical moments using a spectral method, with sample complexity N\gtrsim\sigma^{4} [ 2 ] . In contrast, if the shift distribution is periodic —e.g., uniform on \{0,\ldots,J-1\} —higher-order moments are typically required. (An important exception is when the signal is sparse [ 15 , 31 , 30 ] ). A common approach in this case is to estimate the bispectrum of f (which requires N\gtrsim\sigma^{6} samples), and then invert it; see [ 46 ] for theoretical guarantees using Jennrich’s algorithm. Recent work [ 25 ] provides precise error bounds for bispectrum inversion with explicit dependence on signal length and frequency structure. The high-dimensional setting has also been studied: for instance, [ 49 ] shows that for Gaussian signals, a phase transition in sample complexity occurs at the threshold J/(\sigma^{2}\log J)=2. Closely related to the discrete MRA problem, and moving towards a functional formulation, one may consider estimating the Fourier coefficients f^{\text{ft}}[j], 1\leq j\leq J, of a band-limited signal function f from Fourier domain observations of the form y^{\text{ft}}_{n}[j]=e^{-ij\zeta_{n}}\,f^{\text{ft}}[j]+\eta^{\text{ft}}_{n}[j],\qquad 1\leq j\leq J,\qquad 1\leq n\leq N. This phase shift model has been studied for instance in [ 9 , 25 ] . 1.2.2 Functional MRA Our study of functional MRA is motivated by several limitations of the discrete formulation given in ( 1 ), both as a model for practical applications and in terms of its theoretical analysis. We outline these issues below. In many of the applications that motivate MRA, such as cryo-EM, the latent signal is more naturally modeled as a continuous function rather than a finite-dimensional vector. In such cases, it is important to understand how properties of the noise affect sample complexity independently of the discretization level J . For example, while the results in [ 25 ] are minimax optimal for the discrete model ( 1 ), their analysis does not extend meaningfully to the limit J\to\infty , as the limiting signal is not square-integrable. Similarly, the inversion guarantees in [ 46 ] degrade as the signal length J increases. Moreover, the white noise assumption in ( 1 ) forces the noise to blow up as J\to\infty , which in turn necessitates that the noise level \sigma\to 0 as J\to\infty for recovery to remain possible [ 49 , 25 ] . Beyond this technical issue, white noise is often an unrealistic modeling choice. In many applications, including cryo-EM, the noise is known to exhibit spatial correlations [ 33 , 13 , 36 ] . As resolution increases, the assumption that pixelwise noise is uncorrelated becomes increasingly implausible, and a Gaussian process model with short-range correlations (small lengthscale) may offer a more accurate representation. These limitations motivate us to recast ( 1 ) within a functional framework. This formulation not only accommodates natural smoothness assumptions on the underlying signal but also permits the exploitation of derivative information in the Fourier domain, which is central to our deconvolution methodology. In this vein, the functional model elucidates a deep connection between MRA and the classical statistical problem of deconvolution from replicated measurements [ 41 , 40 , 22 , 39 ] , wherein one seeks to identify the distribution of a latent variable from repeated, conditionally independent noisy observations —possibly under unknown

Read the complete text