More Like this

1. Optimal orthogonal group synchronization and rotation group synchronization

   https://doi.org/10.1093/imaiai/iaac022  

   Gao, Chao; Zhang, Anderson Y. (August 2022, Information and Inference: A Journal of the IMA)

   Abstract We study the statistical estimation problem of orthogonal group synchronization and rotation group synchronization. The model is $$Y_{ij} = Z_i^* Z_j^{*T} + \sigma W_{ij}\in{\mathbb{R}}^{d\times d}$$ where $$W_{ij}$$ is a Gaussian random matrix and $$Z_i^*$$ is either an orthogonal matrix or a rotation matrix, and each $$Y_{ij}$$ is observed independently with probability $$p$$. We analyze an iterative polar decomposition algorithm for the estimation of $Z^*$ and show it has an error of $$(1+o(1))\frac{\sigma ^2 d(d-1)}{2np}$$ when initialized by spectral methods. A matching minimax lower bound is further established that leads to the optimality of the proposed algorithm as it achieves the exact minimax risk. 

   more » « less
2. Synchronization Schemas

   https://doi.org/10.1145/3452021.3458317  

   Alur, Rajeev; Hilliard, Phillip; Ives, Zachary G.; Kallas, Konstantinos; Mamouras, Konstantinos; Niksic, Filip; Stanford, Caleb; Tannen, Val; Xue, Anton (June 2021, ACM Symposium on Principles of Database Systems)

   null (Ed.)
3. Synchronization Schemas

   Alur, R.; Hilliard, P; Ives, Z.G; Kallas, K; Mamouras, K; Niksic, F; Stanford, C.; Tannen, V; Xue, A. (January 2021, ACM Symposium on Principles of Database Systems)

   null (Ed.)
4. Learning Transformation Synchronization

   Huang, Xiangru; Liang, Zhenxiao; Zhou, Xiaowei; Xie, Yao; Guibas, Leonidas J.; Huang, Qixing (January 2019, Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition)
5. Normalized spectral map synchronization

   Shen, Yanyao; Huang, Qixing; srebro, Nati; Sanghavi, Sujay (January 2016, Advances in Neural Information Processing Systems 29 (NIPS 2016))

   The algorithmic advancement of synchronizing maps is important in order to solve a wide range of practice problems with possible large-scale dataset. In this paper, we provide theoretical justifications for spectral techniques for the map synchronization problem, i.e., it takes as input a collection of objects and noisy maps estimated between pairs of objects, and outputs clean maps between all pairs of objects. We show that a simple normalized spectral method that projects the blocks of the top eigenvectors of a data matrix to the map space leads to surprisingly good results. As the noise is modelled naturally as random permutation matrix, this algorithm NormSpecSync leads to competing theoretical guarantees as state-of-the-art convex optimization techniques, yet it is much more efficient. We demonstrate the usefulness of our algorithm in a couple of applications, where it is optimal in both complexity and exactness among existing methods. 

   more » « less