File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: A Unified Approach to Synchronization Problems over Subgroups of the Orthogonal Group

TitleA Unified Approach to Synchronization Problems over Subgroups of the Orthogonal Group
Authors
Liu, HKYue, MCSo, AMC
Keywords(Special) orthogonal matrix
Cyclic group
Error bound
Estimation error
Generalized power method
Group synchronization
Metric entropy
Permutation matrix
Issue Date1-Sep-2023
PublisherElsevier
Citation
Applied and Computational Harmonic Analysis, 2023, v. 66, p. 320-372 How to Cite?
DOI: http://dx.doi.org/10.1016/j.acha.2023.05.002
Abstract

The problem of synchronization over a group G aims to estimate a collection of group elements G∗1,…,G∗n∈G based on noisy observations of a subset of all pairwise ratios of the form G∗iG∗j−1. Such a problem has gained much attention recently and finds many applications across a wide range of scientific and engineering areas. In this paper, we consider the class of synchronization problems in which the group is a closed subgroup of the orthogonal group. This class covers many group synchronization problems that arise in practice. Our contribution is fivefold. First, we propose a unified approach for solving this class of group synchronization problems, which consists of a suitable initialization step and an iterative refinement step based on the generalized power method, and show that it enjoys a strong theoretical guarantee on the estimation error under certain assumptions on the group, measurement graph, noise, and initialization. Second, we formulate two geometric conditions that are required by our approach and show that they hold for various practically relevant subgroups of the orthogonal group. The conditions are closely related to the error-bound geometry of the subgroup — an important notion in optimization. Third, we verify the assumptions on the measurement graph and noise for standard random graph and random matrix models. Fourth, based on the classic notion of metric entropy, we develop and analyze a novel spectral-type estimator. Finally, we show via extensive numerical experiments that our proposed non-convex approach outperforms existing approaches in terms of computational speed, scalability, and/or estimation error.


Persistent Identifierhttp://hdl.handle.net/10722/331930
ISSN
1063-5203
2023 Impact Factor: 2.6
2023 SCImago Journal Rankings: 2.231
ISI Accession Number ID
WOS:001026188100001

 

DC FieldValueLanguage
dc.contributor.authorLiu, HK-
dc.contributor.authorYue, MC-
dc.contributor.authorSo, AMC-
dc.date.accessioned2023-09-28T04:59:41Z-
dc.date.available2023-09-28T04:59:41Z-
dc.date.issued2023-09-01-
dc.identifier.citationApplied and Computational Harmonic Analysis, 2023, v. 66, p. 320-372-
dc.identifier.issn1063-5203-
dc.identifier.urihttp://hdl.handle.net/10722/331930-
dc.description.abstract<p>The problem of synchronization over a group G aims to estimate a collection of group elements G∗1,…,G∗n∈G based on noisy observations of a subset of all pairwise ratios of the form G∗iG∗j−1. Such a problem has gained much attention recently and finds many applications across a wide range of scientific and engineering areas. In this paper, we consider the class of synchronization problems in which the group is a closed subgroup of the <a href="https://www.sciencedirect.com/topics/mathematics/orthogonal-group" title="Learn more about orthogonal group from ScienceDirect's AI-generated Topic Pages">orthogonal group</a>. This class covers many group synchronization problems that arise in practice. Our contribution is fivefold. First, we propose a unified approach for solving this class of group synchronization problems, which consists of a suitable initialization step and an iterative refinement step based on the generalized power method, and show that it enjoys a strong theoretical guarantee on the estimation error under certain assumptions on the group, measurement graph, noise, and initialization. Second, we formulate two geometric conditions that are required by our approach and show that they hold for various practically relevant subgroups of the <a href="https://www.sciencedirect.com/topics/mathematics/orthogonal-group" title="Learn more about orthogonal group from ScienceDirect's AI-generated Topic Pages">orthogonal group</a>. The conditions are closely related to the error-bound geometry of the subgroup — an important notion in optimization. Third, we verify the assumptions on the measurement graph and noise for standard random graph and random matrix models. Fourth, based on the classic notion of <a href="https://www.sciencedirect.com/topics/mathematics/metric-entropy" title="Learn more about metric entropy from ScienceDirect's AI-generated Topic Pages">metric entropy</a>, we develop and analyze a novel spectral-type estimator. Finally, we show via extensive numerical experiments that our proposed non-convex approach outperforms existing approaches in terms of computational speed, scalability, and/or estimation error.<br></p>-
dc.languageeng-
dc.publisherElsevier-
dc.relation.ispartofApplied and Computational Harmonic Analysis-
dc.subject(Special) orthogonal matrix-
dc.subjectCyclic group-
dc.subjectError bound-
dc.subjectEstimation error-
dc.subjectGeneralized power method-
dc.subjectGroup synchronization-
dc.subjectMetric entropy-
dc.subjectPermutation matrix-
dc.titleA Unified Approach to Synchronization Problems over Subgroups of the Orthogonal Group-
dc.typeArticle-
dc.identifier.doi10.1016/j.acha.2023.05.002-
dc.identifier.scopuseid_2-s2.0-85162260652-
dc.identifier.volume66-
dc.identifier.spage320-
dc.identifier.epage372-
dc.identifier.eissn1096-603X-
dc.identifier.isiWOS:001026188100001-
dc.identifier.issnl1063-5203-

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats