Near-optimal performance bounds for orthogonal and permutation group synchronization via spectral methods
From MaRDI portal
Publication:2155796
DOI10.1016/j.acha.2022.02.003zbMath1492.94033arXiv2008.05341OpenAlexW3048770996MaRDI QIDQ2155796
Publication date: 15 July 2022
Published in: Applied and Computational Harmonic Analysis (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2008.05341
signal processingspectral methodsobject matchingeigenvector perturbationorthogonal/permutation group synchronization
Semidefinite programming (90C22) Nonconvex programming, global optimization (90C26) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)
Related Items
Improved Performance Guarantees for Orthogonal Group Synchronization via Generalized Power Method, Joint Community Detection and Rotational Synchronization via Semidefinite Programming, Solving orthogonal group synchronization via convex and low-rank optimization: tightness and landscape analysis, Efficient joint object matching via linear programming, A unified approach to synchronization problems over subgroups of the orthogonal group, A Spectral Method for Joint Community Detection and Orthogonal Group Synchronization, Near-optimal bounds for generalized orthogonal Procrustes problem via generalized power method, Rates of estimation for high-dimensional multireference alignment
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Tightness of the maximum likelihood semidefinite relaxation for angular synchronization
- The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices
- Angular synchronization by eigenvectors and semidefinite programming
- User-friendly tail bounds for sums of random matrices
- Eigenvectors of random matrices: A survey
- The largest eigenvalues of finite rank deformation of large Wigner matrices: Convergence and nonuniversality of the fluctuations
- Random perturbation of low rank matrices: improving classical bounds
- Optimality and sub-optimality of PCA. I: Spiked random matrix models
- Implicit regularization in nonconvex statistical estimation: gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution
- Entrywise eigenvector analysis of random matrices with low expected rank
- The noise-sensitivity phase transition in spectral group synchronization over compact groups
- Phase retrieval from local measurements: improved robustness via eigenvector-based angular synchronization
- Spectral method and regularized MLE are both optimal for top-\(K\) ranking
- Local minima and convergence in low-rank semidefinite programming
- Nonconvex Phase Synchronization
- Perturbation of Linear Forms of Singular Vectors Under Gaussian Noise
- Information Recovery From Pairwise Measurements
- New Perturbation Bounds for the Unitary Polar Factor
- An $\ell_{\infty}$ Eigenvector Perturbation Bound and Its Application to Robust Covariance Estimation
- The Projected Power Method: An Efficient Algorithm for Joint Alignment from Pairwise Differences
- A survey of structure from motion.
- On the Estimation Performance and Convergence Rate of the Generalized Power Method for Phase Synchronization
- Near-Optimal Bounds for Phase Synchronization
- High-Dimensional Probability
- Message‐Passing Algorithms for Synchronization Problems over Compact Groups
- A Performance Guarantee for Spectral Clustering
- Improved Performance Guarantees for Orthogonal Group Synchronization via Generalized Power Method
- Deterministic Guarantees for Burer‐Monteiro Factorizations of Smooth Semidefinite Programs
- MATHEMATICS FOR CRYO-ELECTRON MICROSCOPY
- Exact and stable recovery of rotations for robust synchronization
- On the Landscape of Synchronization Networks: A Perspective from Nonconvex Optimization
- Global Registration of Multiple Point Clouds Using Semidefinite Programming
- Spectral Synchronization of Multiple Views in SE(3)
- Recovering Low-Rank Matrices From Few Coefficients in Any Basis
- A Cheeger Inequality for the Graph Connection Laplacian
- The Rotation of Eigenvectors by a Perturbation. III
