Sparse multi-reference alignment: phase retrieval, uniform uncertainty principles and the beltway problem

DOI10.1007/S10208-022-09584-6MaRDI QIDQ6072333zbMATH OpenOpenAlexFDO

Authors Subhroshekhar Ghosh, Philippe Rigollet

Publication date 13 October 2023

Published in Foundations of Computational Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2106.12996

zbMATH Keywords

beltway problemcombinatorial optimizationcryo electron microscopyFourier analysismulti reference alignmentphase retrievalprobabilistic methodsample complexitysparse signal processinguncertainty principles

Mathematics Subject Classification ID

Combinatorial aspects of difference sets (number-theoretic, group-theoretic, etc.) (05B10) Fourier coefficients, Fourier series of functions with special properties, special Fourier series (42A16) Probabilistic methods for one variable harmonic analysis (42A61) Asymptotic properties of parametric estimators (62F12) Statistics on algebraic and topological structures (62R99) Computational learning theory (68Q32) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Molecular structure (graph-theoretic methods, methods of differential topology, etc.) (92E10) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Information theory (general) (94A15)

Abstract: Motivated by cutting-edge applications like cryo-electron microscopy (cryo-EM), the Multi-Reference Alignment (MRA) model entails the learning of an unknown signal from repeated measurements of its images under the latent action of a group of isometries and additive noise of magnitude $sigma$. Despite significant interest, a clear picture for understanding rates of estimation in this model has emerged only recently, particularly in the high-noise regime $sigmagg1$ that is highly relevant in applications. Recent investigations have revealed a remarkable asymptotic sample complexity of order $sigm{a}^6$ for certain signals whose Fourier transforms have full support, in stark contrast to the traditional $sigm{a}^2$ that arise in regular models. Often prohibitively large in practice, these results have prompted the investigation of variations around the MRA model where better sample complexity may be achieved. In this paper, we show that sparse signals exhibit an intermediate $sigm{a}^4$ sample complexity even in the classical MRA model. Further, we characterise the dependence of the estimation rate on the support size $s$ as $O_p(1)$ and $O_p(s^{3.5})$ in the dilute and moderate regimes of sparsity respectively. Our techniques have implications for the problem of crystallographic phase retrieval, indicating a certain local uniqueness for the recovery of sparse signals from their power spectrum. Our results explore and exploit connections of the MRA estimation problem with two classical topics in applied mathematics: the beltway problem from combinatorial optimization, and uniform uncertainty principles from harmonic analysis. Our techniques include a certain enhanced form of the probabilistic method, which might be of general interest in its own right.

Cites work

• A counterexample to a theorem of S. Piccard
• Asymptotic Statistics
• Benchmark problems for phase retrieval
• Bispectrum Inversion With Application to Multireference Alignment
• Concentration inequalities. A nonasymptotic theory of independence
• Dihedral Multi-Reference Alignment
• Estimating a signal with noisy nuisance parameters
• From Bernoulli–Gaussian Deconvolution to Sparse Signal Restoration
• scientific article; zbMATH DE number 1194132 (Why is no real title available?)
• scientific article; zbMATH DE number 3036931 (Why is no real title available?)
• Maximum likelihood detection and estimation of Bernoulli - Gaussian processes
• Multi-reference alignment in high dimensions: sample complexity and phase transition
• Multireference Alignment Is Easier With an Aperiodic Translation Distribution
• Multireference alignment using semidefinite programming
• On sparse reconstruction from Fourier and Gaussian measurements
• Optimal rates of estimation for multi-reference alignment
• Phase retrieval via matrix completion
• Sparse Phase Retrieval: Uniqueness Guarantees and Recovery Algorithms
• Structure and randomness. Pages from year one of a mathematical blog
• Super Resolution Phase Retrieval for Sparse Signals
• The sample complexity of multireference alignment
• The uncertainty principle
• The uncertainty principle: A mathematical survey
• There Are No Further Counterexamples to S. Piccard's Theorem
• Toward a mathematical theory of the crystallographic phase retrieval problem

Cited in

(5)

• Maximum likelihood for high-noise group orbit estimation and single-particle cryo-EM
• The stability of generalized phase retrieval problem over compact groups
• Phase retrieval with semialgebraic and ReLU neural network priors
• Functional multireference alignment via deconvolution
• A transversality theorem for semi-algebraic sets with application to signal recovery from the second moment and cryo-EM

This page was built for publication: Sparse multi-reference alignment: phase retrieval, uniform uncertainty principles and the beltway problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6072333)