×

Coordinate difference matrices. (English) Zbl 1432.68484

Summary: In many problems such as phase retrieval, molecular biology, source localization, and sensor array calibration, one can measure vector differences between pairs of points and attempt to recover the position of these points; this class of problems is called vector geometry problems (VGPs). A closely related field studies distance geometry problems (DGPs), where only the Euclidean distance between pairs of points is available. This has been extensively studied in the literature and is often associated with Euclidean distance matrices (EDMs). Although similar to DGPs, VGPs have received little attention in the literature; our goal is to fill in this gap and introduce a framework to solve VGPs. Inspired by EDM-related approaches, we arrange the differences in what we call a coordinate difference matrix (CDM) and introduce a methodology to reconstruct a set of points from CDM entries. We first propose a reconstruction scheme in 1D and then generalize it to higher dimensions. We show that our algorithm is optimal in the least-squares sense, even when we have only access to partial measurements. In addition, we provide necessary and sufficient conditions on the number and structure of measurements needed for a successful reconstruction, as well as a comparison with EDMs. In particular we show that compared to EDMs, CDMs are simpler objects, both from an algorithmic and a theoretical point of view. Therefore, CDMs should be favored over EDMs whenever vector differences are available. In the presence of noise, we provide a statistical analysis of the reconstruction error. Finally, we apply the established knowledge to five practical problems to demonstrate the versatility of this theory and showcase the wide range of applications covered by the CDM framework.

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
15A30 Algebraic systems of matrices
15B48 Positive matrices and their generalizations; cones of matrices
51K05 General theory of distance geometry

Software:

DYANA; LSQR; CRAIG; CYANA; word2vec
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] B. Alipanahi Ramandi, New Approaches to Protein NMR Automation, Ph.D. thesis, University of Waterloo, Waterloo, Canada, 2011.
[2] K. S. Arun, T. S. Huang, and S. D. Blostein, Least-squares fitting of two \(3\)-d point sets, IEEE Trans. Pattern Anal. Machine Intell., 9 (1987), pp. 698-700.
[3] J. Azcarreta Ortiz, Pyramic array: An FPGA Based Platform for Multi-channel Audio Acquisition, Master’s thesis, EPFL, Lausanne, Switzerland, and Universitat Politècnica de Catalunya, Barcelona, Spain, 2016.
[4] G. Baechler, M. Kreković, J. Ranieri, A. Chebira, Y. M. Lu, and M. Vetterli, Super resolution phase retrieval for sparse signals, IEEE Trans. Signal Process., 67 (2019), pp. 4839-4854. · Zbl 07123401
[5] S. J. Billinge, P. M. Duxbury, D. S. Gonçalves, C. Lavor, and A. Mucherino, Recent results on assigned and unassigned distance geometry with applications to protein molecules and nanostructures, Ann. Oper. Res., 271 (2018), pp. 161-203. · Zbl 1429.51011
[6] S. T. Birchfield and A. Subramanya, Microphone array position calibration by basis-point classical multidimensional scaling, IEEE Trans. Speech Audio Process., 13 (2005), pp. 1025-1034.
[7] P. Biswas, Semidefinite Programming Approaches to Distance Geometry Problems, Ph.D. dissertation, Stanford University, Stanford, CA, 2007.
[8] R. Biswas and S. Thrun, A passive approach to sensor network localization, in IEEE/RSJ International Conference Intelligent Robots and Systems (IROS), IEEE, Washington, DC, 2004, pp. 1544-1549.
[9] O. Bottema and B. Roth, Theoretical Kinematics, Corrected reprint of the 1979 ed., Dover, New York, 1990. · Zbl 0405.70001
[10] W. Braun, C. Bösch, L. R. Brown, N. Gō, and K. Wüthrich, Combined use of proton-proton Overhauser enhancements and a distance geometry algorithm for determination of polypeptide conformations. Application to micelle-bound glucagon, Biochimica et Biophysica Acta (BBA) Protein Structure, 667 (1981), pp. 377-396.
[11] W. Braun and N. Gō, Calculation of protein conformations by proton-proton distance constraints: A new efficient algorithm, J. Molecular Biol., 186 (1985), pp. 611-626.
[12] J. Bruck, J. Gao, and A. A. Jiang, Localization and routing in sensor networks by local angle information, ACM Trans. Sensor Networks, 5 (2009), 7.
[13] F. Buekenhout and M. Parker, The number of nets of the regular convex polytopes in dimension \(\leq 4\), Discrete Math., 186 (1998), pp. 69-94. · Zbl 0956.52014
[14] T. Callaghan, P. J. Mucha, and M. A. Porter, Random walker ranking for NCAA division I-A football, Amer. Math. Monthly, 114 (2007), pp. 761-777. · Zbl 1143.60036
[15] T. P. Chartier, E. Kreutzer, A. N. Langville, and K. E. Pedings, Sensitivity and stability of ranking vectors, SIAM J. Sci. Comput., 33 (2011), pp. 1077-1102, https://doi.org/10.1137/090772745. · Zbl 1237.65011
[16] M. Cieliebak, S. Eidenbenz, and P. Penna, Partial digest is hard to solve for erroneous input data, Theoret. Comput. Sci., 349 (2005), pp. 361-381. · Zbl 1086.68053
[17] W. N. Colley, Colley’s Bias Free College Football Ranking Method: The Colley Matrix Explained, Princeton University, Press, Princeton, NJ, 2002.
[18] M. Crocco, A. D. Bue, and V. Murino, A bilinear approach to the position self-calibration of multiple sensors, IEEE Trans. Signal Process., 60 (2012), pp. 660-673. · Zbl 1393.94549
[19] T. Dakic, On the Turnpike Problem, Ph.D. thesis, Simon Fraser University, Burnaby, BC, Canada, 2000.
[20] J. Dattorro, Convex Optimization and Euclidean Distance Geometry, Meboo, Palo Alto, CA, 2005. · Zbl 1142.15014
[21] J. De Leeuw, Applications of Convex Analysis to Multidimensional Scaling, Department of Statistics, UCLA, Los Angeles, CA, 2005.
[22] I. Dokmanić, L. Daudet, and M. Vetterli, From acoustic room reconstruction to SLAM, in Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), IEEE, Washington, DC, 2016, pp. 6345-6349.
[23] I. Dokmanić, R. Parhizkar, J. Ranieri, and M. Vetterli, Euclidean distance matrices: Essential theory, algorithms, and applications, IEEE Signal Process. Mag., 32 (2015), pp. 12-30.
[24] I. Dokmanić, R. Parhizkar, A. Walther, Y. M. Lu, and M. Vetterli, Acoustic echoes reveal room shape, Proc. Natl. Acad. Sci. USA, 110 (2013), pp. 12186-12191.
[25] T. Du, S. Qu, Q. Guo, and L. Zhu, A simple efficient anchor-free node localization algorithm for wireless sensor networks, Internat. J. Distributed Sensor Networks, 13 (2017), https://doi.org/10.1177/1550147717705784.
[26] P. Duxbury, L. Granlund, S. Gujarathi, P. Juhas, and S. Billinge, The unassigned distance geometry problem, Discrete Appl. Math., 204 (2016), pp. 117-132. · Zbl 1333.05093
[27] X. Feng, P. J. E. Verdegem, Y. K. Lee, D. Sandström, M. Edén, P. Bovee-Geurts, W. J. de Grip, J. Lugtenburg, H. J. M. de Groot, and M. H. Levitt, Direct determination of a molecular torsional angle in the membrane protein rhodopsin by solid-state NMR, J. Amer. Chem. Soc., 119 (1997), pp. 6853-6857.
[28] B. P. Flanagan and K. L. Bell, Array self-calibration with large sensor position errors, Signal Process., 81 (2001), pp. 2201-2214.
[29] J. Frey, A ranking method based on minimizing the number of in-sample errors, Amer. Statist., 59 (2005), pp. 207-216.
[30] N. Gaffke and R. Mathar, A cyclic projection algorithm via duality, Metrika, 36 (1989), pp. 29-54. · Zbl 0676.90054
[31] S. Gannot, E. Vincent, S. Markovich-Golan, and A. Ozerov, A consolidated perspective on multimicrophone speech enhancement and source separation, IEEE/ACM Trans. Audio Speech Language Process., 25 (2017), pp. 692-730.
[32] N. D. Gaubitch, W. B. Kleijn, and R. Heusdens, Auto-localization in ad-hoc microphone arrays, in Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), IEEE, Washington, DC, 2013, pp. 106-110.
[33] S. Gerschgorin, Über die Abgrenzung der Eigenwerte einer Matrix, Izv. Akad. Nauk. USSR. Otd. Fiz-Mat. Nauk, 7 (1931), pp. 749-754. · JFM 57.1340.06
[34] M. D. Gillette and H. F. Silverman, A linear closed-form algorithm for source localization from time-differences of arrival, IEEE Signal Process. Lett., 15 (2008), pp. 1-4.
[35] W. Glunt, T. Hayden, and M. Raydan, Molecular conformations from distance matrices, J. Comput. Chem., 14 (1993), pp. 114-120.
[36] A. Y. Govan, A. N. Langville, and C. D. Meyer, Offense-defense approach to ranking team sports, J. Quant. Anal. Sports, 5 (2009), 4.
[37] V. Gulshan, L. Peng, M. Coram, M. C. Stumpe, D. Wu, A. Narayanaswamy, S. Venugopalan, K. Widner, T. Madams, J. Cuadros, et al., Development and validation of a deep learning algorithm for detection of diabetic retinopathy in retinal fundus photographs, JAMA, 316 (2016), pp. 2402-2410.
[38] P. Güntert, Automated NMR structure calculation with CYANA, in Protein NMR Techniques, Springer, New York, 2004, pp. 353-378.
[39] P. Güntert, C. Mumenthaler, and K. Wüthrich, Torsion angle dynamics for NMR structure calculation with the new program Dyana, J. Molecular Biol., 273 (1997), pp. 283-298.
[40] L. Guttman, A general nonmetric technique for finding the smallest coordinate space for a configuration of points, Psychometrika, 33 (1968), pp. 469-506. · Zbl 0205.49302
[41] K. M. Hall, An r-dimensional quadratic placement algorithm, Management Sci., 17 (1970), pp. 219-229. · Zbl 0203.52503
[42] G. W. Hart, Multidimensional Analysis: Algebras and Systems for Science and Engineering, Springer-Verlag, New York, 1995. · Zbl 0889.00009
[43] T. F. Havel, Distance geometry: Theory, algorithms and chemical applications, in Encyclopedia of Computational Chemistry, John Wiley & Sons, New York, 1998, pp. 723-742.
[44] R. A. Horn and C. R. Johnson, Matrix Analysis, Cambridge University Press, Cambridge, UK, 2012.
[45] T. Jech, The ranking of incomplete tournaments: A mathematician’s guide to popular sports, Amer. Math. Monthly, 90 (1983), pp. 246-266. · Zbl 0519.05034
[46] C. R. Johnson, Inverse M-matrices, Linear Algebra Appl., 47 (1982), pp. 195-216. · Zbl 0488.15011
[47] J. P. Keener, The Perron-Frobenius theorem and the ranking of football teams, SIAM Rev., 35 (1993), pp. 80-93, https://doi.org/10.1137/1035004. · Zbl 0788.62064
[48] D. Kihara, H. Chen, and Y. David Yang, Quality assessment of protein structure models, Current Protein Peptide Sci., 10 (2009), pp. 216-28.
[49] J. B. Kruskal, Multidimensional scaling by optimizing goodness of fit to a nonmetric hypothesis, Psychometrika, 29 (1964), pp. 1-27. · Zbl 0123.36803
[50] Y. Kuang, E. Ask, S. Burgess, and K. \AAström, Understanding TOA and TDOA network calibration using far field approximation as initial estimate, in Proceedings of the International Conference on Pattern Recognition Applications and Methods, Algarve, Portugal, 2012, pp. 590-596.
[51] Y. Kuang, S. Burgess, A. Torstensson, and K. \AAström, A complete characterization and solution to the microphone position self-calibration problem, in Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), IEEE, Washington, DC, 2013, pp. 3875-3879.
[52] P. Kułakowski, J. Vales-Alonso, E. Egea-López, W. Ludwin, and J. García-Haro, Angle-of-arrival localization based on antenna arrays for wireless sensor networks, Comput. Electrical Engrg., 36 (2010), pp. 1181-1186. · Zbl 1202.94152
[53] L. Liberti, C. Lavor, N. Maculan, and A. Mucherino, Euclidean distance geometry and applications, SIAM Rev., 56 (2014), pp. 3-69, https://doi.org/10.1137/120875909. · Zbl 1292.51010
[54] D. Macagnano and G. T. F. De Abreu, Algebraic approach for robust localization with heterogeneous information, IEEE Trans. Wireless Commun., 12 (2013), pp. 5334-5345.
[55] D. Malioutov, M. Cetin, and A. Willsky, A sparse signal reconstruction perspective for source localization with sensor arrays, IEEE Trans. Signal Process., 53 (2005), pp. 3010-3022. · Zbl 1370.94191
[56] K. Massey, Statistical Models Applied to the Rating of Sports Teams, Bluefield College, Bluefield, VA, 1997.
[57] S. Mika, G. Ratsch, J. Weston, B. Scholkopf, and K. R. Mullers, Fisher discriminant analysis with kernels, in Neural Networks for Signal Processing IX: Proceedings of the 1999 IEEE Signal Processing Society Workshop, IEEE, Washington, DC, 1999, pp. 41-48.
[58] T. Mikolov, I. Sutskever, K. Chen, G. S. Corrado, and J. Dean, Distributed representations of words and phrases and their compositionality, in Advances in Neural Information Processing Systems, NeurIPS, San Diego, CA, 2013, pp. 3111-3119.
[59] A. Mucherino, C. Lavor, and L. Liberti, The discretizable distance geometry problem, Optim. Lett., 6 (2012), pp. 1671-1686. · Zbl 1258.90100
[60] P. Nicolas and G. Vezzosi, Localization of Far-Field Sources with an Array of Unknown Geometry, Springer, Dordrecht, The Netherlands, 1989, pp. 503-509.
[61] N. Ono, H. Kohno, N. Ito, and S. Sagayama, Blind alignment of asynchronously recorded signals for distributed microphone array, in Proceedings of the IEEE Workshop on Applications of Signal Processing to Audio and Acoustics (WASPAA), IEEE, Washington, DC, 2009, pp. 161-164.
[62] B. Osting, C. Brune, and S. J. Osher, Optimal data collection for informative rankings expose well-connected graphs, J. Mach. Learn. Res., 15 (2014), pp. 2981-3012. · Zbl 1319.62046
[63] C. C. Paige and M. A. Saunders, LSQR: An algorithm for sparse linear equations and sparse least squares, ACM Trans. Math. Softw., 8 (1982), pp. 43-71. · Zbl 0478.65016
[64] H. Pan, R. Scheibler, E. Bezzam, I. Dokmanic, and M. Vetterli, FRIDA: FRI-based DOA estimation for arbitrary array layouts, in Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), IEEE, Washington, DC, 2017, pp. 3186-3190.
[65] R. Parhizkar, Euclidean Distance Matrices: Properties, Algorithms and Applications, Ph.D. thesis, École Polytechnique Fédérale de Lausanne (EPFL), Lausanne, Switzerland, 2013.
[66] J. Parsons, J. B. Holmes, J. M. Rojas, J. Tsai, and C. E. M. Strauss, Practical conversion from torsion space to Cartesian space for in silico protein synthesis, J. Comput. Chem., 26 (2005), pp. 1063-1068.
[67] R. Peng and M. L. Sichitiu, Angle of arrival localization for wireless sensor networks, in Proceedings of the 3rd Annual IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks, IEEE, Washington, DC, 2006, pp. 374-382.
[68] G. Poole and T. Boullion, A survey on M-matrices, SIAM Rev., 16 (1974), pp. 419-427, https://doi.org/10.1137/1016079. · Zbl 0292.15009
[69] Y. Saad, Iterative Methods for Sparse Linear Systems, SIAM, Philadelphia, 2003, https://doi.org/10.1137/1.9780898718003. · Zbl 1031.65046
[70] R. Scheibler, J. Azcarreta, R. Beuchat, and C. Ferry, Pyramic: Full stack open microphone array architecture and dataset, in Proceedings of the 16th International Workshop on Acoustic Signal Enhancement (IWAENC), Tokyo, Japan, 2018, pp. 226-230.
[71] R. O. Schmidt, Multiple emitter location and signal parameter estimation, IEEE Trans. Antennas and Propagation., 34 (1986), pp. 276-280.
[72] B. Schölkopf, A. Smola, and K.-R. Müller, Nonlinear component analysis as a kernel eigenvalue problem, Neural Comput., 10 (1998), pp. 1299-1319.
[73] S. Shiraishi, T. Obata, and M. Daigo, Properties of a positive reciprocal matrix and their application to AHP, J. Oper. Res. Soc. Japan, 41 (1998), pp. 404-414. · Zbl 1003.15019
[74] D. A. Spielman and S.-H. Teng, Nearly linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems, SIAM J. Matrix Anal. Appl., 35 (2014), pp. 835-885, https://doi.org/10.1137/090771430. · Zbl 1311.65031
[75] C. H. Suh and C. W. Radcliffe, Kinematics and Mechanisms Design, Wiley, New York, 1987.
[76] S. Thrun, Affine structure from sound, in Advances in Neural Information Processing Systems 18, NeurIPS, San Diego, CA, 2006, p. 1353.
[77] D. S. W. Ting, C. Y.-L. Cheung, G. Lim, G. S. W. Tan, N. D. Quang, A. Gan, H. Hamzah, R. Garcia-Franco, I. Y. San Yeo, S. Y. Lee, et al., Development and validation of a deep learning system for diabetic retinopathy and related eye diseases using retinal images from multiethnic populations with diabetes, JAMA, 318 (2017), pp. 2211-2223.
[78] P. D. Turney and P. Pantel, From frequency to meaning: Vector space models of semantics, J. Artificial Intell. Res., 37 (2010), pp. 141-188. · Zbl 1185.68765
[79] M. Vetterli, J. Kovačević, and V. K. Goyal, Foundations of Signal Processing, Cambridge University Press, Cambridge, UK, 2014.
[80] J. Wendeberg, F. Höflinger, C. Schindelhauer, and L. Reindl, Calibration-free TDOA self-localisation, J. Location Based Services, 7 (2013), pp. 121-144.
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.