Distance geometry and data science. (English) Zbl 1511.51006
Tha aim of this large paper is to discuss various approaches to the basic distance geometry problem and its applications in data science, thereby visiting many current highlights in optimization research.
First the field of mathematical programming is formalized and classified, including reformulations, relaxations and approximations. Then distance geometry is defined as the NP-hard problem of embedding an undirected edge-weighted graph in Euclidean space of given dimension such that the weights equal the corresponding vertex distances, with applications in engineering, protein folding and data mining, the last being further developed.
After showing how different kinds of data, such as process descriptions, text, databases and abductive inference, may be represented as weighted graphs, it is argued that the particular data science tasks of classification and clustering may be applied to graph-data after vectorization by distance geometry, using e.g. \(k\)-means or artificial neural networks, while clustering of the vertices of a graph may be done using spectral or modularity clustering.
Several mathematical programming methods for obtaining robust approximate solutions to distance geometry are detailed for the usual case of perturbed weight data. An unconstrained quartic formulation minimizing the sum of squared square-differences, and two constrained variants may be tackled by a local nonlinear solver. A relaxation of distance geometry may be cast into a semidefinite programming problem solvable for low dimension by interior point methods, which for high dimensions may be further relaxed to diagonally dominant form yielding a linear program. Some fast exact, but very high dimensional embeddings may be obtained by incidence vectors, the Frechet max-norm embedding, or by multidimensional scaling.
Embedding dimension may be reduced using principal component analysis, Isomap, Barvinok’s probabilistic ‘naive method’, and finally by random projections using the fact that these preserve (euclidean) norms on average.
Very disturbing for most of these methods is the phenomenon of distance instability and concentration of distances in high dimension: it is shown that as dimension increases the difference between smallest and largest distance between pairs of points tends to zero in probability.
The survey ends in an exercise of natural language clustering by way of artificial neural networks, comparing several of the techniques described.
First the field of mathematical programming is formalized and classified, including reformulations, relaxations and approximations. Then distance geometry is defined as the NP-hard problem of embedding an undirected edge-weighted graph in Euclidean space of given dimension such that the weights equal the corresponding vertex distances, with applications in engineering, protein folding and data mining, the last being further developed.
After showing how different kinds of data, such as process descriptions, text, databases and abductive inference, may be represented as weighted graphs, it is argued that the particular data science tasks of classification and clustering may be applied to graph-data after vectorization by distance geometry, using e.g. \(k\)-means or artificial neural networks, while clustering of the vertices of a graph may be done using spectral or modularity clustering.
Several mathematical programming methods for obtaining robust approximate solutions to distance geometry are detailed for the usual case of perturbed weight data. An unconstrained quartic formulation minimizing the sum of squared square-differences, and two constrained variants may be tackled by a local nonlinear solver. A relaxation of distance geometry may be cast into a semidefinite programming problem solvable for low dimension by interior point methods, which for high dimensions may be further relaxed to diagonally dominant form yielding a linear program. Some fast exact, but very high dimensional embeddings may be obtained by incidence vectors, the Frechet max-norm embedding, or by multidimensional scaling.
Embedding dimension may be reduced using principal component analysis, Isomap, Barvinok’s probabilistic ‘naive method’, and finally by random projections using the fact that these preserve (euclidean) norms on average.
Very disturbing for most of these methods is the phenomenon of distance instability and concentration of distances in high dimension: it is shown that as dimension increases the difference between smallest and largest distance between pairs of points tends to zero in probability.
The survey ends in an exercise of natural language clustering by way of artificial neural networks, comparing several of the techniques described.
Reviewer: Frank Plastria (Brussels)
MSC:
| 51K05 | General theory of distance geometry |
| 90C26 | Nonconvex programming, global optimization |
| 90C22 | Semidefinite programming |
| 68R12 | Metric embeddings as related to computational problems and algorithms |
| 68T07 | Artificial neural networks and deep learning |
| 68W20 | Randomized algorithms |
| 62H30 | Classification and discrimination; cluster analysis (statistical aspects) |
| 62R07 | Statistical aspects of big data and data science |
Keywords:
Euclidean distance; isometric embedding; random projection; mathematical programming; machine learning; artificial neural networksSoftware:
SNOPT; COIN-OR; CPLEX; Ipopt; WordNet; NetworkX; Scikit; Adam; NLTK; SCS; ROSE; Python; SPOTless; Keras; TensorFlow; word2vecReferences:
| [1] | Abadi M et al (2015) TensorFlow: large-scale machine learning on heterogeneous systems. Software available from tensorflow.org. http://tensorflow.org/ |
| [2] | Achlioptas, D., Database-friendly random projections: Johnson-Lindenstrauss with binary coins, J Comput Syst Sci, 66, 671-687 (2003) · Zbl 1054.68040 |
| [3] | Aggarwal C, Hinneburg A, Keim D (2001) On the surprising behavior of distance metrics in high dimensional space. In: den Bussche JV, Vianu V (eds) Proceedings of ICDT, LNCS, vol 1973. Springer, Berlin, pp 420-434 · Zbl 1047.68038 |
| [4] | Ahmadi, A.; Majumdar, A., DSOS and SDSOS optimization: more tractable alternatives to sum of squares and semidefinite optimization, SIAM J Appl Algebra Geom, 3, 2, 193-230 (2019) · Zbl 1465.90061 |
| [5] | Ahmadi, A.; Jungers, R.; Parrilo, P.; Roozbehani, M., Joint spectral radius and path-complete graph Lyapunov functions, SIAM J Control Optim, 52, 1, 687-717 (2014) · Zbl 1292.93093 |
| [6] | Ailon N, Chazelle B (2006) Approximate nearest neighbors and fast Johnson-Lindenstrauss lemma. In: Proceedings of the symposium on the theory of computing, STOC, vol. ’06. ACM, Seattle · Zbl 1301.68232 |
| [7] | Alfakih, A.; Khandani, A.; Wolkowicz, H., Solving Euclidean distance matrix completion problems via semidefinite programming, Comput Optim Appl, 12, 13-30 (1999) · Zbl 1040.90537 |
| [8] | Allen G (2012) Sparse higher-order principal components analysis. In: N. Lawrence, M. Girolami (eds) Proceedings of the international conference on Artificial intelligence and Statistics, vol 22, pp 27-36. PMLR, La Palma |
| [9] | Allen-Zhu, Z.; Gelashvili, R.; Micali, S.; Shavit, N., Sparse sign-consistent Johnson-Lindenstrauss matrices: Compression with neuroscience-based constraints, Proc Natl Acad Sci, 111, 47, 16872-16876 (2014) |
| [10] | Aloise, D.; Cafieri, S.; Caporossi, G.; Hansen, P.; Perron, S.; Liberti, L., Column generation algorithms for exact modularity maximization in networks, Phys Rev E, 82, 4, 046112 (2010) |
| [11] | Aloise, D.; Hansen, P.; Liberti, L., An improved column generation algorithm for minimum sum-of-squares clustering, Math Program A, 131, 195-220 (2012) · Zbl 1236.90095 |
| [12] | Aloise, D.; Caporossi, G.; Hansen, P.; Liberti, L.; Perron, S.; Ruiz, M.; Bader, D.; Sanders, P.; Wagner, D., Modularity maximization in networks by variable neighbourhood search, Graph partitioning and graph clustering, contemporary mathematics, 113-127 (2013), Providence: AMS, Providence · Zbl 1276.90055 |
| [13] | Amaldi, E.; Liberti, L.; Maffioli, F.; Maculan, N., Edge-swapping algorithms for the minimum fundamental cycle basis problem, Math Methods Oper Res, 69, 205-223 (2009) · Zbl 1163.90036 |
| [14] | Anderson, J., An introduction to neural networks (1995), Cambridge: MIT Press, Cambridge · Zbl 0850.68263 |
| [15] | Arriaga, R.; Vempala, S., An algorithmic theory of learning: Robust concepts and random projection, Mach Learn, 63, 161-182 (2006) · Zbl 1095.68092 |
| [16] | Asimow, L.; Roth, B., The rigidity of graphs, Trans AMS, 245, 279-289 (1978) · Zbl 0392.05026 |
| [17] | Bahr, A.; Leonard, J.; Fallon, M., Cooperative localization for autonomous underwater vehicles, Int J Robot Res, 28, 6, 714-728 (2009) |
| [18] | Barker, G.; Carlson, D., Cones of diagonally dominant matrices, Pac J Math, 57, 1, 15-32 (1975) · Zbl 0283.52005 |
| [19] | Barvinok A (2002) A course in convexity, No. 54 in graduate studies in mathematics. AMS, Providence |
| [20] | Barvinok, A., Problems of distance geometry and convex properties of quadratic maps, Discrete Comput Geom, 13, 189-202 (1995) · Zbl 0829.05025 |
| [21] | Barvinok, A., Measure concentration in optimization, Math Program, 79, 33-53 (1997) · Zbl 0887.90184 |
| [22] | Beeker N, Gaubert S, Glusa C, Liberti L (2013) Is the distance geometry problem in NP? In: Mucherino A., Lavor C., Liberti L., Maculan N. (eds) Distance geometry. Springer, New York, NY, pp 85-94 · Zbl 1271.68111 |
| [23] | Belotti, P.; Lee, J.; Liberti, L.; Margot, F.; Wächter, A., Branching and bounds tightening techniques for non-convex MINLP, Optim Methods Softw, 24, 4, 597-634 (2009) · Zbl 1179.90237 |
| [24] | ben Judah of Worms E (XII-XIII Century) Sodei Razayya |
| [25] | Bengio, Y.; Lamblin, P.; Popovici, D.; Larochelle, H., Greedy layer-wise training of deep networks, Advances in neural information processing systems. NIPS, 153-160 (2007), Cambridge: MIT Press, Cambridge |
| [26] | Ben-Tal, A.; Ghaoui, LE; Nemirovski, A., Robust optimization (2009), Princeton: Princeton University Press, Princeton · Zbl 1221.90001 |
| [27] | Beyer K, Goldstein J, Ramakrishnan R, Shaft U (1998) When is “nearest neighbor” meaningful? In: Beeri C, Buneman P (eds) Proceedings of ICDT, LNCS, vol 1540. Springer, Heidelberg, pp 217-235 |
| [28] | Bird, S.; Klein, E.; Loper, E., Natural language processing with Python (2009), Cambridge: O’Reilly, Cambridge · Zbl 1187.68630 |
| [29] | Birge, J.; Louveaux, F., Introduction to stochastic programming (2011), New York: Springer, New York · Zbl 1223.90001 |
| [30] | Blömer, J.; Lammersen, C.; Schmidt, M.; Sohler, C.; Kliemann, L.; Sanders, P., Theoretical analysis of the k-means algorithm: a survey, Algorithm engineering, LNCS, 81-116 (2016), Cham: Springer, Cham |
| [31] | Blumenthal, L., Theory and applications of distance geometry (1953), Oxford: Oxford University Press, Oxford · Zbl 0050.38502 |
| [32] | Böhm, C.; Jacopini, G., Flow diagrams, Turing machines and languages with only two formation rules, Commun ACM, 9, 5, 366-371 (1966) · Zbl 0145.24204 |
| [33] | Bollobás, B., Modern graph theory (1998), New York: Springer, New York · Zbl 0902.05016 |
| [34] | Borg, I.; Groenen, P., Modern multidimensional scaling (2010), New York: Springer, New York · Zbl 0850.62022 |
| [35] | Bottou, L.; Montavon, G., Stochastic gradient descent tricks, Neural networks: tricks of the trade, LNCS, 421-436 (2012), Berlin: Springer, Berlin |
| [36] | Bourgain, J., On Lipschitz embeddings of finite metric spaces in Hilbert space, Isr J Math, 52, 1-2, 46-52 (1985) · Zbl 0657.46013 |
| [37] | Boutsidis, C.; Zouzias, A.; Drineas, P., Random projections for \(k\)-means clustering, Advances in neural information processing systems. NIPS, 298-306 (2010), La Jolla: NIPS Foundation, La Jolla |
| [38] | Brambilla, A.; Premoli, A., Rigorous event-driven (red) analysis of large-scale nonlinear rc circuits, IEEE Trans Circ Syst I Fundam Theory Appl, 48, 8, 938-946 (2001) |
| [39] | Brandes, U.; Delling, D.; Gaertler, M.; Görke, R.; Hoefer, M.; Nikoloski, Z.; Wagner, D., On modularity clustering, IEEE Trans Knowl Data Eng, 20, 2, 172-188 (2008) |
| [40] | Cafieri, S.; Hansen, P.; Liberti, L., Loops and multiple edges in modularity maximization of networks, Phys Rev E, 81, 4, 46102 (2010) |
| [41] | Cafieri, S.; Hansen, P.; Liberti, L., Locally optimal heuristic for modularity maximization of networks, Phys Rev E, 83, 56105, 1-8 (2011) |
| [42] | Cafieri, S.; Hansen, P.; Liberti, L., Improving heuristics for network modularity maximization using an exact algorithm, Discrete Appl Math, 163, 65-72 (2014) · Zbl 1303.90112 |
| [43] | Cauchy, AL, Sur les polygones et les polyèdres, Journal de l’École Polytechnique, 16, 9, 87-99 (1813) |
| [44] | Cayley, A., A theorem in the geometry of position, Camb Math J, II, 267-271 (1841) |
| [45] | Chollet F et al (2015) Keras. https://keras.io |
| [46] | Chomsky, N., Aspects of the theory of syntax (1965), Cambridge: MIT Press, Cambridge |
| [47] | Choromanska A, Henaff M, Mathieu M, Arous GB, LeCun Y (2015) The loss surfaces of multilayer networks. In: Proceedings of the international conference on artificial intelligence and statistics, AISTATS, vol 18. JMLR, San Diego |
| [48] | COIN-OR (2006) Introduction to IPOPT: a tutorial for downloading, installing, and using IPOPT |
| [49] | Collobert, R.; Weston, J.; Bottou, L.; Karlen, M.; Kavukcuoglu, K.; Kuksa, P., Natural language processing (almost) from scratch, J Mach Learn Res, 12, 2461-2505 (2011) · Zbl 1280.68161 |
| [50] | Connelly, R., A counterexample to the rigidity conjecture for polyhedra, Publications Mathématiques de l’IHES, 47, 333-338 (1978) · Zbl 0375.53034 |
| [51] | Cox, T.; Cox, M., Multidimensional scaling (2001), Boca Raton: Chapman & Hall, Boca Raton · Zbl 1004.91067 |
| [52] | D’Ambrosio, C.; Liberti, L.; Nielsen, F.; Barbaresco, F., Distance geometry in linearizable norms, Geometric science of information, LNCS, 830-838 (2017), Berlin: Springer, Berlin · Zbl 1428.51005 |
| [53] | D’Ambrosio C, Liberti L, Poirion PL, Vu K (2019) Random projections for quadratic programming. Math Program B (in revision) |
| [54] | D’Ambrosio C, Liberti L, Poirion PL, Vu K (2019) Random projections for quadratic programming. Tech. Rep. 2019-7-7322, Optimization Online |
| [55] | Dantzig, G.; Bachem, A.; Grötschel, M.; Korte, B., Reminiscences about the origins of linear programming, Mathematical programming: the state of the art (1983), Berlin: Springer, Berlin · Zbl 0538.90049 |
| [56] | Dasgupta, S.; Gupta, A., An elementary proof of a theorem by Johnson and Lindenstrauss, Random Struct Algorithms, 22, 60-65 (2002) · Zbl 1018.51010 |
| [57] | D’Aspremont, A.; Bach, F.; Ghaoui, LE, Approximation bounds for sparse principal component analysis, Math Program B, 148, 89-110 (2014) · Zbl 1303.90079 |
| [58] | Dattorro J (2015) Convex optimization and Euclidean distance geometry. \({\cal M}\epsilon \beta oo\), Palo Alto |
| [59] | Dauphin, Y.; Pascanu, R.; Gulcehre, C.; Cho, K.; Ganguli, S.; Bengio, Y., Identifying and attacking the saddle point problem in high-dimensional non-convex optimization, Advances in neural information processing systems. NIPS, 2933-2941 (2014), La Jolla: NIPS Foundation, La Jolla |
| [60] | Demartines, P.; Hérault, J., Curvilinear component analysis: a self-organizing neural network for nonlinear mapping of data sets, IEEE Trans Neural Netw, 8, 1, 148-154 (1997) |
| [61] | Deo, N.; Prabhu, G.; Krishnamoorthy, M., Algorithms for generating fundamental cycles in a graph, ACM Trans Math Softw, 8, 1, 26-42 (1982) · Zbl 0477.68070 |
| [62] | Dey S, Mazumder R, Molinaro M, Wang G (2017) Sparse principal component analysis and its \(\ell_1\)-relaxation. Tech. Rep. arXiv:1712.00800v1 |
| [63] | Dias, G.; Liberti, L.; Cerulli, R.; Fujishige, S.; Mahjoub, R., Diagonally dominant programming in distance geometry, International symposium in combinatorial optimization, LNCS, 225-236 (2016), New York: Springer, New York · Zbl 1451.51007 |
| [64] | Douven, I.; Zalta, E., Abduction, The Stanford encyclopedia of philosophy (2017), Stanford: Stanford University, Stanford |
| [65] | Durrant, R.; Kabán, A., When is ‘nearest neighbour’ meaningful: a converse theorem and implications, J Complex, 25, 385-397 (2009) · Zbl 1173.62001 |
| [66] | Eco U (1983) Horns, hooves, insteps. Some hypotheses on three kinds of abduction. In: Eco U, Sebeok T (eds) Dupin, Holmes. Peirce. The Sign of Three. Indiana University Press, Bloomington |
| [67] | Eco, U., Semiotics and the philosophy of language (1984), Bloomington: Indiana University Press, Bloomington |
| [68] | Eren T, Goldenberg D, Whiteley W, Yang Y, Morse A, Anderson B, Belhumeur P (2004) Rigidity, computation, and randomization in network localization. IEEE, pp 2673-2684 |
| [69] | Euler, L.; Fuss, P.; Fuss, N., Continuatio fragmentorum ex adversariis mathematicis depromptorum: II Geometria, 97, Opera postuma mathematica et physica anno 1844 detecta, 494-496 (1862), Petropolis: Eggers & C, Petropolis |
| [70] | Fiedler, M., Algebraic connectivity of graphs, Czechoslov Math J, 23, 2, 298-305 (1973) · Zbl 0265.05119 |
| [71] | Flexer, A.; Schnitzer, D., Choosing \(\ell_p\) norms in high-dimensional spaces based on hub analysis, Neurocomputing, 169, 281-287 (2015) |
| [72] | Floreano, D., Manuale sulle Reti Neurali Il (1996), Bologna: Mulino, Bologna |
| [73] | Fortunato, S., Community detection in graphs, Phys Rep, 486, 3-5, 75-174 (2010) |
| [74] | François, D.; Wertz, V.; Verleysen, M., The concentration of fractional distances, IEEE Trans Knowl Data Eng, 19, 7, 873-886 (2007) |
| [75] | Friedler, F.; Huang, Y.; Fan, L., Combinatorial algorithms for process synthesis, Comput Chem Eng, 16, 1, 313-320 (1992) |
| [76] | Gayraud N (2017) Public remark. Le Monde des Mathématiques Industrielles at INRIA Sophia-Antipolis (MOMI17) |
| [77] | Gilbreth F, Gilbreth L (1921) Process charts: first steps in finding the one best way to do work. In: Proceedings of the annual meeting. American Society of Mechanical Engineers, New York |
| [78] | Gill P (2006) User’s guide for SNOPT version 7.2. Systems Optimization Laboratory, Stanford University, California |
| [79] | Gödel, K.; Feferman, S.; Dawson, J.; Kleene, S.; Moore, G.; Solovay, R.; van Heijenoort, J., On the isometric embeddability of quadruples of points of \(r_3\) in the surface of a sphere, Kurt Gödel: collected works, vol I, pp (1933b) 276-279 (1986), Oxford: Oxford University Press, Oxford |
| [80] | Gonçalves, D.; Mucherino, A.; Lavor, C.; Liberti, L., Recent advances on the interval distance geometry problem, J Glob Optim, 69, 525-545 (2017) · Zbl 1382.90084 |
| [81] | Goodfellow, I.; Bengio, Y.; Courville, A., Deep learning (2016), Cambridge: MIT Press, Cambridge · Zbl 1373.68009 |
| [82] | Haeffele B, Vidal R (2017) Global optimality in neural network training. In: Proceedings of the conference in computer vision and pattern recognition, CVPR. IEEE, Piscataway, pp 4390-4398 |
| [83] | Hagberg A, Schult D, Swart P (2008) Exploring network structure, dynamics, and function using NetworkX. In: Varoquaux G, Vaught T, Millman J (eds) Proceedings of the 7th Python in science conference (SciPy2008), Pasadena, pp 11-15 |
| [84] | Hansen, P.; Jaumard, B., Cluster analysis and mathematical programming, Math Program, 79, 191-215 (1997) · Zbl 0887.90182 |
| [85] | Henneberg, L., Die Graphische Statik der starren Systeme (1911), Leipzig: Teubner, Leipzig · JFM 42.0744.10 |
| [86] | Heron (50AD) Metrica, vol I. Alexandria |
| [87] | Hinneburg A, Aggarwal C, Keim D (2000) What is the nearest neighbor in high dimensional spaces? In: Proceedings of the conference on very large databases, VLDB, vol 26. Morgan Kaufman, San Francisco, pp. 506-515 |
| [88] | Hotelling, H., Analysis of a complex of statistical variables into principal components, J Educ Psychol, 24, 6, 417-441 (1933) · JFM 59.1182.04 |
| [89] | IBM (2017) ILOG CPLEX 12.8 User’s Manual. IBM |
| [90] | Indyk, P., Algorithmic applications of low-distortion geometric embeddings, Foundations of computer science. FOCS, 10-33 (2001), Washington, DC: IEEE, Washington, DC |
| [91] | Indyk P, Motwani R (1998) Approximate nearest neighbors: towards removing the curse of dimensionality. In: Proceedings of the symposium on the theory of computing, STOC, vol 30. ACM, New York, pp 604-613 · Zbl 1029.68541 |
| [92] | Indyk P, Naor A (2007) Nearest neighbor preserving embeddings. ACM Trans Algorithms 3(3), Art. 31 · Zbl 1192.68748 |
| [93] | Jain, A.; Murty, M.; Flynn, P., Data clustering: a review, ACM Comput Surv, 31, 3, 264-323 (1999) |
| [94] | Johnson, W.; Lindenstrauss, J.; Hedlund, G., Extensions of Lipschitz mappings into a Hilbert space, Conference in modern analysis and probability, contemporary mathematics, 189-206 (1984), Providence: AMS, Providence · Zbl 0539.46017 |
| [95] | Jolliffe, I., Principal component analysis (2010), Berlin: Springer, Berlin · Zbl 1011.62064 |
| [96] | Jordan M (1995) Why the logistic function? A tutorial discussion on probabilities and neural networks. Tech. Rep. Computational Cognitive Science TR 9503, MIT |
| [97] | Kane, D.; Nelson, J., Sparser Johnson-Lindenstrauss transforms, J ACM, 61, 1, 4 (2014) · Zbl 1295.68134 |
| [98] | Kantor I, Matoušek J, Šámal R (2015) Mathematics++: selected topics beyond the basic courses. No. 75 in Student Mathematical Library. AMS, Providence · Zbl 1330.00003 |
| [99] | Khalife S, Liberti L, Vazirgiannis M (2019) Geometry and analogies: a study and propagation method for word representation. In: Statistical language and speech processing, SLSP, vol. 7 |
| [100] | Kingma D, Ba J (2015)Adam: A method for stochastic optimization. In: Proceedings of ICLR. San Diego |
| [101] | Knuth D (1997) The art of computer programming, part I: fundamental algorithms, 3rd edn. Addison-Wesley, Reading · Zbl 0895.68055 |
| [102] | Kullback, S.; Leibler, R., On information and sufficiency, Ann Math Stat, 22, 1, 79-86 (1951) · Zbl 0042.38403 |
| [103] | Kuratowski, C., Quelques problèmes concernant les espaces métriques non-séparables, Fundam Math, 25, 534-545 (1935) · JFM 61.0221.02 |
| [104] | Lavor, C.; Liberti, L.; Maculan, N.; Pintér, J., Computational experience with the molecular distance geometry problem, Global optimization: scientific and engineering case studies, 213-225 (2006), Berlin: Springer, Berlin · Zbl 1129.90389 |
| [105] | Lavor, C.; Liberti, L.; Maculan, N.; Mucherino, A., The discretizable molecular distance geometry problem, Comput Optim Appl, 52, 115-146 (2012) · Zbl 1259.90153 |
| [106] | Lavor, C.; Liberti, L.; Mucherino, A., The interval Branch-and-Prune algorithm for the discretizable molecular distance geometry problem with inexact distances, J Glob Optim, 56, 855-871 (2013) · Zbl 1272.90074 |
| [107] | Lavor, C.; Liberti, L.; Donald, B.; Worley, B.; Bardiaux, B.; Malliavin, T.; Nilges, M., Minimal NMR distance information for rigidity of protein graphs, Discrete Appl Math, 256, 91-104 (2019) · Zbl 1405.05178 |
| [108] | Lavor, C.; Souza, M.; Carvalho, L.; Liberti, L., On the polynomiality of finding \({}^K\) DMDGP re-orders, Discrete Appl Math, 267, 190-194 (2019) · Zbl 1419.05037 |
| [109] | Lehmann, S.; Hansen, L., Deterministic modularity optimization, Eur Phys J B, 60, 83-88 (2007) |
| [110] | Levine, R.; Mason, T.; Brown, D., Lex and Yacc (1995), Cambridge: O’Reilly, Cambridge |
| [111] | Liberti L (2010) Software modelling and architecture: exercises. Ecole Polytechnique. https://www.lix.polytechnique.fr/ liberti/swarchex.pdf |
| [112] | Liberti, L., Reformulations in mathematical programming: definitions and systematics, RAIRO-RO, 43, 1, 55-86 (2009) · Zbl 1158.90390 |
| [113] | Liberti, L., Undecidability and hardness in mixed-integer nonlinear programming, RAIRO-Oper Res, 53, 81-109 (2019) · Zbl 1414.90237 |
| [114] | Liberti, L.; Lavor, C.; Migdalas, A.; Sifaleras, A.; Georgiadis, C.; Papathanaiou, J.; Stiakakis, E., On a relationship between graph realizability and distance matrix completion, Optimization theory, decision making, and operational research applications, proceedings in mathematics & statistics, 39-48 (2013), Berlin: Springer, Berlin · Zbl 1375.05124 |
| [115] | Liberti, L.; Lavor, C., Six mathematical gems in the history of distance geometry, Int Trans Oper Res, 23, 897-920 (2016) · Zbl 1362.51002 |
| [116] | Liberti, L.; Lavor, C., Euclidean distance geometry: an introduction (2017), New York: Springer, New York · Zbl 1492.51002 |
| [117] | Liberti, L.; Marinelli, F., Mathematical programming: Turing completeness and applications to software analysis, J Comb Optim, 28, 1, 82-104 (2014) · Zbl 1358.68073 |
| [118] | Liberti, L.; Vu, K., Barvinok’s naive algorithm in distance geometry, Oper Res Lett, 46, 476-481 (2018) · Zbl 1476.90286 |
| [119] | Liberti, L.; Lavor, C.; Maculan, N., A branch-and-prune algorithm for the molecular distance geometry problem, Int Trans Oper Res, 15, 1-17 (2008) · Zbl 1136.92037 |
| [120] | Liberti, L.; Cafieri, S.; Tarissan, F.; Abraham, A.; Hassanien, AE; Siarry, P.; Engelbrecht, A., Reformulations in mathematical programming: a computational approach, Foundations of computational intelligence, 153-234 (2009), Berlin: Springer, Berlin · Zbl 1185.68003 |
| [121] | Liberti, L.; Cafieri, S.; Savourey, D.; Fukuda, K.; van der Hoeven, J.; Joswig, M.; Takayama, N., Reformulation optimization software engine, Mathematical software, LNCS, 303-314 (2010), New York: Springer, New York · Zbl 1294.68160 |
| [122] | Liberti, L.; Lavor, C.; Mucherino, A.; Maculan, N., Molecular distance geometry methods: from continuous to discrete, Int Trans Oper Res, 18, 33-51 (2010) · Zbl 1219.90177 |
| [123] | Liberti, L.; Lavor, C.; Alencar, J.; Abud, G.; Nielsen, F.; Barbaresco, F., Counting the number of solutions of \({}^k\) DMDGP instances, Geometric science of information, LNCS, 224-230 (2013), New York: Springer, New York · Zbl 1405.05083 |
| [124] | Liberti, L.; Lavor, C.; Maculan, N.; Mucherino, A., Euclidean distance geometry and applications, SIAM Rev, 56, 1, 3-69 (2014) · Zbl 1292.51010 |
| [125] | Liberti, L.; Masson, B.; Lavor, C.; Lee, J.; Mucherino, A., On the number of realizations of certain Henneberg graphs arising in protein conformation, Discrete Appl Math, 165, 213-232 (2014) · Zbl 1288.05121 |
| [126] | Liberti, L.; Swirszcz, G.; Lavor, C.; Akiyama, J., Distance geometry on the sphere, JCDCG \({}^2\), LNCS, 204-215 (2016), New York: Springer, New York · Zbl 1482.51009 |
| [127] | Liberti L, D’Ambrosio C (2017) The Isomap algorithm in distance geometry. In: Iliopoulos C, Pissis S, Puglisi S, Raman R (eds) Proceedings of 16th international symposium on experimental algorithms (SEA), LIPICS, vol 75. Dagstuhl Publishing, Schloss Dagstuhl, pp 5:1-5:13 · Zbl 1432.68521 |
| [128] | Liberti, L.; Lavor, C.; Mucherino, A.; Mucherino, A.; Lavor, C.; Liberti, L.; Maculan, N., The discretizable molecular distance geometry problem seems easier on proteins, Distance geometry: theory, methods and applications, 47-60 (2013), New York: Springer, New York · Zbl 1366.92094 |
| [129] | Linial, N.; London, E.; Rabinovich, Y., The geometry of graphs and some of its algorithmic applications, Combinatorica, 15, 2, 215-245 (1995) · Zbl 0827.05021 |
| [130] | Majumdar, A.; Ahmadi, A.; Tedrake, R., Control and verification of high-dimensional systems with dsos and sdsos programming, Conference on decision and control, 394-401 (2014), IEEE: Piscataway, IEEE |
| [131] | Malliavin, T.; Mucherino, A.; Lavor, C.; Liberti, L., Systematic exploration of protein conformational space using a distance geometry approach, J Chem Inf Model, 59, 4486-4503 (2019) |
| [132] | Manning, C.; Schütze, H., Foundations of statistical natural language processing (1999), Cambridge: MIT Press, Cambridge · Zbl 0951.68158 |
| [133] | Mansouri, J.; Khademi, M., Multiplicative distance: a method to alleviate distance instability for high-dimensional data, Knowl Inf Syst, 45, 783-805 (2015) |
| [134] | Matoušek J (2013) Lecture notes on metric embeddings. Tech. rep, ETH Zürich |
| [135] | Matoušek, J., On variants of the Johnson-Lindenstrauss lemma, Random Struct Algorithms, 33, 142-156 (2008) · Zbl 1154.51002 |
| [136] | Maxwell, J., On the calculation of the equilibrium and stiffness of frames, Philos Mag, 27, 182, 294-299 (1864) |
| [137] | McCormick, G., Computability of global solutions to factorable nonconvex programs: Part I-Convex underestimating problems, Math Program, 10, 146-175 (1976) · Zbl 0349.90100 |
| [138] | McCulloch, W., What is a number, that a man may know it, and a man, that he may know a number?, Gen Semant Bull, 26-27, 7-18 (1961) |
| [139] | Mencarelli, L.; Sahraoui, Y.; Liberti, L., A multiplicative weights update algorithm for MINLP, EURO J Comput Optim, 5, 31-86 (2017) · Zbl 1396.90050 |
| [140] | Menger, K., Untersuchungen über allgemeine Metrik, Math Ann, 100, 75-163 (1928) · JFM 54.0622.02 |
| [141] | Menger, K., New foundation of Euclidean geometry, Am J Math, 53, 4, 721-745 (1931) · JFM 57.1509.01 |
| [142] | Merris, R., Laplacian matrices of graphs: a survey, Linear Algebra Appl, 198, 143-176 (1994) · Zbl 0802.05053 |
| [143] | Mikolov, T.; Sutskever, I.; Chen, K.; Corrado, G.; Dean, J.; Burges, C.; Bottou, L.; Welling, M.; Ghahramani, Z.; Weinberger, K., Distributed representations of words and phrases and their compositionality, Advances in neural information processing systems, NIPS, 3111-3119 (2013), La Jolla: NIPS Foundation, La Jolla |
| [144] | Miller, G., Wordnet: a lexical database for English, Commun ACM, 38, 11, 39-41 (1995) |
| [145] | Milnor, J., On the Betti numbers of real varieties, Proc AMS, 15, 275-280 (1964) · Zbl 0123.38302 |
| [146] | Minsky, M., The society of mind (1986), New York: Simon & Schuster, New York |
| [147] | Moitra, A., Algorithmic aspects of machine learning (2018), Cambridge: CUP, Cambridge · Zbl 1484.68007 |
| [148] | Moro, A., The boundaries of Babel (2008), Cambridge: MIT Press, Cambridge |
| [149] | Morris, C., Signs. Language and behavior (1946), New York: Prentice-Hall, New York |
| [150] | Mucherino, A.; Lavor, C.; Liberti, L., Exploiting symmetry properties of the discretizable molecular distance geometry problem, J Bioinform Comput Biol, 10, 1-15, 1242009 (2012) · Zbl 1258.90100 |
| [151] | Mucherino, A.; Lavor, C.; Liberti, L.; Maculan, N., Distance geometry: theory, methods, and applications (2013), New York: Springer, New York · Zbl 1256.51002 |
| [152] | Newman, M.; Girvan, M., Finding and evaluating community structure in networks, Phys Rev E, 69, 026113 (2004) |
| [153] | Object Management Group (2005) Unified modelling language: superstructure, v. 2.0. Tech. Rep. formal/05-07-04, OMG |
| [154] | O’Donoghue, B.; Chu, E.; Parikh, N.; Boyd, S., Operator splitting for conic optimization via homogeneous self-dual embedding, J Optim Theory Appl, 169, 3, 1042-1068 (2016) · Zbl 1342.90136 |
| [155] | Paton, K., An algorithm for finding a fundamental set of cycles of a graph, Commun ACM, 12, 9, 514-518 (1969) · Zbl 0176.47205 |
| [156] | Pedregosa, F.; Varoquaux, G.; Gramfort, A.; Michel, V.; Thirion, B.; Grisel, O.; Blondel, M.; Prettenhofer, P.; Weiss, R.; Dubourg, V.; Vanderplas, J.; Passos, A.; Cournapeau, D.; Brucher, M.; Perrot, M.; Duchesnay, E., Scikit-learn: machine learning in Python, J Mach Learn Res, 12, 2825-2830 (2011) · Zbl 1280.68189 |
| [157] | Peirce, C., Illustrations of the logic of science, part 6: induction, deduction, and hypothesis, Popul Sci Mon, 13, 470-482 (1878) |
| [158] | Penrose, R., The emperor’s new mind (1989), New York: Penguin, New York |
| [159] | Pfeffer, A., Practical probabilistic programming (2016), Shelter Island: Manning Publications, Shelter Island |
| [160] | Popper, K., The logic of scientific discovery (1968), London: Hutchinson, London |
| [161] | Potra, F.; Wright, S., Interior-point methods, J Comput Appl Math, 124, 281-302 (2000) · Zbl 0967.65078 |
| [162] | Proni, G., Is there abduction in Aristotle? Peirce, Eco, and some further remarks, Ocula, 17, 1-14 (2016) |
| [163] | Radovanović, M.; Nanopoulos, A.; Ivanović, M., Hubs in space: Popular nearest neighbors in high-dimensional data, J Mach Learn Res, 11, 2487-2531 (2010) · Zbl 1242.62056 |
| [164] | Rousseau F, Vazirgiannis M (2013) Graph-of-word and TW-IDF: new approach to ad hoc IR. In: Proceedings of CIKM. ACM, New York |
| [165] | Saerens M, Fouss F, Yen L, Dupont P (2004) The principal components analysis of a graph, and its relationships to spectral clustering. In: Boulicaut JF, Esposito F, Giannotti F, Pedreschi D (eds) Proceedings of the European conference in machine learning (ECML), LNAI, vol 3201. Springer, Berlin, pp 371-383 · Zbl 1132.68589 |
| [166] | Salgado E, Scozzari A, Tardella F, Liberti L (2018) Alternating current optimal power flow with generator selection. In: Lee J, Rinaldi G, Mahjoub R (eds) Combinatorial optimization (Proceedings of ISCO 2018), LNCS, vol 10856, pp 364-375 · Zbl 1403.90647 |
| [167] | Sánchez, AB; Lavor, C., On the estimation of unknown distances for a class of Euclidean distance matrix completion problems with interval data, Linear Algebra Appl, 592, 287-305 (2020) · Zbl 1436.15030 |
| [168] | Saxe J (1979) 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 |
| [169] | Schaeffer, S., Graph clustering, Comput Sci Rev, 1, 27-64 (2007) · Zbl 1302.68237 |
| [170] | Schmidhuber J (2015) Deep learning in neural networks: an overview. Neural Netw 61:85-117. 10.1016/j.neunet.2014.09.003. arXiv:1404.7828 [cs.NE] |
| [171] | 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, 3, 724-732 (1935) · JFM 61.0435.04 |
| [172] | Schumacher, M.; Roßner, R.; Vach, W., Neural networks and logistic regression: part I, Comput Stat Data Anal, 21, 661-682 (1996) · Zbl 0900.62378 |
| [173] | Seshu S, Reed M (1961) Linear graphs and electrical networks. Addison-Wesley, Reading · Zbl 0102.34001 |
| [174] | Singer, A., Angular synchronization by eigenvectors and semidefinite programming, Appl Comput Harmon Anal, 30, 20-36 (2011) · Zbl 1206.90116 |
| [175] | Smith, E.; Pantelides, C., A symbolic reformulation/spatial branch-and-bound algorithm for the global optimisation of nonconvex MINLPs, Comput Chem Eng, 23, 457-478 (1999) |
| [176] | Steinhaus H (1956) Sur la division des corps matériels en parties. Bulletin de l’Académie Polonaise des Sciences Cl. III 4(12):801-804 · Zbl 0079.16403 |
| [177] | Tabaghi P, Dokmanić I, Vetterli M (2019) On the move: localization with kinetic Euclidean distance matrices. In: International conference on acoustics, speech and signal processing (ICASSP). IEEE, Piscataway |
| [178] | Tawarmalani, M.; Sahinidis, N., Global optimization of mixed integer nonlinear programs: a theoretical and computational study, Math Program, 99, 563-591 (2004) · Zbl 1062.90041 |
| [179] | Tenenbaum, J.; de Silva, V.; Langford, J., A global geometric framework for nonlinear dimensionality reduction, Science, 290, 2319-2322 (2000) |
| [180] | Thoreau H (1849) Resistance to civil government. In: Peabody E (ed) Æsthetic papers. J. Wilson, Boston |
| [181] | van Rossum G et al (2019) Python language reference, version 3. Python Software Foundation |
| [182] | Vavasis, S., Nonlinear optimization: complexity issues (1991), Oxford: Oxford University Press, Oxford · Zbl 0785.90091 |
| [183] | Vempala S (2004) The Random projection method. No. 65 in DIMACS series in discrete mathematics and theoretical computer science. AMS, Providence |
| [184] | Venkatasubramanian, S.; Wang, Q., The Johnson-Lindenstrauss transform: an empirical study, Algorithm engineering and experiments. ALENEX, 164-173 (2011), Providence: SIAM, Providence · Zbl 1430.68388 |
| [185] | Verboon A (2014) The medieval tree of Porphyry: an organic structure of logic. In: Worm A, Salonis P (eds) The Tree. Symbol, allegory and structural device in medieval art and thought, international medieval research, vol 20. Brepols, Turnhout, pp 83-101 |
| [186] | Vershynin, R., High-dimensional probability (2018), Cambridge: CUP, Cambridge · Zbl 1430.60005 |
| [187] | Vidal, R.; Ma, Y.; Sastry, S., Generalized principal component analysis (2016), New York: Springer, New York · Zbl 1349.62006 |
| [188] | Vu, K.; Poirion, PL; Liberti, L., Random projections for linear programming, Math Oper Res, 43, 4, 1051-1071 (2018) · Zbl 1440.90024 |
| [189] | Vu, K.; Poirion, PL; D’Ambrosio, C.; Liberti, L.; Lodi, A., Random projections for quadratic programs over a Euclidean ball, Integer programming and combinatorial optimization (IPCO), LNCS, 442-452 (2019), New York: Springer, New York · Zbl 1436.90098 |
| [190] | Vu, K.; Poirion, PL; Liberti, L., Gaussian random projections for Euclidean membership problems, Discrete Appl Math, 253, 93-102 (2019) · Zbl 1415.68259 |
| [191] | Wikipedia: Civil disobedience (thoreau) (2019). http://en.wikipedia.org/wiki/Civil_Disobedience_(Thoreau). [Online; accessed 190804] |
| [192] | Wikipedia: Computational pragmatics (2019). http://en.wikipedia.org/wiki/Computational_pragmatics. [Online; accessed 190802] |
| [193] | Wikipedia: Diagonally dominant matrix (2019). http://en.wikipedia.org/wiki/Diagonally_dominant_matrix. [Online; accessed 190716] |
| [194] | Wikipedia: Flowchart (2019). http://en.wikipedia.org/wiki/Flochart. [Online; accessed 190802] |
| [195] | Wikipedia: Principal component analysis (2019). http://en.wikipedia.org/wiki/Principal_component_analysis. [Online; accessed 190726] |
| [196] | Wikipedia: Rectifier (neurl networks) (2019). http://en.wikipedia.org/wiki/Rectifier_(neural_networks). [Online; accessed 190807] |
| [197] | Wikipedia: Slutsky’s theorem (2019). http://en.wikipedia.org/wiki/Slutsky |
| [198] | Williams, H., Model building in mathematical programming (1999), Chichester: Wiley, Chichester · Zbl 1253.90166 |
| [199] | Woodruff, D., Sketching as a tool for linear algebra, Found Trends Theor Comput Sci, 10, 1-2, 1-157 (2014) |
| [200] | Wüthrich, K., Protein structure determination in solution by nuclear magnetic resonance spectroscopy, Science, 243, 45-50 (1989) |
| [201] | Xu, G.; Tsoka, S.; Papageorgiou, L., Finding community structures in complex networks using mixed integer optimisation, Eur Phys J B, 60, 231-239 (2007) · Zbl 1189.90027 |
| [202] | Yemini Y (1978) The positioning problem—a draft of an intermediate summary. In: Proceedings of the conference on distributed sensor networks. Carnegie-Mellon University, Pittsburgh, pp 137-145 |
| [203] | Yemini Y (1979) Some theoretical aspects of position-location problems. In: Proceedings of the 20th annual symposium on the foundations of computer science, pp. 1-8. IEEE, Piscataway |
| [204] | Yun C, Sra S, Jadbabaie A (2018) Global optimality conditions for deep neural networks. In: Proceedings of the 6th international conference on learning representations. ICLR, La Jolla, CA |
| [205] | Zhang L, Mahdavi M, Jin R, Yang T, Zhu S (2013) Recovering the optimal solution by dual random projection. In: Shalev-Shwartz S, Steinwart I (eds) Conference on learning theory (COLT), Proceedings of machine learning research, vol 30, pp \(135-157. \langle\) http://mlr.org \(\rangle \) |
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.
