Document Open Access Logo

The Isomap Algorithm in Distance Geometry

Authors Leo Liberti, Claudia D'Ambrosio

PDF
Thumbnail PDF

File

LIPIcs.SEA.2017.5.pdf
  • Filesize: 1.06 MB
  • 13 pages

Document Identifiers

Author Details

Leo Liberti
Claudia D'Ambrosio

Cite As Get BibTex

Leo Liberti and Claudia D'Ambrosio. The Isomap Algorithm in Distance Geometry. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, pp. 5:1-5:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.SEA.2017.5

Abstract

The fundamental problem of distance geometry consists in finding a realization of a given weighted graph in a Euclidean space of given dimension, in such a way that vertices are realized as points and edges as straight segments having the same lengths as their given weights. This problem arises in structural proteomics, wireless sensor networks, and clock synchronization protocols to name a few applications. The well-known Isomap method is a dimensionality reduction heuristic which projects finite but high dimensional metric spaces into the "most significant" lower dimensional ones, where significance is measured by the magnitude of the corresponding eigenvalues. We start from a simple observation, namely that Isomap can also be used to provide approximate realizations of weighted graphs very efficiently, and then derive and benchmark six new heuristics.

Subject Classification

Keywords
  • distance geometry problem
  • protein conformation
  • heuristics

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. F. Alizadeh. Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM Journal on Optimization, 5(1):13-51, 1995. Google Scholar
  2. A. Bahr, J. Leonard, and M. Fallon. Cooperative localization for autonomous underwater vehicles. International Journal of Robotics Research, 28(6):714-728, 2009. Google Scholar
  3. A. Barvinok. Problems of distance geometry and convex properties of quadratic maps. Discrete and Computational Geometry, 13:189-202, 1995. Google Scholar
  4. A. Barvinok. Measure concentration in optimization. Mathematical Programming, 79:33-53, 1997. Google Scholar
  5. P. Biswas, T. Lian, T. Wang, and Y. Ye. Semidefinite programming based algorithms for sensor network localization. ACM Transactions in Sensor Networks, 2:188-220, 2006. Google Scholar
  6. L. Blum, M. Shub, and S. Smale. On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions, and universal machines. Bulletin of the American Mathematical Society, 21(1):1-46, 1989. Google Scholar
  7. L. Blumenthal. Theory and Applications of Distance Geometry. Oxford University Press, Oxford, 1953. Google Scholar
  8. T. Cox and M. Cox. Multidimensional Scaling. Chapman &Hall, Boca Raton, 2001. Google Scholar
  9. M. Cucuringu, Y. Lipman, and A. Singer. Sensor network localization by eigenvector synchronization over the Euclidean group. ACM Transactions on Sensor Networks, 8:1-42, 2012. Google Scholar
  10. G. Dias and L. Liberti. Diagonally dominant programming in distance geometry. In R. Cerulli, S. Fujishige, and R. Mahjoub, editors, International Symposium in Combinatorial Optimization, volume 9849 of LNCS, pages 225-236, New York, 2016. Springer. Google Scholar
  11. L. Doherty, K. Pister, and L. El Ghaoui. Convex position estimation in wireless sensor networks. In Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies, volume 3 of INFOCOM, pages 1655-1663, Piscataway, 2001. IEEE. Google Scholar
  12. I. Dokmanić, R. Parhizkar, J. Ranieri, and M. Vetterli. Euclidean distance matrices: Essential theory, algorithms and applications. IEEE Signal Processing Magazine, 1053-5888:12-30, Nov. 2015. Google Scholar
  13. R. Fletcher. Practical Methods of Optimization. Wiley, Chichester, second edition, 1991. Google Scholar
  14. D. Hilbert. Grundlagen der Geometrie. Teubner, Leipzig, 1903. Google Scholar
  15. I. Jolliffe. Principal Component Analysis. Springer, Berlin, 2nd edition, 2010. Google Scholar
  16. N. Krislock and H. Wolkowicz. Explicit sensor network localization using semidefinite representations and facial reductions. SIAM Journal on Optimization, 20:2679-2708, 2010. Google Scholar
  17. C. Lavor, L. Liberti, N. Maculan, and A. Mucherino. The discretizable molecular distance geometry problem. Computational Optimization and Applications, 52:115-146, 2012. Google Scholar
  18. L. Liberti and C. Lavor. Six mathematical gems in the history of distance geometry. International Transactions in Operational Research, 23:897-920, 2016. Google Scholar
  19. L. Liberti, C. Lavor, N. Maculan, and A. Mucherino. Euclidean distance geometry and applications. SIAM Review, 56(1):3-69, 2014. Google Scholar
  20. L. Liberti, C. Lavor, and A. Mucherino. The discretizable molecular distance geometry problem seems easier on proteins. In A. Mucherino, C. Lavor, L. Liberti, and N. Maculan, editors, Distance Geometry: Theory, Methods, and Applications, pages 47-60. Springer, New York, 2013. Google Scholar
  21. L. Liberti, C. Lavor, A. Mucherino, and N. Maculan. Molecular distance geometry methods: from continuous to discrete. International Transactions in Operational Research, 18:33-51, 2010. Google Scholar
  22. L. Liberti, G. Swirszcz, and C. Lavor. Distance geometry on the sphere. In JCDCG², LNCS, New York, accepted. Springer. Google Scholar
  23. K. Mehlhorn and P. Sanders. Algorithms and Data Structures. Springer, Berlin, 2008. Google Scholar
  24. K. Menger. Untersuchungen über allgemeine Metrik. Mathematische Annalen, 100:75-163, 1928. Google Scholar
  25. K. Menger. New foundation of Euclidean geometry. American Journal of Mathematics, 53(4):721-745, 1931. Google Scholar
  26. J. Moré and Z. Wu. Global continuation for distance geometry problems. SIAM Journal of Optimization, 7(3):814-846, 1997. Google Scholar
  27. Mosek ApS. The mosek manual, Version 7 (Revision 114), 2014. ěrb+(www.mosek.com)+. Google Scholar
  28. G. Sagnol. PICOS: A Python Interface for Conic Optimization Solvers. Zuse Institut Berlin, 2016. URL: https://picos.zib.de.
  29. J. Saxe. Embeddability of weighted graphs in k-space is strongly NP-hard. Proceedings of 17th Allerton Conference in Communications, Control and Computing, pages 480-489, 1979. Google Scholar
  30. T. Schlick. Molecular modelling and simulation: an interdisciplinary guide. Springer, New York, 2002. Google Scholar
  31. I. Schoenberg. 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". Annals of Mathematics, 36(3):724-732, 1935. Google Scholar
  32. A. Singer. Angular synchronization by eigenvectors and semidefinite programming. Applied and Computational Harmonic Analysis, 30:20-36, 2011. Google Scholar
  33. M. Sippl and H. Scheraga. Cayley-Menger coordinates. Proceedings of the National Academy of Sciences, 83:2283-2287, 1986. Google Scholar
  34. J. Tenenbaum, V. de Silva, and J. Langford. A global geometric framework for nonlinear dimensionality reduction. Science, 290:2319-2322, 2000. Google Scholar
  35. L. Wang, R. Mettu, and B. R. Donald. An algebraic geometry approach to protein structure determination from NMR data. In Proceedings of the Computational Systems Bioinformatics Conference, Piscataway, 2005. IEEE. Google Scholar
  36. K. Wüthrich. Protein structure determination in solution by nuclear magnetic resonance spectroscopy. Science, 243:45-50, 1989. Google Scholar
  37. Y. Yemini. The positioning problem - a draft of an intermediate summary. In Proceedings of the Conference on Distributed Sensor Networks, pages 137-145, Pittsburgh, 1978. Carnegie-Mellon University. Google Scholar
  38. Y. Yemini. Some theoretical aspects of position-location problems. In Proceedings of the 20th Annual Symposium on the Foundations of Computer Science, pages 1-8, Piscataway, 1979. IEEE. URL: http://dx.doi.org/10.1109/SFCS.1979.39.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact