The Projected Power Method: An Efficient Algorithm for Joint Alignment from Pairwise Differences

Yuxin Chen, Emmanuel J. Candès

Type: Preprint

Publication Date: 2016-01-01

Citations: 25

DOI: https://doi.org/10.48550/arxiv.1609.05820

View Publication

Locations

arXiv (Cornell University) - View - PDF
DataCite API - View

Similar Works

Action	Title	Year	Authors
+ PDF Chat	The Projected Power Method: An Efficient Algorithm for Joint Alignment from Pairwise Differences	2018	Yuxin Chen Emmanuel J. Candès
+	Projection-free Graph-based Classifier Learning using Gershgorin Disc Perfect Alignment	2021	Cheng Yang Gene Cheung Wai-Tian Tan Guangtao Zhai
+ PDF Chat	Near-optimal bounds for generalized orthogonal Procrustes problem via generalized power method	2023	Shuyang Ling
+	Optimal Learning of Joint Alignments with a Faulty Oracle	2019	Kasper Green Larsen Michael Mitzenmacher Charalampos E. Tsourakakis
+	Near-Optimal Bounds for Generalized Orthogonal Procrustes Problem via Generalized Power Method	2021	Shuyang Ling
+ PDF Chat	Graph Matching via convex relaxation to the simplex	2024	Ernesto Araya Hemant Tyagi
+ PDF Chat	Joint Alignment From Pairwise Differences with a Noisy Oracle	2020	Charalampos E. Tsourakakis Michael Mitzenmacher
+ PDF Chat	Reconstructing Point Sets From Distance Distributions	2021	Shuai Huang Ivan Dokmanić
+	A Novel and Optimal Spectral Method for Permutation Synchronization	2023	Duc T. Nguyen Anderson Ye Zhang
+ PDF Chat	Multi-Reference Alignment in High Dimensions: Sample Complexity and Phase Transition	2021	Elad Romanov Tamir Bendory Or Ordentlich
+	DS++: A flexible, scalable and provably tight relaxation for matching problems	2017	Nadav Dym Haggai Maron Yaron Lipman
+	DS++: A flexible, scalable and provably tight relaxation for matching problems	2017	Nadav Dym Haggai Maron Yaron Lipman
+ PDF Chat	Optimal Learning of Joint Alignments with a Faulty Oracle	2020	Kasper Green Larsen Michael Mitzenmacher Charalampos E. Tsourakakis
+ PDF Chat	Variable Substitution and Bilinear Programming for Aligning Partially Overlapping Point Sets	2024	Wei Lian Zhesen Cui Fei Ma Hang Pan Wangmeng Zuo
+ PDF Chat	Sparsity-Exploiting Distributed Projections onto a Simplex	2023	Yongzheng Dai Chen Chen
+	MAP Estimation of Semi-Metric MRFs via Hierarchical Graph Cuts	2012	Manish Kumar Daphne Koller
+ PDF Chat	A Hybrid Semidefinite and Bilinear Programming Approach to Aligning Partially Overlapping Point Sets	2024	Wei Lian Fei Ma Zhesen Cui Hang Pan
+ PDF Chat	Optimal Learning of Joint Alignments with a Faulty Oracle	2020	Kasper Green Larsen Michael Mitzenmacher Charalampos E. Tsourakakis
+	Solving Orthogonal Group Synchronization via Convex and Low-Rank Optimization: Tightness and Landscape Analysis	2020	Shuyang Ling
+	Optimal scaling by alternating length-constrained nonnegative least squares, with application to distance-based analysis	2000	Patrick J. F. Groenen Bart-Jan van Os Jacqueline J. Meulman

Works That Cite This (22)

Action	Title	Year	Authors
+	Optimal rates of estimation for multi-reference alignment	2017	Afonso S. Bandeira Philippe Rigollet Jonathan Weed
+	Phase Transitions of Spectral Initialization for High-Dimensional Nonconvex Estimation	2017	Yue M. Lu Gen Li
+ PDF Chat	Spectral method and regularized MLE are both optimal for top-$K$ ranking	2019	Yuxin Chen Jianqing Fan Cong Ma Kaizheng Wang
+ PDF Chat	Near-Optimal Bounds for Phase Synchronization	2018	Yiqiao Zhong Nicolas Boumal
+	Non-Convex Phase Retrieval From STFT Measurements	2017	Tamir Bendory Yonina C. Eldar Nicolas Boumal
+ PDF Chat	Path-Invariant Map Networks	2019	Zaiwei Zhang Zhenxiao Liang Lemeng Wu Xiaowei Zhou Qixing Huang
+	Path-Invariant Map Networks	2018	Zaiwei Zhang Zhenxiao Liang Lemeng Wu Xiaowei Zhou Qixing Huang
+	Global Guarantees for Enforcing Deep Generative Priors by Empirical Risk	2019	Paul Hand Vladislav Voroninski
+	Median-Truncated Nonconvex Approach for Phase Retrieval With Outliers	2018	Huishuai Zhang Yuejie Chi Yingbin Liang
+	A representation theory perspective on simultaneous alignment and classification	2019	Roy R. Lederman Amit Singer

Works Cited by This (24)

Action	Title	Year	Authors
+	Finding Dense Clusters via "Low Rank + Sparse" Decomposition	2011	Samet Oymak Babak Hassibi
+	Community detection in sparse networks via Grothendieck's inequality	2014	Olivier Guédon Roman Vershynin
+	Achieving Exact Cluster Recovery Threshold via Semidefinite Programming: Extensions	2015	Bruce Hajek Yihong Wu Jiaming Xu
+	An Introduction to Matrix Concentration Inequalities	2015	Joel A. Tropp
+	Stochastic Block Model and Community Detection in the Sparse Graphs: A spectral algorithm with optimal rate of recovery	2015	Peter Chin Anup Rao Van Vu
+	Cone-Constrained Principal Component Analysis	2014	Yash Deshpande Andrea Montanari Émile Richard
+	When Are Nonconvex Problems Not Scary?	2015	Ju Sun Qing Qu John Wright
+ PDF Chat	Robust principal component analysis?	2011	Emmanuel J. Candès Xiaodong Li Yi Ma John Wright
+	Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems	2015	Yuxin Chen Emmanuel J. Candès
+	Kaczmarz Method for Solving Quadratic Equations	2016	Yuejie Chi Yue M. Lu