TY - JOUR

T1 - Estimation under group actions

T2 - Recovering orbits from invariants

AU - Bandeira, Afonso S.

AU - Blum-Smith, Ben

AU - Kileel, Joe

AU - Niles-Weed, Jonathan

AU - Perry, Amelia

AU - Wein, Alexander S.

N1 - Publisher Copyright:
© 2023 Elsevier Inc.

PY - 2023/9

Y1 - 2023/9

N2 - We study a class of orbit recovery problems in which we observe independent copies of an unknown element of Rp, each linearly acted upon by a random element of some group (such as Z/p or SO(3)) and then corrupted by additive Gaussian noise. We prove matching upper and lower bounds on the number of samples required to approximately recover the group orbit of this unknown element with high probability. These bounds, based on quantitative techniques in invariant theory, give a precise correspondence between the statistical difficulty of the estimation problem and algebraic properties of the group. Furthermore, we give computer-assisted procedures to certify these properties that are computationally efficient in many cases of interest. The model is motivated by geometric problems in signal processing, computer vision, and structural biology, and applies to the reconstruction problem in cryo-electron microscopy (cryo-EM), a problem of significant practical interest. Our results allow us to verify (for a given problem size) that if cryo-EM images are corrupted by noise with variance σ2, the number of images required to recover the molecule structure scales as σ6. We match this bound with a novel (albeit computationally expensive) algorithm for ab initio reconstruction in cryo-EM, based on invariant features of degree at most 3. We further discuss how to recover multiple molecular structures from mixed (or heterogeneous) cryo-EM samples.

AB - We study a class of orbit recovery problems in which we observe independent copies of an unknown element of Rp, each linearly acted upon by a random element of some group (such as Z/p or SO(3)) and then corrupted by additive Gaussian noise. We prove matching upper and lower bounds on the number of samples required to approximately recover the group orbit of this unknown element with high probability. These bounds, based on quantitative techniques in invariant theory, give a precise correspondence between the statistical difficulty of the estimation problem and algebraic properties of the group. Furthermore, we give computer-assisted procedures to certify these properties that are computationally efficient in many cases of interest. The model is motivated by geometric problems in signal processing, computer vision, and structural biology, and applies to the reconstruction problem in cryo-electron microscopy (cryo-EM), a problem of significant practical interest. Our results allow us to verify (for a given problem size) that if cryo-EM images are corrupted by noise with variance σ2, the number of images required to recover the molecule structure scales as σ6. We match this bound with a novel (albeit computationally expensive) algorithm for ab initio reconstruction in cryo-EM, based on invariant features of degree at most 3. We further discuss how to recover multiple molecular structures from mixed (or heterogeneous) cryo-EM samples.

KW - Applications of commutative algebra

KW - Applications of invariant theory

KW - Applications of lie groups

KW - Biomedical imaging

KW - Signal processing

KW - Statistical aspects of information theory

UR - http://www.scopus.com/inward/record.url?scp=85162197362&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85162197362&partnerID=8YFLogxK

U2 - 10.1016/j.acha.2023.06.001

DO - 10.1016/j.acha.2023.06.001

M3 - Article

AN - SCOPUS:85162197362

SN - 1063-5203

VL - 66

SP - 236

EP - 319

JO - Applied and Computational Harmonic Analysis

JF - Applied and Computational Harmonic Analysis

ER -