Robust Group Synchronization via Quadratic Programming

Yunpeng Shi, Cole M Wyeth, Gilad Lerman
Proceedings of the 39th International Conference on Machine Learning, PMLR 162:20095-20105, 2022.

Abstract

We propose a novel quadratic programming formulation for estimating the corruption levels in group synchronization, and use these estimates to solve this problem. Our objective function exploits the cycle consistency of the group and we thus refer to our method as detection and estimation of structural consistency (DESC). This general framework can be extended to other algebraic and geometric structures. Our formulation has the following advantages: it can tolerate corruption as high as the information-theoretic bound, it does not require a good initialization for the estimates of group elements, it has a simple interpretation, and under some mild conditions the global minimum of our objective function exactly recovers the corruption levels. We demonstrate the competitive accuracy of our approach on both synthetic and real data experiments of rotation averaging.

Cite this Paper

BibTeX
@InProceedings{pmlr-v162-shi22g, title = {Robust Group Synchronization via Quadratic Programming}, author = {Shi, Yunpeng and Wyeth, Cole M and Lerman, Gilad}, booktitle = {Proceedings of the 39th International Conference on Machine Learning}, pages = {20095--20105}, year = {2022}, editor = {Chaudhuri, Kamalika and Jegelka, Stefanie and Song, Le and Szepesvari, Csaba and Niu, Gang and Sabato, Sivan}, volume = {162}, series = {Proceedings of Machine Learning Research}, month = {17--23 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v162/shi22g/shi22g.pdf}, url = {https://proceedings.mlr.press/v162/shi22g.html}, abstract = {We propose a novel quadratic programming formulation for estimating the corruption levels in group synchronization, and use these estimates to solve this problem. Our objective function exploits the cycle consistency of the group and we thus refer to our method as detection and estimation of structural consistency (DESC). This general framework can be extended to other algebraic and geometric structures. Our formulation has the following advantages: it can tolerate corruption as high as the information-theoretic bound, it does not require a good initialization for the estimates of group elements, it has a simple interpretation, and under some mild conditions the global minimum of our objective function exactly recovers the corruption levels. We demonstrate the competitive accuracy of our approach on both synthetic and real data experiments of rotation averaging.} }
Endnote
%0 Conference Paper %T Robust Group Synchronization via Quadratic Programming %A Yunpeng Shi %A Cole M Wyeth %A Gilad Lerman %B Proceedings of the 39th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2022 %E Kamalika Chaudhuri %E Stefanie Jegelka %E Le Song %E Csaba Szepesvari %E Gang Niu %E Sivan Sabato %F pmlr-v162-shi22g %I PMLR %P 20095--20105 %U https://proceedings.mlr.press/v162/shi22g.html %V 162 %X We propose a novel quadratic programming formulation for estimating the corruption levels in group synchronization, and use these estimates to solve this problem. Our objective function exploits the cycle consistency of the group and we thus refer to our method as detection and estimation of structural consistency (DESC). This general framework can be extended to other algebraic and geometric structures. Our formulation has the following advantages: it can tolerate corruption as high as the information-theoretic bound, it does not require a good initialization for the estimates of group elements, it has a simple interpretation, and under some mild conditions the global minimum of our objective function exactly recovers the corruption levels. We demonstrate the competitive accuracy of our approach on both synthetic and real data experiments of rotation averaging.
APA
Shi, Y., Wyeth, C.M. & Lerman, G.. (2022). Robust Group Synchronization via Quadratic Programming. Proceedings of the 39th International Conference on Machine Learning, in Proceedings of Machine Learning Research 162:20095-20105 Available from https://proceedings.mlr.press/v162/shi22g.html.

Related Material