Angular synchronization by eigenvectors and semidefinite programming

DOI10.1016/j.acha.2010.02.001zbMath1206.90116arXiv0905.3174OpenAlexW2143703915WikidataQ34414976 ScholiaQ34414976MaRDI QIDQ617701

Amit Singer

Publication date: 13 January 2011

Published in: Applied and Computational Harmonic Analysis (Search for Journal in Brave)

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

zbMATH Keywords

recovery algorithm Goemans-Williamson algorithm

Mathematics Subject Classification ID

Semidefinite programming (90C22) Mathematical programming (90C99)

Related Items

Continuous symmetry breaking along the Nishimori line, Maximum A Posteriori Inference of Random Dot Product Graphs via Conic Programming, Iterative algorithm for discrete structure recovery, Noisy dynamic simulations in the presence of symmetry: data alignment and model reduction, Vector diffusion maps and the connection Laplacian, Fast Phase Retrieval from Local Correlation Measurements, An extension of the angular synchronization problem to the heterogeneous setting, Near-optimal performance bounds for orthogonal and permutation group synchronization via spectral methods, Approximating the little Grothendieck problem over the orthogonal and unitary groups, Synchronization over Cartan Motion Groups via Contraction, A multiplicative weights update algorithm for MINLP, Improved Performance Guarantees for Orthogonal Group Synchronization via Generalized Power Method, On recovery guarantees for angular synchronization, Distributed methods for synchronization of orthogonal matrices over graphs, Optimal rates of estimation for multi-reference alignment, Magnetic eigenmaps for the visualization of directed networks, Joint Community Detection and Rotational Synchronization via Semidefinite Programming, On connections between amplitude flow and error reduction for phase retrieval and ptychography, Lie PCA: density estimation for symmetric manifolds, Solving orthogonal group synchronization via convex and low-rank optimization: tightness and landscape analysis, Cohomology of Cryo-Electron Microscopy, A survey of structure from motion., Detection of core–periphery structure in networks using spectral methods and geodesic paths, Distance geometry and data science, Rejoinder on: ``Distance geometry and data science, Local2global: a distributed approach for scaling representation learning on graphs, Cycle-based formulations in distance geometry, Lagrangian Duality in Complex Pose Graph Optimization, A unified approach to synchronization problems over subgroups of the orthogonal group, Synchronization problems in computer vision with closed-form solutions, Unnamed Item, Unnamed Item, Robust Phase Retrieval Algorithm for Time-Frequency Structured Measurements, Entrywise eigenvector analysis of random matrices with low expected rank, A Spectral Method for Joint Community Detection and Orthogonal Group Synchronization, The noise-sensitivity phase transition in spectral group synchronization over compact groups, Localization in 1D non-parametric latent space models from pairwise affinities, Phase transitions in semidefinite relaxations, Near-optimal bounds for generalized orthogonal Procrustes problem via generalized power method, Estimation under group actions: recovering orbits from invariants, Local convexity of the TAP free energy and AMP convergence for \(\mathbb{Z}_2\)-synchronization, Power spectrum unbiasing for dilation-invariant multi-reference alignment, A graphic structure based branch-and-bound algorithm for complex quadratic optimization and applications to magnitude least-square problem, On the Estimation Performance and Convergence Rate of the Generalized Power Method for Phase Synchronization, Rates of estimation for high-dimensional multireference alignment, Stochastic Model-Based Minimization of Weakly Convex Functions, Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization, Concentration of the Kirchhoff index for Erdős-Rényi graphs, The geometry of synchronization problems and learning group actions, Tightness of a New and Enhanced Semidefinite Relaxation for MIMO Detection, Notes on computational-to-statistical gaps: predictions using statistical physics, TAP free energy, spin glasses and variational inference, Stable optimizationless recovery from phaseless linear measurements, Uniform Bounds for Invariant Subspace Perturbations, Near-Optimal Bounds for Phase Synchronization, Lasserre Hierarchy for Large Scale Polynomial Optimization in Real and Complex Variables, Memory-Efficient Structured Convex Optimization via Extreme Point Sampling, Unnamed Item, Unnamed Item, Random Laplacian matrices and convex relaxations, New error measures and methods for realizing protein graphs from distance data, Tightness of the maximum likelihood semidefinite relaxation for angular synchronization, Preface: Special issue dedicated to distance geometry, Ranking and Sparsifying a Connection Graph, Orientability and diffusion maps, A Local Clustering Algorithm for Connection Graphs, Penalized semidefinite programming for quadratically-constrained quadratic optimization, Graph connection Laplacian methods can be made robust to noise, Phase recovery, MaxCut and complex semidefinite programming, Subspace estimation from unbalanced and incomplete data matrices: \({\ell_{2,\infty}}\) statistical guarantees, Preface, Optimality and sub-optimality of PCA. I: Spiked random matrix models, Hermitian Laplacians and a Cheeger Inequality for the Max-2-Lin Problem, Toward a spectral theory of cellular sheaves, Bridging convex and nonconvex optimization in robust PCA: noise, outliers and missing data, A cycle-based formulation for the distance geometry problem, Joint image formation and two-dimensional autofocusing for synthetic aperture radar data, Nonconvex Phase Synchronization, Group synchronization on grids, Projection-based model reduction with dynamically transformed modes, Multi-Reference Alignment in High Dimensions: Sample Complexity and Phase Transition, Unsupervised particle sorting for high-resolution single-particle cryo-EM, Non-unique games over compact groups and orientation estimation in cryo-EM, Global Registration of Multiple Point Clouds Using Semidefinite Programming, Robust group synchronization via cycle-edge message passing, Orthogonal Trace-Sum Maximization: Tightness of the Semidefinite Relaxation and Guarantee of Locally Optimal Solutions, Spectral Synchronization of Multiple Views in SE(3), The Sample Complexity of Multireference Alignment

Uses Software

Cites Work