Multireference alignment using semidefinite programming
From MaRDI portal
Abstract: The multireference alignment problem consists of estimating a signal from multiple noisy shifted observations. Inspired by existing Unique-Games approximation algorithms, we provide a semidefinite program (SDP) based relaxation which approximates the maximum likelihood estimator (MLE) for the multireference alignment problem. Although we show that the MLE problem is Unique-Games hard to approximate within any constant, we observe that our poly-time approximation algorithm for the MLE appears to perform quite well in typical instances, outperforming existing methods. In an attempt to explain this behavior we provide stability guarantees for our SDP under a random noise model on the observations. This case is more challenging to analyze than traditional semi-random instances of Unique-Games: the noise model is on vertices of a graph and translates into dependent noise on the edges. Interestingly, we show that if certain positivity constraints in the SDP are dropped, its solution becomes equivalent to performing phase correlation, a popular method used for pairwise alignment in imaging applications. Finally, we show how symmetry reduction techniques from matrix representation theory can simplify the analysis and computation of the SDP, greatly decreasing its computational cost.
Recommendations
- Super-resolution multi-reference alignment
- Wavelet invariants for statistically robust multi-reference alignment
- The projected power method: an efficient algorithm for joint alignment from pairwise differences
- Multi-reference alignment in high dimensions: sample complexity and phase transition
- Tightness of the maximum likelihood semidefinite relaxation for angular synchronization
Cites work
- (Leveled) fully homomorphic encryption without bootstrapping
- A hierarchy of polynomial time lattice basis reduction algorithms
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- Bounds for Width Two Branching Programs
- Efficient Fully Homomorphic Encryption from (Standard) LWE
- Evaluating Branching Programs on Encrypted Data
- Fully homomorphic encryption using ideal lattices
- Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP
- Homomorphic encryption from learning with errors: conceptually-simpler, asymptotically-faster, attribute-based
- scientific article; zbMATH DE number 1559544 (Why is no real title available?)
- New lattice-based cryptographic constructions
- On lattices, learning with errors, random linear codes, and cryptography
- On lattices, learning with errors, random linear codes, and cryptography
- Pseudorandom knapsacks and the sample complexity of LWE search-to-decision reductions
- Public-key cryptosystems from the worst-case shortest vector problem
- Toward basing fully homomorphic encryption on worst-case hardness
- Trapdoors for hard lattices and new cryptographic constructions
- Trapdoors for lattices: simpler, tighter, faster, smaller
Cited in
(30)- Rank-one multi-reference factor analysis
- Iterative algorithm for discrete structure recovery
- Optimal rates of estimation for multi-reference alignment
- The noise-sensitivity phase transition in spectral group synchronization over compact groups
- A representation theory perspective on simultaneous alignment and classification
- The geometry of synchronization problems and learning group actions
- Generalized shapes and point sets correspondence and registration
- Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems
- The projected power method: an efficient algorithm for joint alignment from pairwise differences
- Multi-reference alignment in high dimensions: sample complexity and phase transition
- Non-unique games over compact groups and orientation estimation in cryo-EM
- The sample complexity of multireference alignment
- Wavelet invariants for statistically robust multi-reference alignment
- scientific article; zbMATH DE number 7626745 (Why is no real title available?)
- Multi-target detection with application to cryo-electron microscopy
- Tightness of the maximum likelihood semidefinite relaxation for angular synchronization
- Sparse multi-reference alignment: phase retrieval, uniform uncertainty principles and the beltway problem
- Estimation under group actions: recovering orbits from invariants
- Power spectrum unbiasing for dilation-invariant multi-reference alignment
- Rates of estimation for high-dimensional multireference alignment
- Orbit recovery for band-limited functions
- Non-degenerate rigid alignment in a patch framework
- The stability of generalized phase retrieval problem over compact groups
- The reflection-invariant bispectrum: signal recovery in the dihedral model
- Robust Detection of Lead-Lag Relationships in Lagged Multi-Factor Models
- Functions on symmetric matrices and point clouds via lightweight invariant features from Galois theory
- Generalized orthogonal Procrustes problem under arbitrary adversaries
- Spectral methods from tensor networks
- Circular trace reconstruction
- Computational lower bounds for multi-frequency group synchronization
This page was built for publication: Multireference alignment using semidefinite programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2988900)
