Near-optimal bounds for generalized orthogonal Procrustes problem via generalized power method

DOI10.1016/J.ACHA.2023.04.008MaRDI QIDQ6172167zbMATH OpenFDO

Authors Shuyang Ling

Publication date 19 July 2023

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

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

zbMATH Keywords

leave-one-out techniquenonconvex optimizationorthogonal Procrustes problemrandom matrixsemidefinite programming

Mathematics Subject Classification ID

Statistics (62-XX) Numerical analysis (65-XX)

Abstract: Given multiple point clouds, how to find the rigid transform (rotation, reflection, and shifting) such that these point clouds are well aligned? This problem, known as the generalized orthogonal Procrustes problem (GOPP), has found numerous applications in statistics, computer vision, and imaging science. While one commonly-used method is finding the least squares estimator, it is generally an NP-hard problem to obtain the least squares estimator exactly due to the notorious nonconvexity. In this work, we apply the semidefinite programming (SDP) relaxation and the generalized power method to solve this generalized orthogonal Procrustes problem. In particular, we assume the data are generated from a signal-plus-noise model: each observed point cloud is a noisy copy of the same unknown point cloud transformed by an unknown orthogonal matrix and also corrupted by additive Gaussian noise. We show that the generalized power method (equivalently alternating minimization algorithm) with spectral initialization converges to the unique global optimum to the SDP relaxation, provided that the signal-to-noise ratio is high. Moreover, this limiting point is exactly the least squares estimator and also the maximum likelihood estimator. In addition, we derive a block-wise estimation error for each orthogonal matrix and the underlying point cloud. Our theoretical bound is near-optimal in terms of the information-theoretic limit (only loose by a factor of the dimension and a log factor). Our results significantly improve the state-of-the-art results on the tightness of the SDP relaxation for the generalized orthogonal Procrustes problem, an open problem posed by Bandeira, Khoo, and Singer in 2014.

Cites work

• A feasible method for optimization with orthogonality constraints
• A geometric analysis of phase retrieval
• A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
• Angular synchronization by eigenvectors and semidefinite programming
• Approximating the little Grothendieck problem over the orthogonal and unitary groups
• Blind Deconvolution Using Convex Programming
• Community detection and stochastic block models: recent developments
• Deterministic guarantees for Burer-Monteiro factorizations of smooth semidefinite programs
• Efficient rounding for the noncommutative Grothendieck inequality
• Entrywise eigenvector analysis of random matrices with low expected rank
• Exact and stable recovery of rotations for robust synchronization
• Exact matrix completion via convex optimization
• Generalized Procrustes analysis
• Global registration of multiple point clouds using semidefinite programming
• Gradient descent with random initialization: fast global convergence for nonconvex phase retrieval
• High-dimensional probability. An introduction with applications in data science
• High-dimensional statistics. A non-asymptotic viewpoint
• scientific article; zbMATH DE number 49190 (Why is no real title available?)
• scientific article; zbMATH DE number 5223994 (Why is no real title available?)
• Implicit regularization in nonconvex statistical estimation: gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Local minima and convergence in low-rank semidefinite programming
• Mathematics for cryo-electron microscopy
• Matrix Completion From a Few Entries
• Moment inequalities for sums of random matrices and their applications in optimization
• Near-optimal bounds for phase synchronization
• Near-optimal performance bounds for orthogonal and permutation group synchronization via spectral methods
• New Perturbation Bounds for the Unitary Polar Factor
• Non-Iterative Rigid 2D/3D Point-Set Registration Using Semidefinite Programming
• Nonconvex phase synchronization
• On the estimation performance and convergence rate of the generalized power method for phase synchronization
• Optimality and sub-optimality of PCA. I: Spiked random matrix models
• Orthogonal Trace-Sum Maximization: Tightness of the Semidefinite Relaxation and Guarantee of Locally Optimal Solutions
• Perturbation bounds in connection with singular value decomposition
• Phase Retrieval by Alternating Minimization With Random Initialization
• Phase retrieval via matrix completion
• Phase retrieval via Wirtinger flow: theory and algorithms
• Procrustes Problems
• Random perturbation of low rank matrices: improving classical bounds
• Recovering Low-Rank Matrices From Few Coefficients in Any Basis
• Reducibility among combinatorial problems
• Scalable semidefinite programming
• SDPNAL+: a majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints
• SDPNAL+: A Matlab software for semidefinite programming with bound constraints (version 1.0)
• Solving orthogonal group synchronization via convex and low-rank optimization: tightness and landscape analysis
• Solving semidefinite-quadratic-linear programs using SDPT3
• The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices
• The generalized orthogonal Procrustes problem in the high noise regime
• The projected power method: an efficient algorithm for joint alignment from pairwise differences
• The Rotation of Eigenvectors by a Perturbation. III
• Three-dimensional structure determination from common lines in cryo-EM by eigenvectors and semidefinite programming
• Tightness of the maximum likelihood semidefinite relaxation for angular synchronization

Cited in

(4)

• Non-degenerate rigid alignment in a patch framework
• Tightness of SDP and Burer-Monteiro factorization for phase synchronization in a high-noise regime
• Generalized orthogonal Procrustes problem under arbitrary adversaries
• Local geometry determines global landscape in low-rank factorization for synchronization

This page was built for publication: Near-optimal bounds for generalized orthogonal Procrustes problem via generalized power method

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6172167)