Abstract
We review a recent algorithm for localization of points in Euclidean space from a sparse and noisy subset of their pairwise distances. Our approach starts by extracting and embedding uniquely realizable subsets of neighboring sensors called patches. In the noise-free case, each patch agrees with its global positioning up to an unknown rigid motion of translation, rotation, and possibly reflection. The reflections and rotations are estimated using the recently developed eigenvector synchronization algorithm, while the translations are estimated by solving an overdetermined linear system. In other words, to every patch, there corresponds an element of the Euclidean group Euc(3) of rigid transformations in \({\mathbb{R}}^{3}\), and the goal is to estimate the group elements that will properly align all the patches in a globally consistent way. The algorithm is scalable as the number of nodes increases, and can be implemented in a distributed fashion. Extensive numerical experiments show that it compares favorably to other existing algorithms in terms of robustness to noise, sparse connectivity and running time.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
We used the SNL-SDP code of [44].
- 2.
For example three common vertices, although the precise definition of “enough” will be given later.
- 3.
The diagonal matrix D should not be confused with the partial distance matrix.
- 4.
Not to be confused with G(i) = (V (i), E(i)) defined in the beginning of this section.
References
Akyildiz, I.F., Su, W., Cayirci, Y.S.E.: Wireless sensor networks: A survey. Comput. Network. 38, 393–422 (2002)
Anderson, B.D.O., Belhumeur, P.N., Eren, T., Goldenberg, D.K., Morse, A.S., Whiteley, W.: Graphical properties of easily localizable networks. Wireless Network. 15, 177–191 (2009)
Arie-Nachimson, M., Basri, R., Singer, A.: in preparation
Aspnes, J., Eren, T., Goldenberg, D.K., Morse, A.S., Whiteley, W., Yang, Y.R., Anderson, B.D.O., Belhumeur, P.N.: A theory of network localization. IEEE Trans. Mobile. Comput. 5, 1663–1678 (2006)
Aspnes, J., Goldenberg, D.K., Yang, Y.R.: On the computational complexity of sensor network localization. In: Proceedings of Algorithmic Aspects of Wireless Sensor Networks: First International Workshop (ALGOSENSORS), Lecture Notes in Computer Science, pp. 32–44. Springer (2004)
Bandeira, A.S., Singer, A., Spielman, D.A.: A cheeger inequality for the graph connection laplacian, arXiv.12043873
Belkin, M., Niyogi, P.: Laplacian eigenmaps for dimensionality reduction and data representation. Neural Comput. 15, 1373–1396 (2003)
Biswas, P., Aghajan, H., Ye, Y.: Semidefinite programming algorithms for sensor network localization using angle of arrival information. In: Proceedings of the 39th Annual Asilomar Conference on Signals, Systems, and Computers, pp. 220–224 (2005)
Biswas, P., Lian, T.C., Wang, T.C., Ye, Y.: Semidefinite programming based algorithms for sensor network localization. ACM Transactions on Sensor Networks 2, 188–220 (2006) a
Biswas, P., Liang, T., Toh, K., Ye, Y., Wang, T.: Semidefinite programming approaches for sensor network localization with noisy distance measurements. IEEE Transactions on Automation Science and Engineering 3, 360–371 (2006) b
Biswas, P., Ye, Y.: Semidefinite programming for ad hoc wireless sensor network localization. In: ACM Conference Proceedings, Third International Symposium on Information Processing in Sensor Networks, pp. 46–54. New York (2004)
Borg, I., Groenen, P.J.F.: Modern Multidimensional Scaling: Theory and Applications. Springer, New York (2005)
Coifman, R.R., Lafon, S.: Diffusion maps. Applied and Computational Harmonic Analysis 21, 5–30 (2006)
Connelly, R., Whiteley, W.J.: Global rigidity: The effect of coning. Discrete Comput. Geom. 43, 717–735 (2010)
Cox, T.F., Cox, M.A.A.: Multidimensional scaling. Monographs on Statistics and Applied Probability 88. Chapman & Hall/CRC, Boca Raton (2001)
Cucuringu, M., Lipman, Y., Singer, A.: Sensor network localization by eigenvector synchronization over the Euclidean group. ACM Tran. Sen. Net. 8(3), 1–42 (2011)
Cucuringu, M., Singer, A., Cowburn, D.: Synchronization, graph rigidity and the molecule problem. submitted (2011)
De Leeuw, J.: Applications of convex analysis to multidimensional scaling. In: Barra, J.R., Brodeau, F., Romierand, G., Cutsem, B.V. (eds.) Recent Developments in Statistics, pp. 133–146. North Holland Publishing Company, Amsterdam (1977)
Frank, J.: Three-dimensional Electron Microscopy of Macromolecular Assemblies: Visualization of Biological Molecules in Their Native State, 2nd edn. Oxford University Press, USA (2006)
Giridhar, A., Kumar, P.R.: Distributed clock synchronization over wireless networks: algorithms and analysis. In: IEEE Conference Proceedings, 45th IEEE Conference on Decision and Control, pp. 4915–4920 (2006)
Gotsman, C., Koren, Y.: Distributed graph layout for sensor networks. In: Proceedings of the International Symposium on Graph Drawing, pp. 273–284 (2004)
Hadani, R., Singer, Representation theoretic patterns in three dimensional Cryo-Electron Microscopy I – the intrinsic reconstitution algorithm, Ann. Math. 174(2), pp. 1219–1241 (2011).
Hendrickson, B.: Conditions for unique graph realizations. SIAM J. Comput. 21, 65–84 (1992)
Hendrickson, B.: The molecule problem: exploiting structure in global optimization. SIAM J. Optim. 5, 835–857 (1995)
Horn, B., Hilden, H., Negahdaripour, S.: Closed-form solution of absolute orientation using orthonormal matrices. J. Opt. Soc. Am. A 5, 1127–1135 (1988)
Javanmard, A., Montanari, A.: Localization from incomplete noisy distance measurements, submitted
Ji, X., Zha, H.: Sensor positioning in wireless ad-hoc sensor networks using multidimensional scaling. In: Proceedings of INFOCOM, vol. 4, pp. 2652–2661 (2004)
Karp, R., Elson, J., Estrin, D., Shenker, S.: Optimal and global time synchronization in sensornets. Tech. Report, Center for Embedded Networked Sensing, University of California, Los Angeles (2003)
Koren, Y., Gotsman, C., Ben-Chen, M.: PATCHWORK: Efficient localization for sensor networks by distributed global optimization. Tech. Report (2005)
Liberti, L., Lavor, C., Maculan, N., Mucherino, A.: Euclidean distance geometry and applications. Tech. Report, arXiv.12050349 (2012)
Liberti, L., Lavor, C., Mucherino, A., Maculan, N.: Molecular distance geometry methods: From continuous to discrete. Int. Trans. Oper. Res. 18, 33–51 (2011)
Moore, D., Leonard, J., Rus, D., Teller, S.: Robust distributed network localization with noisy range measurements. In: Proceedings of the Second ACM Conference on Embedded Networked Sensor Systems, pp. 50–61 (2004)
Ozyesil, O., Singer, A.: Synchronization in non-compact groups: Special euclidean group case, submitted
Roweis, S.T., Saul, L.K.: Nonlinear dimensionality reduction by locally linear embedding. Science 290 2323–2326 (2000)
Saxe, J.B.: Embeddability of weighted graphs in k-space is strongly NP-hard. In: Proceedings of 17th Allerton Conference in Communications, Control and Computing, pp. 480–489 (1979)
Shang, Y., Ruml, W.: Improved MDS-based localization. In: Proceedings of IEEE INFOCOM, vol. 23, pp. 2640–2651. Hong Kong, China (2004)
Singer, A.: A remark on global positioning from local distances. Proc. Natl. Acad. Sci. 105, 9507–9511 (2008)
Singer, A.: Angular synchronization by eigenvectors and semidefinite programming. Applied and Computational Harmonic Analysis 30, 20–36 (2011)
Singer, A., Shkolnisky, Three-Dimensional Structure Determination from Common Lines in Cryo-EM by Eigenvectors and Semidefinite Programming. SIAM J. Imag. Sci. 4(2), pp. 543–572 (2011).
Singer, A., Wu, H.-T.: Vector diffusion maps and the connection Laplacian, Commun. Pur. Appl. Math. (CPAM), 65(8), pp. 1067–1144 (2012)
Singer, A., Zhao, Z., Shkolnisky, Y., Hadani, R.: Viewing angle classification of cryo-electron microscopy images using eigenvectors. SIAM J. Imag. Sci. 4, 543–572 (2011)
So, A.M.C.: A semidefinite programming approach to the graph realization problem: theory, applications and extensions. Ph.D. Thesis (2007)
So, A.M.C., Ye, Y.: Theory of semidefinite programming for sensor network localization. In: Proceedings of the 17th Annual ACM–SIAM Symposium on Discrete Algorithm (SODA), pp. 405–414 (2005)
Toh, K., Biswas, P., Ye, Y.: SNLSDP version 0 – a MATLAB software for sensor network localization, October 2008 http://www.math.nus.edu.sg/ mattohkc/SNLSDP.html
Tubaishat, M., Madria, S.: Sensor networks: an overview. IEEE Potentials 22, 20–23 (2002)
Weinberger, K.Q., Sha, F., Zhu, Q., Saul, L.K.: Graph laplacian regularization for large-scale semidefinite programming. In: Schoolkopf, B., Platt, J., Hofmann, T. (eds.) Advances in neural information processing systems (NIPS), MIT Press, Cambridge (2007)
Yemini, Y.: Some theoretical aspects of location-location problems. In: Proceedings of the IEEE Annual Symposium on Foundations of Computer Science, pp. 1–8 (1979)
Zhang, L., Liu, L., Gotsman, C., Gortler, S.J.: An As-Rigid-As-Possible approach to sensor network localization. ACM Tran. Sen. Net. 6(4), 1–21 (2010)
Zhu, Z., So, A.M.C., Ye, Y.: Universal rigidity: towards accurate and efficient localization of wireless networks. In: Proceedings of the IEEE INFOCOM, pp. 1–9 (2010)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer Science+Business Media New York
About this chapter
Cite this chapter
Cucuringu, M. (2013). ASAP: An Eigenvector Synchronization Algorithm for the Graph Realization Problem. In: Mucherino, A., Lavor, C., Liberti, L., Maculan, N. (eds) Distance Geometry. Springer, New York, NY. https://doi.org/10.1007/978-1-4614-5128-0_10
Download citation
DOI: https://doi.org/10.1007/978-1-4614-5128-0_10
Published:
Publisher Name: Springer, New York, NY
Print ISBN: 978-1-4614-5127-3
Online ISBN: 978-1-4614-5128-0
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)