Workshop Details

An n-by-n matrix D is a Euclidean distance matrix (EDM) if its entries can be realized as the interpoint squared Euclidean distances of an n-point configuration. If the points of the configuration lie on a sphere of radius ρ, then the corresponding EDM is said to be spherical of radius ρ.

In the first part of this talk, I will survey the basic theory of EDMs, where the main emphasis will be on various properties and characterizations of EDMs and spherical EDMs. In the second part, I will discuss recently obtained results on a couple of distance geometry problems posed in terms of EDMs. The following is an example of such problems. Given a spherical EDM D of unit radius and 1≤ k < l ≤ n, characterize the set of all spherical EDMs of unit radius whose entries agree with those of D except possibly with the entry in the klth and lkth positions.

The Euclidean distance geometry (EDG) problem naturally arises in a wide variety of applications ranging from determining molecular conformations in computational chemistry to localization in sensor networks. We formulate the EDG problem as a matrix completion problem of recovering a low rank r Gram matrix with respect to certain predefined basis. The well known restricted isometry property can not apply to this formulation. Instead, we introduce a dual basis approach to theoretically analyze the proposed program. If the Gram matrix satisfies certain coherence condition, our main result shows that the underlying configuration of n points can be recovered with high probability from O(nr log2 n) uniformly random samples of the distance matrix. Computationally, simple and fast algorithms are designed to solve the Euclidean distance geometry problem. Numerical tests on different three dimensional data and protein molecules validate effectiveness and efficiency of the proposed algorithms.

We consider some Euclidean distance matrix (EDM) completion problems, inspired by molecular determination problems. Some distances in the matrix are precisely known, some distances are given in terms of intervals and some distances are completely unknown. We propose a method for estimation of the values of the unknown distances in the matrix, based on results about minimal rank EDM completions.

Many problems in data science are addressed by mapping entities of various kind to vectors in a Euclidean space of some dimension. Most of these methods (e.g. Multidimensional Scaling, Principal Component Analysis, K-means clustering, random projections) are based on the proximity of pairs of vectors. In order for the results of these methods to make sense, the proximity of entities in the original problem must be well approximated in the Euclidean space setting. If proximity were known for each pair of original entities, this mapping would be a good example of isometric embedding. Usually, however, this is not the case, as data are partial, noisy and wrong. I shall survey some of the methods above from the point of view of Distance Geometry.

We consider the matrix completion problem for special classes of matrices. This includes EDM, low rank, robust PCA, and Toeplitz. We consider both the exact and noisy cases. We include theoretical results as well as efficient numerical techniques. Our tools are semidefinite programming, facial reduction, and trust region subproblems.

We study time-varying semidefinite programs (TV-SDPs), which are semidefinite programs whose data (and solutions) are functions of time. Our focus is on the setting where the data varies polynomially with time. We show that under a strict
feasibility assumption, restricting the solutions to also be polynomial functions of time does not change the optimal value of the TV-SDP. Moreover, by using a Positivstellensatz on univariate polynomial matrices, we show that the best polynomial solution of a given degree to a TV-SDP can be found by solving a semidefinite program of tractable size. We also provide a sequence of dual problems which can be cast as SDPs and that give upper bounds on the optimal value of a TV-SDP (in maximization form). We prove that under a boundedness assumption, this sequence of upper bounds converges to the optimal value of the TV-SDP. Under the same assumption, we also show that the optimal value of the TV-SDP is attained. We demonstrate the efficacy of our algorithms on a maximum-flow problem with time-varying edge capacities, a wireless coverage problem with time-varying coverage requirements, and on bi-objective semidefinite  optimization where the goal is to approximate the Pareto curve in one shot.

Joint work with Bachir El Khadir (Princeton).

The matching problem between two adjacency matrices, A and B, can be formulated as the NP-hard quadratic assignment problem (QAP). While the QAP admits a semide nite (SDP) relaxation that is often tight in practice, this SDP scales badly as it involves a matrix variable of size n2 by n2. To achieve a speed up, a further relaxation of the SDP will be described, where the number of variables scale as O(bn2), where b is the number of non-zero entries in B. The dual problem of this relaxation has a natural three-block structure that can be solved via Alternating Direction Method of Multipliers (ADMM) in a distributed manner. I will show results that suggest this relaxation o ers a good compromise between speed and tightness in practice, and will discuss how the assignment problem in Nuclear Magnetic Resonance Spectroscopy can be formulated as a QAP with sparse B.

This is joint work with Jose Simoes Bravo Ferreira and Amit Singer.

This talk will be a tutorial introduction to the unassigned variant (called uDG) of the DG problem, and how it arises in the problem of finding the atomic structure of materials. Two classes of optimization algorithm will be described, with both based on build-up methods but using dfferent strategies. Classes of problem for which the buildup methods are exact will be outlined and bounds on their computational time will be derived and tested using computational experiments. As in the DG problem, graph rigidity provides useful insights into the minimal number of distances that are required for there to be a unique solution to the uDG problem. A list of unsolved problems in the area will be discussed. Selected papers are listed below.

*This work was done in collaboration with co-authors of the papers listed below.

[1] P. Juhas, D. Cherba, P.M. Duxbury, W. Punch, S.J.L. Billinge, Ab-initio determination of solid state nanostructure, Nature 440, 655 (2006)

[2] P. Juhas, L. Granlund, P.M. Duxbury, W.F. Punch and S.J.L. Billinge, The LIGA algorithm for ab initio determination of nanostructure, Acta Crystallographica A64, 631- 640 (2008).

[3] S.R. Gujarathi, C.L. Farrow, C. Glosser, L. Granlund and P.M. Duxbury. Abinitio reconstruction of complex Euclidean networks in two dimensions. Phys. Rev. E89, number 53311, (2014).

[4] P.M. Duxbury, L. Granlund, S.R. Gujarathi, P. Juhas, S.J.L. Billinge. The unassigned distance geometry problem. Discrete Applied Mathematics 204, 117-132 (2016).

[5] S.J.L. Billinge, P.M. Duxbury, D.S. Goncalves, C. Lavor, A. Mucherino. Assigned and unassigned distance geometry: Applications to biological molecules and nanostructures. 4OR Quarterly Journal of Operations Research 14 (4), 337-376 (2016).

[6] S.J.L. Billinge, P.M. Duxbury, D.S. Goncalves, C. Lavor, A. Mucherino. Recent results on assigned and unassigned distance geometry: Applications to biological molecules and nanostructures. Annals of Operations Research 271 (1), 161-203 (2018)

Conformational sampling for biological macromolecules, e.g., proteins, DNA, RNA, etc., usually relies on molecular dynamics simulations (MDS), either in explicit solvent or with continuum electrostatic models to mimic the physiological environment of the biomolecules. MDS are intrinsically an N-particle move conformational sampling algorithm, in which the movement of each atom is guided by the force experienced. To avoid steric collision, the movement for each step has to be small so that MDS can be conducted smoothly. MDS usually will be terminated if the system evolves into bad configurations. Another popular sampling approach is the Monte Carlo method, and the Metropolis algorithm is commonly applied if the canonical ensemble distribution is desired. Monte Carlo methods have the advantages of being more robust, and can be conducted with bad initial configuration. However, there is no efficient N-particle move algorithm for the Monte Carlo sampling of biomolecular conformations, if the force calculations are to be avoided. We recently proposed a new method to construct the protein conformations by solving the discretizable distance geometry problem with interval data, and we now apply this method to generate the conformations for the Monte Carlo move of the protein conformations. We will demonstrate the efficiency of sampling of our method with various sampling strategies for folded protein structures, and also test whether our method could be suitable protein folding simulations.

Joint work with Antonio Mucherino, IRISA, University of Rennes 1, France.

The Branch-and-Prune algorithm (BP) and its variations are among the most cited methods to solve molecular discretizable distance geometry problems (DMDGP). The BP-like algorithms represent the DMDGP by a graph whose nodes are ordered in such a way that a solution can be constructed iteratively. Previous results indicated that finding a BP-order was a NP-hard problem, but in this presentation we show that it can be done in polynomial time. An interesting property of DMDGP is that all solutions can be generated from any other applying partial reflections. We also introduce a new application of this result using it to reduce the number of float point operations required by BP to calculate a solution to DMDGP. Finally, we define a NP-hard problem whose solution identifies the minimal number operations needed to solve the DMDGP with BP algorithm.

Discretizable distance geometry problems (DDGPs) constitute a class of graph realization problems where the vertices can be ordered in such a way that the search space of possible positions becomes discrete, usually represented by a binary tree. In dimension K, a discretization order is such that each one of the vertices with rank greater than K + 1 has at least K adjacent predecessors, called references. Finding such vertex orders is an essential step to identify and solve DDGPs. Here we look for discretization orders that minimize one of two distinct indicators of the size of the search tree. With both indicators, the key is to have a small number of vertices with exactly K references. In the first part of the presentation, we will consider a generalization of this discretization problem and show that it is strongly NP-Hard with both indicators, even if K is fixed to any value larger than or equal to one. In the second part, I will talk about two different solution methods for this problem. One is a cutting plane algorithm based on an extended integer programming formulation. The other is a branch-and-bound algorithm making use of a previously developed greedy algorithm that is guaranteed to return a discretization order when one exists. Finally, I will discuss a numerical comparison of the different approaches on a benchmark based on distance geometry instances.

New mixed integer nonlinear optimization models for the Euclidean Steiner tree problem in d-space (with d ≥ 3) will be presented in this talk. Each model features a non smooth objective function but a convex set of feasible solutions. All these models are theoretically equivalent. From these models, six mixed integer linear and nonlinear relaxations will be considered. Each relaxation has the same set of feasible solutions as the model from which it is derived. Finally, preliminary computational results highlighting the main features of the presented relaxations will be discussed.

This work is joint with Hacene Ouzia.

Autocorrelation analysis offers an alternative computational framework for 3-D structure determination of biological macromolecules using single particle cryo-EM. Similar to distance geometry, autocorrelation analysis also requires solving a system of low degree polynomial equations and the question of uniqueness plays a significant role.

Previous approaches to solve the unassigned distance geometry problem (uDGP) were often based on backtracking and build-up algorithms. Being a combinatorial optimization problem in nature, the uDGP can be quadratically formulated as 0-1 integer programming with the points locations represented by a 0-1 vector x. The unassigned distance distribution can then be computed from the autocorrelation of x. We further relax the 0-1 integer programming into a constrained nonconvex optimization problem, and propose to solve it using projected gradient descent with spectral initialization. The unknown view tomography problem arising from applications such as cryo-electron microscopy can be connected to uDGP under the 3D point-source model and Gaussian-source model. It can also be formulated as a constrained nonconvex problem and solved using the proposed approach.

We propose new mathematical programming formulations and a new heuristic to solve the unassigned distance geometry problem. Preliminary computational results are also presented.

I will present a tutorial on rigidity theory for bar-and-joint frameworks with a focus on flexible structures, both finite and periodic. I will cover generic properties captured by combinatorial descriptors, infinitesimal and continuous deformations, and how to design flexible structures with special kinds of trajectories, such as those that avoid singularities, expand all distances or, in crystals, just the unit cells. Along the way, applications in robotics, structural molecular biology and materials science will be described.

A (bar-joint) framework (G;p) in Rd is the combination of a graph G and a map p assigning positions to the vertices of G. A framework is rigid if the only edgelength-preserving continuous motions of the vertices arise from isometries of Rd. The framework is globally rigid if every other framework with the same edge lengths arises from isometries of Rd. Both rigidity and global rigidity, generically, are well understood when d = 2.

A linearly constrained framework in Rd is a generalisation of a framework in which some vertices are constrained to lie on one or more given hyperplanes. Streinu and Theran characterised rigid linearly constrained generic frameworks in R2 in 2010. In this talk I will describe an analogous result for the global rigidity of linearly constrained generic frameworks in R2.

This is joint work with Hakan Guler and Bill Jackson.

Humans use a wealth of heterogeneous signals to navigate through space. We leverage the rich visual signals from our retina, and combine it with acoustic and inertial measurements from the auditory system, tactile signals, and others, to sense our surroundings. We learn to travel efficiently through an environment, to reorient ourselves when we get lost, and to create cognitive maps for future use. The diversity of signals improves the accuracy of our navigation, and it provides us with a resilience to failure of the underlying systems.

Inspired by this, we develop solutions which aim at providing accurate localization by aggregating signals from different modalities. In this talk, I will provide both theoretical and practical insights which can pave the way for such multimodal systems. I will present Coordinate Difference Matrices (CDMs), which we developed to solve various problems arising in localization and mapping, for example localization from ranges and angles. Then, I will present our ongoing research on the reconstruction of parametric trajectories, which eliminates the necessity for dense and synchronized distance measurements. Finally, I will share results from our real-world indoor localization system combining Bluetooth, WiFi, inertial measurement units and visual measurements.

Part of my presentation contains research done by my colleagues from the laboratory of audiovisual communications (LCAV) or in collaboration. The last project is a collaboration with the school of engineering and architecture of Fribourg (HEIA-FR) and Vidinoti.

Graph coloring constitutes a class of combinatorial optimization problems of great theoretical and practical relevance with many applications, for which variations have been proposed in the literature, using different characteristics applied to vertices and edges. One of its most important applications is the channel assignment in mobile wireless networks, where channels must be attributed to devices while avoiding interferences, for which the Bandwidth Coloring Problem (BCP) has been proposed, where colors assigned to vertices must be separated according to weights imposed on edges. However, such a model does not take into account all scenarios of the channel assignment so other theoretical approaches can be used to identify new models. In this talk, we present new coloring problems based on distance geometry, generalizing the classic Vertex Coloring Problem (VCP) and BCP with adjacency constraints involving equalities and inequalities, which can be applied to different characteristics of the channel assignment, such as bidirectional communication. For the new models, we present feasibility and computational complexity properties. We propose constraint programming formulations based on such problem definitions, using global constraints for treating multi-coloring demands. Also, we explored integer programming models for BCP, improving an existing one and proposing two new others, based on orientations of the input graph and distances between colors. Both new models have polynomial size, in contrast to existing ones that are pseudopolynomial. For the new corresponding polytopes, we present their properties and valid inequalities which define facets under certain conditions. We also developed a cut-and-branch algorithm based on the orientation polytope and its valid inequalities. Our experiments show that this strategy has good potential for BCP, obtaining optimal solutions in less runtime when compared to the standard formulation for many literature instances.

Phase unwrapping is the process of recovering a continuous phase signal from an original signal wrapped in the [-π, π] interval. It is a critical step of coherent signal processing, with applications such as synthetic aperture radar, acoustic imaging, magnetic resonance, X-ray crystallography, and seismic processing, and thus the subject of extensive research. We reformulate the phase unwrapping problem under L0-norm as the search for a minimum-cost balanced spanning forest in a graph where the vertices represent the residues of the wrapped phase, and introduce branch-and-cut, column generation and metaheuristic approaches. These approaches lead us one step closer towards good solutions for this problem, which were previously viewed, in the signal processing literature, as highly desirable but nonetheless intractable.