Multireference alignment using semidefinite programming

DOI10.1145/2554797.2554839zbMath1364.94108arXiv1308.5256OpenAlexW2147554450MaRDI QIDQ2988900

Amit Singer, Afonso S. Bandeira, Andy Zhu, Moses Charikar

Publication date: 19 May 2017

Published in: Proceedings of the 5th conference on Innovations in theoretical computer science (Search for Journal in Brave)

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

zbMATH Keywords

semidefinite relaxationphase correlationmultireference alignmentunique-games

Mathematics Subject Classification ID

Asymptotic properties of parametric estimators (62F12) Semidefinite programming (90C22) Approximation methods and heuristics in mathematical programming (90C59) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Related Items

Iterative algorithm for discrete structure recovery ⋮ Optimal rates of estimation for multi-reference alignment ⋮ Sparse multi-reference alignment: phase retrieval, uniform uncertainty principles and the beltway problem ⋮ The noise-sensitivity phase transition in spectral group synchronization over compact groups ⋮ A representation theory perspective on simultaneous alignment and classification ⋮ 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 ⋮ Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems ⋮ The geometry of synchronization problems and learning group actions ⋮ Unnamed Item ⋮ Tightness of the maximum likelihood semidefinite relaxation for angular synchronization ⋮ Rank-one multi-reference factor analysis ⋮ Multi-target detection with application to cryo-electron microscopy ⋮ Generalized shapes and point sets correspondence and registration ⋮ 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

Cites Work

• Unnamed Item
• A hierarchy of polynomial time lattice basis reduction algorithms
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• (Leveled) fully homomorphic encryption without bootstrapping
• Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based
• Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller
• Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP
• Trapdoors for hard lattices and new cryptographic constructions
• Toward Basing Fully Homomorphic Encryption on Worst-Case Hardness
• Evaluating Branching Programs on Encrypted Data
• Bounds for Width Two Branching Programs
• Fully homomorphic encryption using ideal lattices
• Public-key cryptosystems from the worst-case shortest vector problem
• Pseudorandom Knapsacks and the Sample Complexity of LWE Search-to-Decision Reductions
• New lattice-based cryptographic constructions
• Efficient Fully Homomorphic Encryption from (Standard) LWE
• On lattices, learning with errors, random linear codes, and cryptography
• On lattices, learning with errors, random linear codes, and cryptography