NONCONVEX PHASE SYNCHRONIZATION

被引:108
作者
Boumal, Nicolas [1 ]
机构
[1] Princeton Univ, Dept Math, Princeton, NJ 08544 USA
关键词
angular synchronization; nonconvex optimization; generalized power method; projected power method; sufficient optimality conditions; quadratically constrained quadratic programming; optimization on manifolds; SEMIDEFINITE; EIGENVECTORS; OPTIMIZATION; RETRIEVAL; RECOVERY;
D O I
10.1137/16M105808X
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
We estimate n phases (angles) from noisy pairwise relative phase measurements. The task is modeled as a nonconvex least-squares optimization problem. It was recently shown that this problem can be solved in polynomial time via convex relaxation, under some conditions on the noise. In this paper, under similar but more restrictive conditions, we show that a modified version of the power method converges to the global optimum. This is simpler and (empirically) faster than convex approaches. Empirically, they both succeed in the same regime. Further analysis shows that, in the same noise regime as previously studied, second-order necessary optimality conditions for this quadratically constrained quadratic program are also sufficient, despite nonconvexity.
引用
收藏
页码:2355 / 2377
页数:23
相关论文
共 50 条
[41]   On the Minimization of the Sum of Nonconvex Functions with Applications to Mathematical Programming [J].
Lara, Felipe ;
Yen, Le Hai .
JOURNAL OF GLOBAL OPTIMIZATION, 2025,
[42]   Distributed and Parallel ADMM for Structured Nonconvex Optimization Problem [J].
Wang, Xiangfeng ;
Yan, Junchi ;
Jin, Bo ;
Li, Wenhao .
IEEE TRANSACTIONS ON CYBERNETICS, 2021, 51 (09) :4540-4552
[43]   Multichannel Hankel Matrix Completion Through Nonconvex Optimization [J].
Zhang, Shuai ;
Hao, Yingshuai ;
Wang, Meng ;
Chow, Joe H. .
IEEE JOURNAL OF SELECTED TOPICS IN SIGNAL PROCESSING, 2018, 12 (04) :617-632
[44]   A Nonconvex Approach with Structural Priors for Restoring Underwater Images [J].
Awan, Hafiz Shakeel Ahmad ;
Mahmood, Muhammad Tariq .
MATHEMATICS, 2024, 12 (22)
[45]   A "Nonconvex plus Nonconvex" approach for image restoration with impulse noise removal [J].
Cui, Zhuo-Xu ;
Fan, Qibin .
APPLIED MATHEMATICAL MODELLING, 2018, 62 :254-271
[46]   ReSync: Riemannian Subgradient-based Robust Rotation Synchronization [J].
Liu, Huikang ;
Li, Xiao ;
So, Anthony Man-Cho .
ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS 36 (NEURIPS 2023), 2023,
[47]   Convexification of nonconvex functions and application to minimum and maximum principles for nonconvex sets [J].
Wu, CX ;
Cheng, LX ;
Ha, MH ;
Lee, ES .
COMPUTERS & MATHEMATICS WITH APPLICATIONS, 1996, 31 (07) :27-36
[48]   Velocity reconstruction with nonconvex optimization for low-velocity-encoding phase-contrast MRI [J].
Loecher, Michael ;
Ennis, Daniel B. .
MAGNETIC RESONANCE IN MEDICINE, 2018, 80 (01) :42-52
[49]   Efficient Algorithm for Nonconvex Minimization and Its Application to PM Regularization [J].
Li, Wen-Ping ;
Wang, Zheng-Ming ;
Deng, Ya .
IEEE TRANSACTIONS ON IMAGE PROCESSING, 2012, 21 (10) :4322-4333
[50]   HALF-LINEAR REGULARIZATION FOR NONCONVEX IMAGE RESTORATION MODELS [J].
Coll, Bartomeu ;
Duran, Joan ;
Sbert, Catalina .
INVERSE PROBLEMS AND IMAGING, 2015, 9 (02) :337-370