×

The algebro-geometric study of range maps. (English) Zbl 1366.14042

This paper features a study of the localization problem for a radiant point source from the viewpoint of algebraic and differential geometry. A source point \(S\) is to be computed from its distances to a set of receivers or, in later sections, from the differences of these distances. The paper is concerned with the calibrated and (mostly with the) deterministic model. This means that the relative position of the receivers is known and the distance measures are not subject to noise. Stochastic considerations are only considered once a solid description of the deterministic geometry has been established.
The fundamental object under scrutiny is range maps. These associate to a point the tuple of distances to the receivers. In the most general situation that is considered in this paper, three non-collinear receivers are given. It turns out that the image of the range map is contained in the intersection of the first octant with Kummer’s quartic surface. Its geometry is exploited to study invertability of the range map and to obtain a tight polyhedral bounding volume. Moreover, it is related to non-generic situations, to stochastic models, and to the localization problem from range differences.

MSC:

14J99 Surfaces and higher-dimensional varieties
14P10 Semialgebraic sets and related spaces
51K99 Distance geometry
94A12 Signal theory (characterization, reconstruction, filtering, etc.)

Software:

Trilater.c
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Abraham, R., Marsden, J., Ratiu, T.: Manifolds, Tensor Analysis, and Applications, 2nd edn. Springer-Verlag, New York (1988) · Zbl 0875.58002 · doi:10.1007/978-1-4612-1029-0
[2] Alameda-Pineda, X., Horaud, R.: A geometric approach to sound source localization from time-delay estimates. IEEE Trans. Audio Speech Lang. Process. (TASLP) 22, 1082-1095 (2014) · doi:10.1109/TASLP.2014.2317989
[3] Amari, S.: Differential geometry of curved exponential families-curvatures and information loss. Ann. Stat. 10(2), 357-385 (1982) · Zbl 0507.62026 · doi:10.1214/aos/1176345779
[4] Amari, S., Nagaoka, H.: Methods of Information Geometry. American Mathematical Society, Providence, RI (2000) · Zbl 0960.62005
[5] Aspnes, J., Eren, T., Goldenberg, D., Morse, S., Whiteley, W., Yang, R., Anderson, B., Belhumeur, P.: A theory of network localization. IEEE Trans. Mobile Comput. 5, 1663-1678 (2006) · doi:10.1109/TMC.2006.174
[6] Beck, A., Stoica, P., Li, J.: Exact and approximate solutions of source localization problems. IEEE Trans. Signal Process. (TSP) 56, 1770-1778 (2008) · Zbl 1390.94091 · doi:10.1109/TSP.2007.909342
[7] Bellman, R., Astrom, K.: On structural identifiability. Math. Biosci. 7, 329-339 (1970) · doi:10.1016/0025-5564(70)90132-X
[8] Beltrametti, M., Carletti, E., Gallarati, D., Monti Bragadin, G.: Lectures on Curves, Surfaces and Projective Varieties. A Classical View of Algebraic Geometry. EMS Textbooks in Mathematics. European Mathematical Society, Zurich (2009) · Zbl 1180.14001
[9] Benesty, J., Huang, Y. (eds.): Audio Signal Processing for Next-Generation Multimedia Communication Systems. Springer, US (2004)
[10] Berry, T.G.: Points at rational distance from the vertices of a triangle. Acta Arith. LXI I(4), 391-398 (1992) · Zbl 0758.11019
[11] Bestagini, P., Compagnoni, M., Antonacci, F., Sarti, A., Tubaro, S.: TDOA-based acoustic source localization in the space-range reference frame. Multidimens. Syst. Signal Process. 25, 337-359 (2014) · Zbl 1345.94012 · doi:10.1007/s11045-013-0233-8
[12] Blekherman, G., Parrilo, P.A., Thomas, R.R.: Semidefinite Optimization and Convex Algebraic Geometry. Number 13 in MOS-SIAM Series on Optimization. SIAM, Philadelphia (2013) · Zbl 1260.90006
[13] Blumenthal, L.: Theory and Applications of Distance Geometry. Oxford University Press, Oxford (1953) · Zbl 0050.38502
[14] Borcea, C.: Point Configurations and Cayley-Menger Varieties. arXiv:math/0207110 (2002)
[15] Borcea, C., Streinu, I.: The number of embeddings of minimally rigid graphs. Discrete Comput. Geom. 31(2), 287-303 (2004) · Zbl 1050.05030 · doi:10.1007/s00454-003-2902-0
[16] Caffery, J.J.: A new approach to the geometry of toa location. Proc. IEEE Veh. Technol. Conf. (VTC) 4(52), 1943-1949 (2000)
[17] Cheng, Y., Wangb, X., Morelande, M., Moran, B.: Information geometry of target tracking sensor networks. Inf. Fusion 14, 311-326 (2013) · doi:10.1016/j.inffus.2012.02.005
[18] Cheung, K.W., So, H.C., Ma, W.K., Chan, Y.T.: Least squares algorithms for time-of-arrival-based mobile location. IEEE Trans. Signal Process. 52(4), 1121-1128 (2004) · Zbl 1369.94347 · doi:10.1109/TSP.2004.823465
[19] Cheung, K.W., Ma, W.K., So, H.C.: Accurate approximation algorithm for TOA-based maximum likelihood mobile location using semidefinite programming. In: IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), vol. 2, pp. 145-148 (2004b)
[20] Cheung, K.W., So, H.C.: A multidimensional scaling framework for mobile location using time-of-arrival measurements. IEEE Trans. Signal Process. 53(2), 460-470 (2005) · Zbl 1370.90066 · doi:10.1109/TSP.2004.840721
[21] Coll, B., Ferrando, J., Morales-Lladosa, J.: Positioning systems in minkowski space-time: from emission to inertial coordinates. Class. Quantum Gravity 27, 065013 (2010) · Zbl 1185.83002 · doi:10.1088/0264-9381/27/6/065013
[22] Coll, B., Ferrando, J., Morales-Lladosa, J.: Positioning systems in Minkowski space-time: bifurcation problem and observational data. Phys. Rev. D 86, 084036 (2012) · doi:10.1103/PhysRevD.86.084036
[23] Compagnoni, M., Bestagini, P., Antonacci, F., Sarti, A., Tubaro, S.: Localization of acoustic sources through the fitting of propagation cones using multiple independent arrays. IEEE Trans. Audio Speech Lang. Process. (TASLP) 20, 1964-1975 (2012) · Zbl 1345.94012 · doi:10.1109/TASL.2012.2191958
[24] Compagnoni, M., Canclini, A., Bestagini, P., Antonacci, F., Sarti, A.: Source localization and denoising: a perspective from the TDOA space. J. Multi-Dimens. Syst. Signal Process. doi:10.1007/s11045-016-0400-9 (2016a) · Zbl 1387.94031
[25] Compagnoni, M., Notari, R., Antonacci, F., Sarti, A.: On the statistical model of source localization based on range difference measurements. arXiv:1606.08303 (2016b) · Zbl 1373.93320
[26] Compagnoni, M., Notari, R.: Tdoa-based localization in two dimension: the bifurcation curve. Fundam. Inform. 135, 199-210 (2014) · Zbl 1342.94017
[27] Compagnoni, M., Notari, R., Antonacci, F., Sarti, A.: A comprehensive analysis of the geometry of TDOA maps in localization problems. Inverse Probl. 30(3), 035004 (2014) · Zbl 1290.94008 · doi:10.1088/0266-5611/30/3/035004
[28] Costa, J.A., Patwari, N., Hero, A.O.: Distributed weighted-multidimensional scaling for node localization in sensor networks. ACM Trans. Sens. Netw. (TOSN) 2(1), 39-64 (2006) · doi:10.1145/1138127.1138129
[29] do Carmo, M.P.: Differential Geometry of Curves and Surfaces. Prentice-Hall, Inc., Englewood Cliffs, NJ (1976) · Zbl 0326.53001
[30] Draisma, J., Horobet, E., Ottaviani, G., Sturmfels, B., Thomas, R.R.: The euclidean distance degree. In: Proceedings of the 2014 Symposium on Symbolic-Numeric Computation, pp. 9-16 (2014) · Zbl 1346.68281
[31] Drton, M., Sturmfels, B., Sullivant, S.: Lectures on Algebraic Statistics, volume 40 of Oberwolfach Seminars Series. Birkhauser, Basel (2009) · Zbl 1166.13001 · doi:10.1007/978-3-7643-8905-5
[32] Drton, M., Sullivant, S.: Algebraic statistical models. Stat. Sin. 17(4), 1273-1297 (2007) · Zbl 1132.62003
[33] Eren, T., Goldenberg, D., Whiteley, W., Yang, Y., Morse, A., Anderson, B., Belhumeur, P.: Rigidity, computation, and randomization in network localization. IEEE Infocom Proc. 4, 2673-2683 (2004)
[34] Fischler, M.A., Bolles, R.C.: Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography. Commun. ACM 24(6), 381-395 (1981) · doi:10.1145/358669.358692
[35] Forman, G., Zahorjan, J.: The challenges of mobile computing. IEEE Comput. 27, 38-47 (1994) · doi:10.1109/2.274999
[36] Friedland, S., Stawiska, M.: Some Approximation Problems in Semi-algebraic Geometry. arXiv:1412.3178v1 [math.AG] (2014) · Zbl 1338.14055
[37] Hudson, R.W.H.T.: Kummer’s Quartic Surface, with a Forward by W. Cambridge University Press, Barth (1990) · Zbl 0716.14025
[38] Ichiki, S., Nishimura, T.: Distance-squared mappings. Topol. Appl. 160, 1005-1016 (2013) · Zbl 1290.57031 · doi:10.1016/j.topol.2013.03.011
[39] Jian, L., Yang, Z., Liu, Y.: Beyond triangle inequality: sifting noisy and outlier distance measurements for localization. In: INFOCOM, 2010 Proceedings IEEE, pp. 1-9 (2010)
[40] Kobayashi, K., Wynn, H.P.: Asymptotically efficient estimators for algebraic statistical manifolds. Lect. Notes Comput. Sci. 8085, 721-728 (2013) · Zbl 1396.62102 · doi:10.1007/978-3-642-40020-9_80
[41] Lasserre, J.B.: An Introduction to Polynomial and Semi-algebraic Optimization. Number 52 in Cambridge Texts in Applied Mathematics. Cambridge University Press, Cambridge (2015) · Zbl 1320.90003 · doi:10.1017/CBO9781107447226
[42] Liberti, L., Lavor, C., Maculan, N., Mucherino, A.: Euclidean distance geometry and applications. SIAM Rev. 56(1), 3-69 (2014) · Zbl 1292.51010 · doi:10.1137/120875909
[43] Menger, K.: Untersuchungen uber allgemeine metrik. Math. Ann. 100, 75-163 (1928) · JFM 54.0622.02 · doi:10.1007/BF01448840
[44] Menger, K.: New foundation of euclidean geometry. Am. J. Math. 53, 721-745 (1931) · JFM 57.1509.01 · doi:10.2307/2371222
[45] Moran, B., Howard, S.D., Cochran, D.: An information-geometric approach to sensor management. In: 2012 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 5261-5264 (2012)
[46] Navidi, W., Murphy, W.S., Hereman, W.: Statistical methods in surveying by trilateration. Comput. Stat. Data Anal. 27(2), 209-227 (1998) · Zbl 1042.62630 · doi:10.1016/S0167-9473(97)00053-4
[47] Pistone, G., Riccomagno, E., Wynn, H.P.: Algebraic Statistics. Computational Commutative Algebra in Statistics. Volume 89 of Monographs on Statistics and Applied Probability. Chapman and Hall/CRC, Boca Raton (2001) · Zbl 0960.62003
[48] Quazi, A.H.: An overview on the time delay estimation in active and passive systems for target localization. IEEE Trans. Acoust. Speech Signal Process. ASSP 29, 527-533 (1981) · doi:10.1109/TASSP.1981.1163618
[49] Savvides, A., Han, C.C., Strivastava, M.: Dynamic fine-grained localization in ad-hoc networks of sensors. In: Proceedings of the 7th Annual International Conference on Mobile Computing and Networking, pp. 166-179 (2001) · Zbl 1390.94417
[50] Schoenberg, I.: Remarks to maurice frèchet’s article “sur la définition axiomatique d’une classe d’espaces distanciès vectoriellement applicable sur l’espace de hilbert”. Ann. Math. 36, 724-732 (1935) · Zbl 0012.30703 · doi:10.2307/1968654
[51] Shen, G., Zetik, R., Thoma, R.S.: Performance comparison of TOA and TDOA based location estimation algorithms in los environment. In: Proceedings of the 5th Workshop on Positioning, Navigation and Communication, pp. 71-78 (2008) · Zbl 1390.94470
[52] Shin, D.H., Sung, T.K.: Comparisons of error characteristics between TOA and TDOA positioning. IEEE Trans. Aerosp. Electron. Syst. 38(1), 307-311 (2002) · doi:10.1109/7.993253
[53] Sippl, M., Scheraga, H.: Cayley-menger coordinates. Proc. Natl. Acad. Sci. USA 83, 2283-2287 (1986) · Zbl 0587.51013 · doi:10.1073/pnas.83.8.2283
[54] So, H., Chan, F.: A generalized subspace approach for mobile positioning with time-of-arrival measurements. IEEE Trans. Signal Process. 55(10), 5103-5107 (2007) · Zbl 1390.94417 · doi:10.1109/TSP.2003.896092
[55] Watanabe, S.: Algebraic Analysis for Singular Statistical Estimation. In: 10th International Conference on Algorithmic Learning Theory, ALT’99, volume 1720 of Lecture Notes in Computer Science, pp. 39-50 (1999) · Zbl 0949.68126
[56] Wei, H.W., Wan, Q., Chen, Z.X., Ye, S.F.: A novel weighted multidimensional scaling analysis for time-of-arrival-based mobile location. IEEE Trans. Signal Process. 56(7), 3018-3022 (2008) · Zbl 1317.62014 · doi:10.1109/TSP.2007.914349
[57] Weiser, M.: Some computer science issues in ubiquitous computing. Commun. ACM 36, 75-84 (1993) · doi:10.1145/159544.159617
[58] Zhayida, S., Burgess, S., Kuang, Y., Åström, K.: Toa-based self-calibration of dual-microphone array. IEEE J. Sel. Top. Signal Process. 9(5), 791-801 (2015) · doi:10.1109/JSTSP.2015.2417117
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.