March  2022, 4(1): 71-122. doi: 10.3934/fods.2021036

An extension of the angular synchronization problem to the heterogeneous setting

1. 

Department of Statistics and Mathematical Institute, University of Oxford, Oxford, UK

2. 

The Alan Turing Institute, London, UK

3. 

Inria, Univ. Lille, CNRS, UMR 8524, Laboratoire Paul Painlevé, F-59000

*Corresponding author: Mihai Cucuringu

Received  February 2021 Revised  September 2021 Published  March 2022 Early access  January 2022

Fund Project: This work was supported by EPSRC grant EP/N510129/1

Given an undirected measurement graph $ G = ([n], E) $, the classical angular synchronization problem consists of recovering unknown angles $ \theta_1, \dots, \theta_n $ from a collection of noisy pairwise measurements of the form $ (\theta_i - \theta_j) \mod 2\pi $, for each $ \{i, j\} \in E $. This problem arises in a variety of applications, including computer vision, time synchronization of distributed networks, and ranking from preference relationships. In this paper, we consider a generalization to the setting where there exist $ k $ unknown groups of angles $ \theta_{l, 1}, \dots, \theta_{l, n} $, for $ l = 1, \dots, k $. For each $ {\left\{{{i, j}}\right\}} \in E $, we are given noisy pairwise measurements of the form $ \theta_{\ell, i} - \theta_{\ell, j} $ for an unknown $ \ell \in \{1, 2, \ldots, k\} $. This can be thought of as a natural extension of the angular synchronization problem to the heterogeneous setting of multiple groups of angles, where the measurement graph has an unknown edge-disjoint decomposition $ G = G_1 \cup G_2 \ldots \cup G_k $, where the $ G_i $'s denote the subgraphs of edges corresponding to each group. We propose a probabilistic generative model for this problem, along with a spectral algorithm for which we provide a detailed theoretical analysis in terms of robustness against both sampling sparsity and noise. The theoretical findings are complemented by a comprehensive set of numerical experiments, showcasing the efficacy of our algorithm under various parameter regimes. Finally, we consider an application of bi-synchronization to the graph realization problem, and provide along the way an iterative graph disentangling procedure that uncovers the subgraphs $ G_i $, $ i = 1, \ldots, k $ which is of independent interest, as it is shown to improve the final recovery accuracy across all the experiments considered.

Citation: Mihai Cucuringu, Hemant Tyagi. An extension of the angular synchronization problem to the heterogeneous setting. Foundations of Data Science, 2022, 4 (1) : 71-122. doi: 10.3934/fods.2021036
References:
[1]

A. A. AminiA. ChenP. J. Bickel and E. Levina, Pseudo-likelihood methods for community detection in large sparse networks, Ann. Statist., 41 (2013), 2097-2122.  doi: 10.1214/13-AOS1138.

[2]

G. AnderssonL. Engebretsen and J. Håstad, A new way of using semidefinite programming with applications to linear equations mod $p$, J. Algorithms, 39 (2001), 162-204.  doi: 10.1006/jagm.2000.1154.

[3]

M. Arie-Nachimson, S. Z. Kovalsky, I. Kemelmacher-Shlizerman, A. Singer and R. Basri, Global motion estimation from point matches, 2012 Second International Conference on 3D Imaging, Modeling, Processing, Visualization Transmission, Zurich, Switzerland, 2012. doi: 10.1109/3DIMPVT.2012.46.

[4]

A. S. BandeiraN. Boumal and A. Singer, Tightness of the maximum likelihood semidefinite relaxation for angular synchronization, Math. Program., 163 (2017), 145-167.  doi: 10.1007/s10107-016-1059-6.

[5]

A. S. Bandeira, Y. Chen, R. R. Lederman and A. Singer, Non-unique games over compact groups and orientation estimation in cryo-EM, Inverse Problems, 36 (2020), 39pp. doi: 10.1088/1361-6420/ab7d2c.

[6]

A. S. BandeiraA. Perry and A. S. Wein, Notes on computational-to-statistical gaps: Predictions using statistical physics, Port. Math., 75 (2018), 159-186.  doi: 10.4171/PM/2014.

[7]

A. S. Bandeira and R. van Handel, Sharp nonasymptotic bounds on the norm of random matrices with independent entries, Ann. Probab., 44 (2016), 2479-2506.  doi: 10.1214/15-AOP1025.

[8]

A.-L. Barabási and R. Albert, Emergence of scaling in random networks, Science, 286 (1999), 509-512.  doi: 10.1126/science.286.5439.509.

[9]

A. I. Barvinok, Problems of distance geometry and convex properties of quadratic maps, Discrete Comput. Geom., 13 (1995), 189-202.  doi: 10.1007/BF02574037.

[10]

P. BiswasT.-C. LianT.-C. Wang and Y. Ye, Semidefinite programming based algorithms for sensor network localization, ACM Trans. Sen. Netw., 2 (2006), 188-220.  doi: 10.1145/1149283.1149286.

[11]

N. Boumal, Nonconvex phase synchronization, SIAM J. Optim., 26 (2016), 2355-2377.  doi: 10.1137/16M105808X.

[12]

S. Burer and R. D. C. Monteiro, Local minima and convergence in low-rank semidefinite programming, Math. Program., 103 (2005), 427-444.  doi: 10.1007/s10107-004-0564-1.

[13]

K. ChaudhuriF. Chung and A. Tsiatas, Spectral clustering of graphs with general degrees in the extended planted partition model, Proceedings of Machine Learning Research, 23 (2012), 35.1-35.23. 

[14]

R. Connelly, Generic global rigidity, Discrete Comput. Geom., 33 (2005), 549-563.  doi: 10.1007/s00454-004-1124-4.

[15]

R. Connelly, On generic global rigidity, in Applied Geometry and Discrete Mathematics, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 4, Amer. Math. Soc., Providence, RI, 1991, 147–155. doi: 10.1090/dimacs/004/11.

[16]

T. F. Cox and M. A. A. Cox, Multidimensional Scaling, Monographs on Statistics and Applied Probability, 88, Chapman & Hall/CRC, Boca Raton, FL, 2001.

[17]

M. Cucuringu, Sync-rank: Robust ranking, constrained ranking and rank aggregation via eigenvector and SDP synchronization, IEEE Trans. Network Sci. Eng., 3 (2016), 58-79.  doi: 10.1109/TNSE.2016.2523761.

[18]

M. CucuringuH. LiH. Sun and L. Zanetti, Hermitian matrices for clustering directed graphs: Insights and applications, Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, 108 (2020), 983-992. 

[19]

M. CucuringuY. Lipman and A. Singer, Sensor network localization by eigenvector synchronization over the Euclidean group, ACM Trans. Sen. Netw., 8 (2012), 1-42.  doi: 10.1145/2240092.2240093.

[20]

M. CucuringuA. Singer and D. Cowburn, Eigenvector synchronization, graph rigidity and the molecule problem, Inf. Inference, 1 (2012), 21-67.  doi: 10.1093/imaiai/ias002.

[21]

M. Cucuringu, A. V. Singh, D. Sulem and H. Tyagi, Regularized spectral methods for clustering signed networks, J. Mach. Learn. Res., 22 (2021), 79pp.

[22]

A. d'Aspremont, M. Cucuringu and H. Tyagi, Ranking and synchronization from pairwise measurements via SVD, J. Mach. Learn. Res., 22 (2021), 63pp.

[23]

C. Davis and W. M. Kahan, The rotation of eigenvectors by a perturbation. Ⅲ, SIAM J. Numer. Anal., 7 (1970), 1-46.  doi: 10.1137/0707001.

[24]

N. El Karoui and A. d'Aspremont, Second order accurate distributed eigenvector computation for extremely large matrices, Electron. J. Stat., 4 (2010), 1345-1385.  doi: 10.1214/10-EJS577.

[25]

M. Fanuel and J. A. K. Suykens, Deformed Laplacians and spectral ranking in directed networks, Appl. Comput. Harmon. Anal., 47 (2019), 397-422.  doi: 10.1016/j.acha.2017.09.002.

[26]

U. Feige and L. Lovász, Two-prover one-round proof systems: Their power and their problems (extended abstract), Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing, (1992), 733-744.  doi: 10.1145/129712.129783.

[27]

S. J. GortlerA. D. Healy and D. P. Thurston, Characterizing generic global rigidity, Amer. J. Math., 132 (2010), 897-939.  doi: 10.1353/ajm.0.0132.

[28]

C. Gotsman and Y. Koren, Distributed graph layout for sensor networks, J. Graph Algorithms Appl., 9 (2005), 327-346.  doi: 10.7155/jgaa.00112.

[29]

X. Guo, X. Li, X. Chang, S. Wang and Z. Zhang, Privacy-preserving distributed SVD via federated power, preprint, 2021, arXiv: 2103.00704.

[30]

B. Hendrickson, The molecule problem: Exploiting structure in global optimization, SIAM J. Optim., 5 (1995), 835-857.  doi: 10.1137/0805040.

[31]

J. KunegisS. SchmidtA. LommatzschJ. LernerE. W. De Luca and S. Albayrak, Spectral analysis of signed graphs for clustering, prediction and visualization, Proceedings of the 2010 SIAM International Conference on Data Mining (SDM), (2010), 559-570.  doi: 10.1137/1.9781611972801.49.

[32]

R.-C. Li, Relative perturbation theory. Ⅱ. Eigenspace and singular subspace variations, SIAM J. Matrix Anal. Appl., 20 (1999), 471-492.  doi: 10.1137/S0895479896298506.

[33]

A. PerryA. S. WeinA. S. Bandeira and A. Moitra, Message-passing algorithms for synchronization problems over compact groups, Comm. Pure Appl. Math., 71 (2018), 2275-2322.  doi: 10.1002/cpa.21750.

[34]

A. Perry, A. S. Wein, A. S. Bandeira and A. Moitra, Optimality and sub-optimality of PCA for spiked random matrices and synchronization, preprint, 2016, arXiv: 1609.05573.

[35]

Y. Shkolnisky and A. Singer, Viewing direction estimation in cryo-EM using synchronization, SIAM J. Imaging Sci., 5 (2012), 1088-1110.  doi: 10.1137/120863642.

[36]

A. Singer, Angular synchronization by eigenvectors and semidefinite programming, Appl. Comput. Harmon. Anal., 30 (2011), 20-36.  doi: 10.1016/j.acha.2010.02.001.

[37]

A. Singer and H.-T. Wu, Vector diffusion maps and the connection Laplacian, Comm. Pure Appl. Math., 65 (2012), 1067-1144.  doi: 10.1002/cpa.21395.

[38]

A. SingerZ. ZhaoY. Shkolnisky and R. Hadani, Viewing angle classification of cryo-electron microscopy images using eigenvectors, SIAM J. Imaging Sci., 4 (2011), 723-759.  doi: 10.1137/090778390.

[39]

E. Sizikova and T. Funkhouser, Wall painting reconstruction using a genetic algorithm, Proceedings of the 14th Eurographics Workshop on Graphics and Cultural Heritage, (2016), 83-91. 

[40]

M. Tubaishat and S. Madria, Sensor networks: An overview, IEEE Potentials, 22 (2003), 20-23.  doi: 10.1109/MP.2003.1197877.

[41]

T. Tzeneva, Global Alignment of Multiple 3-D Scans Using Eigenvector Synchronization, Undergraduate Thesis, Princeton University, 2011.

[42]

R. Vershynin, Introduction to the non-asymptotic analysis of random matrices, in Compressed Sensing, Cambridge Univ. Press, Cambridge, 2012, 210–268.

[43]

H. Weyl, Das asymptotische Verteilungsgesetz der Eigenwerte linearer partieller Differentialgleichungen (mit einer Anwendung auf die Theorie der Hohlraumstrahlung), Math. Ann., 71 (1912), 441-479.  doi: 10.1007/BF01456804.

[44]

S. Yu, Angular embedding: A robust quadratic criterion, IEEE Trans. Pattern Anal. Mach. Intell., 34 (2012), 158-173.  doi: 10.1109/TPAMI.2011.107.

[45]

S. X. Yu, Angular embedding: From jarring intensity differences to perceived luminance, 2009 IEEE Conference on Computer Vision and Pattern Recognition, Miami, FL, USA, 2009. doi: 10.1109/CVPR.2009.5206673.

[46]

Y. YuT. Wang and R. J. Samworth, A useful variant of the Davis-Kahan theorem for statisticians, Biometrika, 102 (2015), 315-323.  doi: 10.1093/biomet/asv008.

[47]

Y. Zhong and N. Boumal, Near-optimal bounds for phase synchronization, SIAM J. Optim., 28 (2018), 989-1016.  doi: 10.1137/17M1122025.

show all references

References:
[1]

A. A. AminiA. ChenP. J. Bickel and E. Levina, Pseudo-likelihood methods for community detection in large sparse networks, Ann. Statist., 41 (2013), 2097-2122.  doi: 10.1214/13-AOS1138.

[2]

G. AnderssonL. Engebretsen and J. Håstad, A new way of using semidefinite programming with applications to linear equations mod $p$, J. Algorithms, 39 (2001), 162-204.  doi: 10.1006/jagm.2000.1154.

[3]

M. Arie-Nachimson, S. Z. Kovalsky, I. Kemelmacher-Shlizerman, A. Singer and R. Basri, Global motion estimation from point matches, 2012 Second International Conference on 3D Imaging, Modeling, Processing, Visualization Transmission, Zurich, Switzerland, 2012. doi: 10.1109/3DIMPVT.2012.46.

[4]

A. S. BandeiraN. Boumal and A. Singer, Tightness of the maximum likelihood semidefinite relaxation for angular synchronization, Math. Program., 163 (2017), 145-167.  doi: 10.1007/s10107-016-1059-6.

[5]

A. S. Bandeira, Y. Chen, R. R. Lederman and A. Singer, Non-unique games over compact groups and orientation estimation in cryo-EM, Inverse Problems, 36 (2020), 39pp. doi: 10.1088/1361-6420/ab7d2c.

[6]

A. S. BandeiraA. Perry and A. S. Wein, Notes on computational-to-statistical gaps: Predictions using statistical physics, Port. Math., 75 (2018), 159-186.  doi: 10.4171/PM/2014.

[7]

A. S. Bandeira and R. van Handel, Sharp nonasymptotic bounds on the norm of random matrices with independent entries, Ann. Probab., 44 (2016), 2479-2506.  doi: 10.1214/15-AOP1025.

[8]

A.-L. Barabási and R. Albert, Emergence of scaling in random networks, Science, 286 (1999), 509-512.  doi: 10.1126/science.286.5439.509.

[9]

A. I. Barvinok, Problems of distance geometry and convex properties of quadratic maps, Discrete Comput. Geom., 13 (1995), 189-202.  doi: 10.1007/BF02574037.

[10]

P. BiswasT.-C. LianT.-C. Wang and Y. Ye, Semidefinite programming based algorithms for sensor network localization, ACM Trans. Sen. Netw., 2 (2006), 188-220.  doi: 10.1145/1149283.1149286.

[11]

N. Boumal, Nonconvex phase synchronization, SIAM J. Optim., 26 (2016), 2355-2377.  doi: 10.1137/16M105808X.

[12]

S. Burer and R. D. C. Monteiro, Local minima and convergence in low-rank semidefinite programming, Math. Program., 103 (2005), 427-444.  doi: 10.1007/s10107-004-0564-1.

[13]

K. ChaudhuriF. Chung and A. Tsiatas, Spectral clustering of graphs with general degrees in the extended planted partition model, Proceedings of Machine Learning Research, 23 (2012), 35.1-35.23. 

[14]

R. Connelly, Generic global rigidity, Discrete Comput. Geom., 33 (2005), 549-563.  doi: 10.1007/s00454-004-1124-4.

[15]

R. Connelly, On generic global rigidity, in Applied Geometry and Discrete Mathematics, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 4, Amer. Math. Soc., Providence, RI, 1991, 147–155. doi: 10.1090/dimacs/004/11.

[16]

T. F. Cox and M. A. A. Cox, Multidimensional Scaling, Monographs on Statistics and Applied Probability, 88, Chapman & Hall/CRC, Boca Raton, FL, 2001.

[17]

M. Cucuringu, Sync-rank: Robust ranking, constrained ranking and rank aggregation via eigenvector and SDP synchronization, IEEE Trans. Network Sci. Eng., 3 (2016), 58-79.  doi: 10.1109/TNSE.2016.2523761.

[18]

M. CucuringuH. LiH. Sun and L. Zanetti, Hermitian matrices for clustering directed graphs: Insights and applications, Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, 108 (2020), 983-992. 

[19]

M. CucuringuY. Lipman and A. Singer, Sensor network localization by eigenvector synchronization over the Euclidean group, ACM Trans. Sen. Netw., 8 (2012), 1-42.  doi: 10.1145/2240092.2240093.

[20]

M. CucuringuA. Singer and D. Cowburn, Eigenvector synchronization, graph rigidity and the molecule problem, Inf. Inference, 1 (2012), 21-67.  doi: 10.1093/imaiai/ias002.

[21]

M. Cucuringu, A. V. Singh, D. Sulem and H. Tyagi, Regularized spectral methods for clustering signed networks, J. Mach. Learn. Res., 22 (2021), 79pp.

[22]

A. d'Aspremont, M. Cucuringu and H. Tyagi, Ranking and synchronization from pairwise measurements via SVD, J. Mach. Learn. Res., 22 (2021), 63pp.

[23]

C. Davis and W. M. Kahan, The rotation of eigenvectors by a perturbation. Ⅲ, SIAM J. Numer. Anal., 7 (1970), 1-46.  doi: 10.1137/0707001.

[24]

N. El Karoui and A. d'Aspremont, Second order accurate distributed eigenvector computation for extremely large matrices, Electron. J. Stat., 4 (2010), 1345-1385.  doi: 10.1214/10-EJS577.

[25]

M. Fanuel and J. A. K. Suykens, Deformed Laplacians and spectral ranking in directed networks, Appl. Comput. Harmon. Anal., 47 (2019), 397-422.  doi: 10.1016/j.acha.2017.09.002.

[26]

U. Feige and L. Lovász, Two-prover one-round proof systems: Their power and their problems (extended abstract), Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing, (1992), 733-744.  doi: 10.1145/129712.129783.

[27]

S. J. GortlerA. D. Healy and D. P. Thurston, Characterizing generic global rigidity, Amer. J. Math., 132 (2010), 897-939.  doi: 10.1353/ajm.0.0132.

[28]

C. Gotsman and Y. Koren, Distributed graph layout for sensor networks, J. Graph Algorithms Appl., 9 (2005), 327-346.  doi: 10.7155/jgaa.00112.

[29]

X. Guo, X. Li, X. Chang, S. Wang and Z. Zhang, Privacy-preserving distributed SVD via federated power, preprint, 2021, arXiv: 2103.00704.

[30]

B. Hendrickson, The molecule problem: Exploiting structure in global optimization, SIAM J. Optim., 5 (1995), 835-857.  doi: 10.1137/0805040.

[31]

J. KunegisS. SchmidtA. LommatzschJ. LernerE. W. De Luca and S. Albayrak, Spectral analysis of signed graphs for clustering, prediction and visualization, Proceedings of the 2010 SIAM International Conference on Data Mining (SDM), (2010), 559-570.  doi: 10.1137/1.9781611972801.49.

[32]

R.-C. Li, Relative perturbation theory. Ⅱ. Eigenspace and singular subspace variations, SIAM J. Matrix Anal. Appl., 20 (1999), 471-492.  doi: 10.1137/S0895479896298506.

[33]

A. PerryA. S. WeinA. S. Bandeira and A. Moitra, Message-passing algorithms for synchronization problems over compact groups, Comm. Pure Appl. Math., 71 (2018), 2275-2322.  doi: 10.1002/cpa.21750.

[34]

A. Perry, A. S. Wein, A. S. Bandeira and A. Moitra, Optimality and sub-optimality of PCA for spiked random matrices and synchronization, preprint, 2016, arXiv: 1609.05573.

[35]

Y. Shkolnisky and A. Singer, Viewing direction estimation in cryo-EM using synchronization, SIAM J. Imaging Sci., 5 (2012), 1088-1110.  doi: 10.1137/120863642.

[36]

A. Singer, Angular synchronization by eigenvectors and semidefinite programming, Appl. Comput. Harmon. Anal., 30 (2011), 20-36.  doi: 10.1016/j.acha.2010.02.001.

[37]

A. Singer and H.-T. Wu, Vector diffusion maps and the connection Laplacian, Comm. Pure Appl. Math., 65 (2012), 1067-1144.  doi: 10.1002/cpa.21395.

[38]

A. SingerZ. ZhaoY. Shkolnisky and R. Hadani, Viewing angle classification of cryo-electron microscopy images using eigenvectors, SIAM J. Imaging Sci., 4 (2011), 723-759.  doi: 10.1137/090778390.

[39]

E. Sizikova and T. Funkhouser, Wall painting reconstruction using a genetic algorithm, Proceedings of the 14th Eurographics Workshop on Graphics and Cultural Heritage, (2016), 83-91. 

[40]

M. Tubaishat and S. Madria, Sensor networks: An overview, IEEE Potentials, 22 (2003), 20-23.  doi: 10.1109/MP.2003.1197877.

[41]

T. Tzeneva, Global Alignment of Multiple 3-D Scans Using Eigenvector Synchronization, Undergraduate Thesis, Princeton University, 2011.

[42]

R. Vershynin, Introduction to the non-asymptotic analysis of random matrices, in Compressed Sensing, Cambridge Univ. Press, Cambridge, 2012, 210–268.

[43]

H. Weyl, Das asymptotische Verteilungsgesetz der Eigenwerte linearer partieller Differentialgleichungen (mit einer Anwendung auf die Theorie der Hohlraumstrahlung), Math. Ann., 71 (1912), 441-479.  doi: 10.1007/BF01456804.

[44]

S. Yu, Angular embedding: A robust quadratic criterion, IEEE Trans. Pattern Anal. Mach. Intell., 34 (2012), 158-173.  doi: 10.1109/TPAMI.2011.107.

[45]

S. X. Yu, Angular embedding: From jarring intensity differences to perceived luminance, 2009 IEEE Conference on Computer Vision and Pattern Recognition, Miami, FL, USA, 2009. doi: 10.1109/CVPR.2009.5206673.

[46]

Y. YuT. Wang and R. J. Samworth, A useful variant of the Davis-Kahan theorem for statisticians, Biometrika, 102 (2015), 315-323.  doi: 10.1093/biomet/asv008.

[47]

Y. Zhong and N. Boumal, Near-optimal bounds for phase synchronization, SIAM J. Optim., 28 (2018), 989-1016.  doi: 10.1137/17M1122025.

Figure 1.  An instance of the bi-synchronization problem. The measurement graph (bottom row) available to the user is a union of two edge disjoint graphs (top row) on the same vertex set. The top graphs each capture angle offsets for two different sets of angles: the top left graph encodes noise pairwise offsets between the angles $ \alpha_1, \ldots, \alpha_n $, while the top right graph contains similar information from the angles $ \beta_1, \ldots, \beta_n $
Figure 2.  An instance of the bi-synchronization problem in the context of ranking from pairwise comparisons with multiple voting systems. The red and blue judges each give a rating for pair of items $ {\left\{{{i, j}}\right\}} $. $ (\alpha_1, \ldots, \alpha_n ) $ denote the intrinsic strength/skill of the players as construed by the red judge, while $ ( \beta_1, \ldots, \beta_n) $ capture the strength/skill of the same set of $ n $ players as perceived by the blue judge
Figure 3.  An instance of the cluster-synchronization problem, closely related to the bi-synchronization problem we study in this paper. The collection of angles is partitioned into two clusters $ \mathcal{C}_1 = (\alpha_1, \alpha_2, \ldots, \alpha_{n_1}) $, $ \mathcal{C}_2 = (\beta_{n_1+1}, \beta_{n+2}, \ldots, \beta_{n_2}) $, of potentially unequal sizes $ n_1, n_2 $ (as is the case in this example, with $ n_1 = 5, n_2 = 4 $), such that when a pair of angles is chosen from the same cluster, we obtain a (potentially noisy) offset $ \alpha_i - \alpha_j $ or $ \beta_i - \beta_j $. However, when a pair $ (\alpha_i, \beta_j) $ of angles from two different clusters is compared, the measured offset $ \Theta_{ij} $ is completely random and contains no meaningful information
Figure 4.  Experimental Setup Ⅰ: Correlation of recovered angles with the ground truth for $ n = 500 $ (top), respectively $ n = 1000 $ (bottom), with $ k = 2 $ groups of angles, and various noise levels $ \eta \in \{ 0.50, 0.70, 0.85\} $ as a function of $ \lambda $ (sparsity of the measurement graph). Results are averaged over $ 20 \times 20 = 400 $ runs (i.e, over 20 random instances of groups of angles, and for each such a group of angles, we consider 20 random instances of the sampling graph according to $ p_1 $ and $ p_2 $)
Figure 5.  Experimental Setup Ⅰ: Correlation of recovered angles with the ground truth for $ n = 1000 $, with $ k = 3 $ (top) and $ k = 4 $ (bottom) collections of angles, and various noise levels $ \eta $, as a function of $ \lambda $ (sparsity of the measurement graph). Results are averaged over $ 20 \times 20 = 625 $ runs
Figure 6.  Experimental Setup Ⅱ: Correlation of recovered angles with the ground truth, where we keep constant the gap $ \gamma = 0.05 $ between consecutive sampling probabilities $ p_{l+1} - p_l = \gamma, l = 1, \ldots, k-1 $, of the subgraphs $ G_{l} $. We also fix the number of angles $ n = 500 $, and vary $ k \in \{2, 3, 4\} $ (indexing the rows), and the overall measurement graph sparsity $ \lambda \in \{ 0.2, 0.4, 0.8\} $ (indexing the columns). Each plot shows the correlation with the ground truth, as we vary the noise level $ \eta $. Results are averaged over $ 20 \times 20 = 400 $ runs
Figure 7.  Experimental Setup Ⅱ: Correlation of recovered angles with the ground truth in the second experimental setup where we compared the performance of the two spectral relaxations and the SDP relaxation. EIG-H denotes the relaxation that uses the top eigenvector of matrix $ H $ from (4.5); EIG-R employs the normalized matrix eq. (6.2), and SDP-BM denotes the SDP relaxation eq. (2.4) solved via the Burer-Monteiro approach. We keep constant the gap $ \gamma = 0.05 $ between consecutive sampling probabilities $ p_{l+1} - p_l = \gamma, l = 1, \ldots, k-1 $, of the subgraphs $ G_{l} $. The number of angles is kept fixed at $ n = 500 $, and we vary $ k \in \{2, 3, 4\} $ (indexing the rows), and the overall measurement graph sparsity $ \lambda \in \{ 0.2, 0.4, 0.8\} $ (indexing the columns). Each plot shows the correlation with ground truth, as we vary the noise level $ \eta $. Results are averaged over $ 20 \times 20 = 400 $ runs
Figure 8.  Experimental Setup Ⅱ: Performance comparison in the setting of a Barabási–Albert model, for $ n = 500 $, edge density $ \lambda = 0.20 $, gap $ \gamma = 0.05 $, $ k \in \{2, 3, 4\} $, as a function of the noise levels $ \eta $. Results are averaged over $ 20 \times 20 $ runs
Figure 9.  Top: ground truth good graph $ G_1, G_2 $ and the bad graph $ W $, all edge disjoint, of size $ n = 100 $, with corresponding probabilities $ p_1 = 0.45 $, $ p_2 = 0.35 $ and $ \eta = 0.20 $. Middle: the user observes an angle offset matrix $ \Theta $ whose underlying entangled measurement graph $ G = G_1 \cup G_2 \cup W $ is depicted. Bottom: final estimates of $ \widehat{G}_1, \widehat{G}_2, \widehat{W} $ from our recovery pipeline, with a visualization of the classification errors; the titles contain the two types of errors being made: the number of extra edges (+) and the number of missing edges (-) for each individual estimated graph
Figure 10.  Histogram of synchronization residuals given by the non-zero entries of the matrix $ \tilde{\Psi}_{l}, \; l = \{1, 2, 3\} $, as defined in (6.5), where the $ k = 3 $ underlying measurement graphs have edges densities $ (p_1, p_2, p_3) = (0.18, 0.15, 0.12) $, noise level $ \eta = 0.55 $, and sparsity $ \lambda = 0.3 $. The top (resp. bottom) row plots the non-zero residual entries after one iteration (resp., 20 iterations of Algorithm 2), with columns indexing the three groups of underlying angles. Note that for each column (i.e., group of angles), the residuals become significantly smaller after 20 iterations, for all three groups of angles, showcasing the effectiveness of the iterative procedure
Figure 11.  Correlation with ground truth for the first 20 iterations of Algorithm 2, for three problem instances with $ k = 2, 3, 4 $ and $ n = 500 $, at various noise levels $ \eta $ and sparsity levels $ \lambda $. In all three problem instances, and across all subsets of angles within each instance, the iterative procedure leads to an increase in the correlation with ground truth, especially for the groups of angles with the sparsest measurement graph
Figure 12.  Optimal alignment of two patch embeddings, that overlap in four (green) nodes [19]. This pairwise alignment provides a measurement for the ratio of the two corresponding group elements in Euc(2)
Figure 13.  The ASAP recovery process in $ d = 2 $ dimensions, considered in [19], for a patch in the US graph
Figure 14.  Alignment of frescos, as explored in [39]. The alignment of the pieces can be construed as an instance of the synchronization problem over the Euclidean group of rigid motions
Figure 15.  Clean data, two non-congruent embeddings of the US graph: (a) Original US map (b) Non-rigid transformation of the original data (shear transformation, followed by a rotation and scaling of the Midwest and East Coast). (c) Procrustes alignment of the point clouds in (a) and (b) showing the displacements between the two embeddings, making the point that the two embeddings that we aim to recover are indeed non-congruent
Figure 16.  (a) Adjacency matrix of the measurement graph $ G $, highlighting the decomposition $ G = G_1 $ (red) $ + G_2 $ (yellow). Plots (b) and (c) show the histogram of degrees in $ G_1 $ and $ G_2 $. The embeddings of $ X $ and $ Y $ are colored by their corresponding degree, i.e., each node $ i $ in the embedding (that lies at the center of patch $ P_i $) is colored by the number of other patches it overlaps with
Figure 17.  Recovery of the two estimated embeddings $ \hat{X} $ and $ \hat{Y} $ shown in the first and third columns, where the coloring is given by the longitude. The second column shows the Procrustes alignment between the recovered embedding $ \hat{X} $ (red) and the ground truth $ X $ (blue), together with the displacement error bars. The forth column shows a similar visualization for $ \hat{Y} $ and the ground truth $ Y $. We vary the noise level $ \sigma $ used in the perturbations of the local patch embeddings in both ensembles, across the following set of values $ \sigma \in \{ 0, 0.2, 0.4, 0.6, 0.8 \} $
Figure 18.  Left: classical angular synchronization; Right: an instance of the $ k $-list synchronization problem, where the goal is to recover a single group of $ n $ angles, from a small subset of pairwise noisy offsets $ \theta_i - \theta_j $; however, there are now multiple candidates for a given pairwise offset, only one of which is correct (or approximately correct)
[1]

Angelo B. Mingarelli. Nonlinear functionals in oscillation theory of matrix differential systems. Communications on Pure and Applied Analysis, 2004, 3 (1) : 75-84. doi: 10.3934/cpaa.2004.3.75

[2]

Maxim Sølund Kirsebom. Extreme value theory for random walks on homogeneous spaces. Discrete and Continuous Dynamical Systems, 2014, 34 (11) : 4689-4717. doi: 10.3934/dcds.2014.34.4689

[3]

Jeremy L. Marzuola. Dispersive estimates using scattering theory for matrix Hamiltonian equations. Discrete and Continuous Dynamical Systems, 2011, 30 (4) : 995-1035. doi: 10.3934/dcds.2011.30.995

[4]

Giovanni Russo, Fabian Wirth. Matrix measures, stability and contraction theory for dynamical systems on time scales. Discrete and Continuous Dynamical Systems - B, 2022, 27 (6) : 3345-3374. doi: 10.3934/dcdsb.2021188

[5]

Florian Dorsch, Hermann Schulz-Baldes. Random Möbius dynamics on the unit disc and perturbation theory for Lyapunov exponents. Discrete and Continuous Dynamical Systems - B, 2022, 27 (2) : 945-976. doi: 10.3934/dcdsb.2021076

[6]

Fabio Camilli, Annalisa Cesaroni. A note on singular perturbation problems via Aubry-Mather theory. Discrete and Continuous Dynamical Systems, 2007, 17 (4) : 807-819. doi: 10.3934/dcds.2007.17.807

[7]

Wenlei Li, Shaoyun Shi. Singular perturbed renormalization group theory and its application to highly oscillatory problems. Discrete and Continuous Dynamical Systems - B, 2018, 23 (4) : 1819-1833. doi: 10.3934/dcdsb.2018089

[8]

Jonathan H. Tu, Clarence W. Rowley, Dirk M. Luchtenburg, Steven L. Brunton, J. Nathan Kutz. On dynamic mode decomposition: Theory and applications. Journal of Computational Dynamics, 2014, 1 (2) : 391-421. doi: 10.3934/jcd.2014.1.391

[9]

Debasisha Mishra. Matrix group monotonicity using a dominance notion. Numerical Algebra, Control and Optimization, 2015, 5 (3) : 267-274. doi: 10.3934/naco.2015.5.267

[10]

Stéphane Chrétien, Sébastien Darses, Christophe Guyeux, Paul Clarkson. On the pinning controllability of complex networks using perturbation theory of extreme singular values. application to synchronisation in power grids. Numerical Algebra, Control and Optimization, 2017, 7 (3) : 289-299. doi: 10.3934/naco.2017019

[11]

Rémi Leclercq. Spectral invariants in Lagrangian Floer theory. Journal of Modern Dynamics, 2008, 2 (2) : 249-286. doi: 10.3934/jmd.2008.2.249

[12]

Barry Simon. Equilibrium measures and capacities in spectral theory. Inverse Problems and Imaging, 2007, 1 (4) : 713-772. doi: 10.3934/ipi.2007.1.713

[13]

Ai-Guo Wu, Ying Zhang, Hui-Jie Sun. Parametric Smith iterative algorithms for discrete Lyapunov matrix equations. Journal of Industrial and Management Optimization, 2020, 16 (6) : 3047-3063. doi: 10.3934/jimo.2019093

[14]

Tao Wu, Yu Lei, Jiao Shi, Maoguo Gong. An evolutionary multiobjective method for low-rank and sparse matrix decomposition. Big Data & Information Analytics, 2017, 2 (1) : 23-37. doi: 10.3934/bdia.2017006

[15]

Giuseppe Geymonat, Françoise Krasucki. Hodge decomposition for symmetric matrix fields and the elasticity complex in Lipschitz domains. Communications on Pure and Applied Analysis, 2009, 8 (1) : 295-309. doi: 10.3934/cpaa.2009.8.295

[16]

Huseyin Coskun. Nonlinear decomposition principle and fundamental matrix solutions for dynamic compartmental systems. Discrete and Continuous Dynamical Systems - B, 2019, 24 (12) : 6553-6605. doi: 10.3934/dcdsb.2019155

[17]

Xianchao Xiu, Lingchen Kong. Rank-one and sparse matrix decomposition for dynamic MRI. Numerical Algebra, Control and Optimization, 2015, 5 (2) : 127-134. doi: 10.3934/naco.2015.5.127

[18]

Óscar Vega-Amaya, Joaquín López-Borbón. A perturbation approach to a class of discounted approximate value iteration algorithms with borel spaces. Journal of Dynamics and Games, 2016, 3 (3) : 261-278. doi: 10.3934/jdg.2016014

[19]

John Boyd. Strongly nonlinear perturbation theory for solitary waves and bions. Evolution Equations and Control Theory, 2019, 8 (1) : 1-29. doi: 10.3934/eect.2019001

[20]

Victor Kozyakin. Iterative building of Barabanov norms and computation of the joint spectral radius for matrix sets. Discrete and Continuous Dynamical Systems - B, 2010, 14 (1) : 143-158. doi: 10.3934/dcdsb.2010.14.143

 Impact Factor: 

Metrics

  • PDF downloads (125)
  • HTML views (154)
  • Cited by (0)

Other articles
by authors

[Back to Top]