DIMACS Workshop on Distance Geometry: Theory and Applications

July 26 - 29, 2016
DIMACS Center, CoRE Building, Rutgers University

Organizing Committee:
Farid Alizadeh (co-chair), Rutgers University, alizadeh at rci.rutgers.edu
Leo Liberti (co-chair), CNRS and Ecole Polytechnique, liberti at lix.polytechnique.fr

Amir Ali Ahmadi, Princeton University, USA
Marcia Fampa, Universidade Federal do Rio de Janeiro, Brazil
Bill Jackson, Queen Mary, University of London, UK
Nathan Krislock, Northern Illinois University, USA
Monique Laurent, CWI, The Netherlands
Therese Malliavin, Institut Pasteur, France
Michel Petitjean, University of Paris 7, France
Nicolas Rojas, Yale University, USA
Amit Singer, Princeton University, USA
Ileana Streinu, Smith College, USA
Henry Wolkowicz, University of Waterloo, Canada
Yinyu Ye, Stanford University, USA
Presented under the auspices of the DIMACS Special Focus on Information Sharing and Dynamic Data Analysis with additional support from the National Science Foundation under with additional support from NSF award DMS-1623007.


Abdo Alfakih, Univ. of Windsor, Canada

Title: On the uniqueness of the EDM Completion problem, also known as, the bar framework universal rigidity problem.

An $n \times n$ matrix $D=(d_{ij})$ is called a {\em Euclidean distance matrix (EDM) } if there exist points $p^1, \ldots, p^n$ in some Euclidean space such that $d_{ij} = ||p^i-p^j||^2$ for all $i,j=1,\ldots,n$. Given a partial matrix $A$ where some of its entries are specified or fixed and the others are unspecified or free, the {\em EDM Completion problem} is the problem of completing $A$ into an EDM by assigning values to its free entries.

In this talk, we are interested in the uniqueness of a given EDM completion of $A$. This problem is also known as the bar framework universal rigidity problem. In particular, we are interested in a sufficient condition for a given free entry of $A$ to assume the same value in all EDM completions of $A$. Obviously, such condition leads into a sufficient condition for the uniqueness of a given EDM completion of $A$.

Simon J. L. Billinge, Columbia University, Philip Duxbury and Pavol Juhas

Title: The Unassigned Distance Geometry Problem Applied to Find Atoms in Nanoclusters for Sustainable Energy

Studies of distance geometry problems (DGP) have focused on cases where the vertices at the ends of all or most of the given distances are known or assigned, which we call assigned distance geometry problems (aDGPs). The problem can get much more difficult when the vertices at the end of each edge are not known, the case we call the unassigned distance geometry problem (uDGP).

There is a pressing practical problem that is a realization of this case: finding the atomic structure of molecules and nanoparticles using X-ray or neutron diffraction data from non-crystalline materials. In this talk I will review the nanostructure inverse problem and its graph theoretical description, and describe some progress that has been made using build-up algorithms for discovering unassigned graph structures constrained by experimental results. I will also discuss limitations of the approach for real data with noise and measured with finite resolution, that makes these buildup problems inherently ill-posed.

Bob Connelly, Bob Connelly, Cornell University

Title: Global Rigidity and Universal Rigidity of Bipartite Graphs

A framework, given by a graph together with a configuration of its vertices, is globally rigid in Euclidean space if every other configuration, with the corresponding edge lengths the same, is congruent to the original. We will show that for complete bipartite graphs in d-space, if the configuration is generic and the partitions cannot be separated by quadric surface, then not only is the framework globally rigid in d-space, but it is globally rigid in all higher dimensions as well, a property called universal rigidity. Using geometric criteria it is possible to give many concrete examples of bipartite frameworks that are universally rigid.

This is joint work with S. Gortler and L. Theran.

Marcia Fampa, Federal Univ. of Rio de Janeiro, Brazil

Title: Modeling the Euclidean Steiner Tree Problem

On the Euclidean Steiner Tree Problem, the goal is to find a network of minimum length interconnecting a set P of given points in the n-dimensional Euclidean space. Such networks may be represented by a tree, where the set of nodes is given by the points in P, known as terminals, and possibly by additional points, known as Steiner points. The length of the network is defined as the sum of the Euclidean lengths of the edges in T. We will present mixed integer nonlinear programming formulations for the problem from the literature, and discuss the difficulties involved in solving them by branch-and-bound algorithms. Different techniques to overcome these difficulties are proposed and some numerical results show their impact on the solution of the problem.

This work was done in collaboration with Claudia D'Ambrosio, Jon Lee, Nelson Maculan, Wendel Melo, and Stefan Vigerske.

Hamza Fawzi, MIT

Title: Positive Semidefinite Rank

Let M be a pxq matrix with nonnegative entries. The positive semidefinite rank (psd rank) of M is the smallest integer k for which there exist positive semidefinite matrices A_i,B_j of size kxk such that M_ij=trace(A_i*B_j). The psd rank plays an important role in semidefinite optimization in the context of semidefinite representation of polytopes. In this talk I will describe this connection and will outline some of the main properties and open questions concerning the psd rank.

Based on joint work with Joao Gouveia, Pablo Parrilo, Richard Robinson, James Saunderson, Rekha Thomas.

Douglas Gonçalves, Federal Univ. of Santa Catalina, Brazil

Title: A Least-squares Approach for the Discretizable Distance Geometry Problem with Inexact Distances

The discretizable distance geometry problem in dimension K is a particular case of the distance geometry problem in which there exists a vertex order ensuring that the initial K vertices form a clique and for the remaining vertices, there are at least K reference distances to predecessors. We extend a branch-and-prune approach for this problem by considering noisy distances instead of exact ones. Candidate positions are obtained by the solution of a least-squares problem related to a reduced distance matrix, and possibly by a reflection around the affine subspace generated by the references. The feasibility of such candidates is verified based on a perturbation result for the singular value decomposition and the discrepancy principle.

Steven Gortler, Harvard University

Title: Affine Rigidity and Conics at Infinity

We prove that if a framework of a graph is neighborhood affine rigid in $d$-dimensions (or has the stronger property of having an equilibrium stress matrix of rank $n-d-1$) then its edge directions lie on a conic at infinity if and only if the framework is ruled on a single quadric.

This strengthens and also simplifies a related result by Alfakih. It also allows us to prove that the property of super stability is invariant with respect to projective transforms and also to the coning and slicing operations.

Finally this allows us to unify some previous results on the Strong Arnold Property of matrices.

(joint with Connelly and Theran)

Georgina Hall, Princeton University

Title: Polynomial DC Decompositions and Applications

Difference of Convex (DC) programing is a class of optimization problems where the objective and constraints are given as the difference of two convex functions. Although several important problems (e.g., in machine learning) already appear in DC form, such a decomposition is not always available. We consider this decomposition question for polynomial optimization and present algorithms based on linear, second order cone, or semidefinite programming that can find so-called undominated DC decompositions. We also present applications to distance geometry problems.

Bill Jackson, Queen Mary University of London, UK

Title: Rigidity and Global Rigidity of Frameworks

The study of the rigidity of frameworks has its origins in the work of Euler, Cauchy and Maxwell. There was a flurry of activity in the 1970's prompted by Laman's characterisation of rigid generic bar-joint frameworks in the plane and Connelly's counterexample to Euler's original conjecture on rigid polyhedra in 3-space. This activity has increased since then and it is now an exciting and thriving research area. I will give an introduction to rigidity theory, concentrating on results and problems for bar-joint frameworks but also describing how these have been extended to other types of frameworks and the matrix completion problem.

Tibor Jordan, Eötvös Lorànd University, Hungary

Title: Generic Global Rigidity of Graphs

A d-dimensional bar-and-joint framework is said to be globally rigid if every d-dimensional framework with the same underlying graph and with the same edge lengths is congruent to it. It is known that, for every fixed d, if the set of the joint coordinates is generic then global rigidity depends only on the underlying graph.

A major combinatorial question, which is still open in three-space and in higher dimensions, is whether there is a good characterization of the generically globally rigid graphs. In this talk we shall give a survey of the known results and open questions concerning (a number of versions of) this question.

Bahman Kalantari, Rutgers University

Title: The Triangle Algorithm: An Algorithmic Separation Theorem and its Applications

First, we introduce the Triangle Algorithm, a fully polynomial time approximation scheme (FPTAS) for the convex hull membership problem (CHMP). CHMP is testing if the convex hull of a finite set of points in the Euclidean space contains a distinguished point, a fundamental problem in LP, statistics, machine learning and computational geometry. The validity of the algorithm relies on a geometric duality, called distance duality. Next, we describe a generalization of the Triangle Algorithm, the distance duality and corresponding computational complexities for testing if two arbitrary compact convex subsets K and K' intersect. It computes p in K and p' in K', where either the Euclidean distance d(p, p') is arbitrarily small, or the orthogonal bisecting hyperplane to the line segment pp' separates K from K'. If desired, it computes the optimal supporting hyperplanes. It thus applies to the support vector machine (SVM) problem. Having tested the Triangle Algorithm on reasonably large size instances of CHMP, LP, and SVM, it is competitive with the Frank-Wolfe method, the simplex method, and the sequential minimal optimization algorithm (SMO). In fact in an unorthodox application of the Triangle Algorithm in solving a linear system, it outperforms such iterative methods as SOR and AOR. It also finds applications in solving relaxations of NP-hard problems. In summary, the Triangle Algorithm is a robust algorithm that finds applications in diverse problems in optimization, CS and numerical analysis.

Yuehaw Khoo, Princeton University

Title: Integrating NOE and RDC using Semidefinite Programming for Protein Structure Determination

Nuclear magnetic resonance (NMR) spectroscopy is the most-used technique for protein structure determination besides X-ray crystallography. Typically the 3D structure of a protein is obtained through finding the coordinates of atoms subject to pairwise distance constraints. However, for large proteins there are usually insufficient distance measurements and the structure determination problem becomes ill-posed. Residual dipolar coupling (RDC) measurements provide additional geometric information on the angles between bond directions and the principal-axis-frame. The optimization problem involving RDC is non-convex and we present a novel convex programming relaxation to it. In simulations we attain the Cramer-Rao lower bound with relatively efficient running time. From real data, we obtain the protein backbone structure for ubiquitin with 1 Angstrom resolution.

This is joint work with Amit Singer and David Cowburn.

Nathan Krislock, Northern Illinois University

Title: Facial Reduction for Euclidean Distance Matrix Problems

A powerful approach to solving problems involving Euclidean distance matrices (EDMs) is to represent the EDM using a semidefinite matrix. Due to the nature of these problems, the resulting semidefinite programming problem is typically not strictly feasible. In this talk we discuss how to take advantage of this lack of strict feasibility by using facial reduction to obtain smaller equivalent problems. This approach has proven very successful for solving large-scale Euclidean distance matrix problems having little to no noise in the given incomplete distance measurements. We will present recent results on the use of facial reduction for solving noisy Euclidean distance matrix problems.

Carlile Lavor, University of Campinas, Brazil

Title: Distance Geometry and Clifford Algebra

Distance Geometry (DG) is the study of geometry based on the concept of distance and Clifford Algebra (CA) is a generalization of the hypercomplex number systems based on the concept of multivector. This talk will explain how DG and CA can be combined to model problems related to 3D protein structure determination using Nuclear Magnetic Resonance data.

Jon Lee, University of Michigan

Title: Relaxing Kindly and Efficiently

Very generously interpreting the conference theme, I will talk about two issues that arise in the sBB (spatial branch-and-bound) global-optimization algorithm. One has to do with smoothing functions having limited non-differentiability (for example, p-th roots which arise in computing distances via p-norms) in a suitable way for sBB. The second has to do with a way of measuring quality of convex relaxations via volumes and getting from the mathematical analysis, some actionable algorithmic ideas for sBB.

Thérése Malliavin, Institut Pasteur, France

Title: The interval branch-and-prune algorithm for the resolution of the molecular Distance Geometry problem: toward an application to real-life protein structure determination by NMR

M. Machat (1), B Bardiaux (1), A Cassioli (1), C Lavor (2), L Liberti (3), TE Malliavin (1)
(1) Structural Bioinformatics Unit, CNRS UMR 3528 and Institut Pasteur, Paris, France
(2) IMECC - UNICAMP, Campinas, Brazil
(3) LIX, Ecole Polytechnique, Palaiseau, France

The interval branch-and-prune (iBP) approach has been proposed ([1-6]) as a method for allowing a global optimisation of molecular structure with distance restraints. A recursive implementation of this algorithm [9] has permitted to apply this approach on small structures of proteins in alpha-bundles. Here, we are going to present the results obtained on a set of protein structures with sizes from 24 to 120 residues, displaying various secondary structures and topologies. The results obtained with various sets of distance restraints, including exact values and interval of values, will be presented, in order to experimentally evaluate the complexity of the algorithm on real-case of protein structure determination. This experimental evaluation will be related to the theoretical estimation previously obtained [8]. The effect of several procedures of acceleration will be used in order to allow a complete exploration of the tree describing the molecular Distance Geometry problem. The consequences of the availability of such an approach for the field of structural biology will be discussed [7].


[1] Lavor C., Liberti L., Mucherino A., On the solution of molecular distance geometry problems with interval data,in Proceedings of the International Workshop on Computational Proteomics (Int. Conf. on Bioinformatics and Biomedicine), IEEE, Hong-Kong, 77-82, 2010.

[2] Liberti L., Lavor C., Maculan N., A branch-and-prune algorithm for the molecular distance geometry problem, International Transactions in Operational Research, 15:1-17, 2008.

[3] Lavor C., Liberti L., Maculan N., Mucherino A., The discretizable molecular distance geometry problem, Computational Optimization and Applications (2012) 52:115-146.

[4] Lavor C., Liberti L., Mucherino A., The interval Branch-and-Prune algorithm for the Discretizable Molecular Distance Geometry Problem with inexact distances, Journal of Global Optimization, 56:855-871, 2013.

[5] Lavor C., Alves R., Figueiredo W., Petraglia A., Maculan N., Clifford Algebra and the Discretizable Molecular Distance Geometry Problem, Advances in Appllied Clifford Algebras 25 (2015), 925-942.

[6] Mucherino A., Lavor C., Malliavin T., Liberti L., Nilges M., Maculan N., Influence of Pruning Devices on the Solution of Molecular Distance Geometry Problems, in Pardalos, P. and Rebennack, S. (eds.), Experimental Algorithms (ISCO), LNCS 6630:206-217, 2011.

[7] Malliavin T.E., Mucherino A., Nilges M., Distance geometry in structural biology: new perspectives, in: Distance Geometry: Theory, Methods and Applications, A. Mucherino, C. Lavor, L. Liberti, N. Maculan (Eds.), Springer, 2013.

[8] Liberti L., Lavor C., Mucherino A., The Discretizable Molecular Distance Geometry Problem Seems Easier on Proteins, in: Distance Geometry: Theory, Methods and Applications, A. Mucherino, C. Lavor, L. Liberti, N. Maculan (Eds.), Springer, 2013.

[9] Cassioli A, Bardiaux B, Bouvier G, Mucherino A, Alves R, Liberti L, Nilges M, Lavor C and Malliavin T., An algorithm to enumerate all possible protein conformations verifying a set of distance constraints, BMC Bioinformatics, 28:16-23 (2015).

Antony Man-Cho So, Chinese Univ. of Hong Kong

Title: Robust Convex Approximation Methods for TDOA-Based Localization under NLOS Conditions

In this talk, we present a novel robust optimization approach to source localization using time-difference-of-arrival (TDOA) measurements that are collected under non-line-of-sight (NLOS) conditions. A key feature of our approach is that it does not require knowledge of the distribution or statistics of the NLOS errors, which are often difficult to obtain in practice. Instead, it only assumes that the NLOS errors have bounded supports.

Based on this assumption, we formulate the TDOA-based source localization problem as a robust least squares (RLS) problem, in which a location estimate that is robust against the NLOS errors is sought. Since the RLS problem is non-convex, we propose two efficiently implementable convex relaxation-based approximation methods to tackle it. We then analyze the approximation quality of these two methods and establish conditions under which they will yield a unique localization of the source.

Onur Ozyesil, Princeton University

Title: Robust Camera Location Estimation by Convex Programming

$3$D structure recovery from a collection of $2$D images requires the estimation of the camera locations and orientations, i.e. the camera motion. For large, irregular collections of images, existing methods for the location estimation part, which can be formulated as the inverse problem of estimating $n$ locations $\mathbf\{t\}_1, \mathbf\{t\}_2, \ldots, \mathbf\{t\}_n$ in $\mathbb\{R\}^3$ from noisy measurements of a subset of the pairwise directions $\frac{\mathbf\{t\}_i - \mathbf\{t\}_j}{\|\mathbf\{t\}_i - \mathbf\{t\}_j\|}$, are sensitive to outliers in direction measurements. In our work, we firstly provide a complete characterization of well-posed instances of the location estimation problem, by presenting its relation to the existing theory of parallel rigidity. For robust estimation of camera locations, we introduce a two-step approach, comprised of a pairwise direction estimation method robust to outliers in point correspondences between image pairs, and a convex program to maintain robustness to outlier directions. In the presence of partially corrupted measurements, we empirically demonstrate that our convex formulation can even recover the locations exactly. Lastly, we demonstrate the utility of our formulations through experiments on Internet photo collections.

(This is a joint work with Amit Singer)

Pablo Parrilo, MIT

Title: Graph Structure in Polynomial Systems: Chordal Networks

The sparsity structure of a system of polynomial equations or an optimization problem can be naturally described by a graph summarizing the interactions among the decision variables. It is natural to wonder whether the structure of this graph might help in computational algebraic geometry tasks (e.g., in solving the system). In this lecture we will provide a gentle introduction to this area, focused on the key notions of chordality and treewidth, which are of great importance in related areas such as numerical linear algebra, database theory, constraint satisfaction, and graphical models. In particular, we will discuss “chordal networks”, a novel representation of structured polynomial systems that provides a computationally convenient decomposition of a polynomial ideal into simpler (triangular) polynomial sets, while maintaining its underlying graphical structure. As we will illustrate through examples from different application domains, algorithms based on chordal networks can significantly outperform existing techniques. (Joint work with Diego Cifuentes.)

Frank Permenter, MIT

Title: Dimension Reduction For SDPs Via Jordan Algebras

We propose a new method for simplifying semidefinite programs inspired by symmetry reduction. Specifically, we show if a projection satisfies certain invariance conditions, restricting to its range yields an equivalent primal-dual pair over a lower-dimensional symmetric cone---namely, the cone-of-squares of a Jordan subalgebra of symmetric matrices. We then give a simple algorithm for minimizing the rank of this projection and hence the dimension of this cone. Finally, we explore connections with *-algebra-based reduction methods, which, along with symmetry reduction, can be seen as special cases of our method.

Iraj Saniee, Bell Labs, Nokia

Title: Informational Networks

I will summarize our investigations showing that "informational networks" typically have very small hyperbolic constants. Classifying the vertices of such networks into a (small) number of clusters is a topic of much interest in the data mining community but highquality clustering algorithms have at the very best cubic complexity and these networks often have millions to billions of nodes. This motivates the rest of the talk, which is as follows. We provide a quasi-linear time algorithm for the p-center clustering algorithm with an additive error not exceeding 3 times a network's hyperbolic constant. Specifically, for the graph G = (V,E) with n vertices, m edges and hyperbolic constant δ, we construct an algorithm for the p-center computation in time O(p+1)(δ +1)(n+m) log(n)) with radius r(p) + δ when p = 3, where r(p) is the optimal radius of the p-center. Prior work had identified p centers with accuracy r(p) + δ but with time complexity O((n3 log n + n2m) log(diam(G))) which is infeasible for large graphs, that is, graphs with 10K or more nodes.

Joint work with Katherine Edwards and Sean Kennedy.

Amit Singer, Princeton University

Title: Non-unique Games Over Compact Groups and Orientation Estimation in Cryo-EM

Let G be a compact group and let f_ij be real valued bandlimited functions over G for i,j=1,...,n. We define the Non-Unique Games (NUG) problem as finding g_1,..., g_n in G that minimize \sum_{i,j=1}^n f_ij(g_i g_j^{-1}) . We devise a relaxation of the NUG problem to a semidefinite program (SDP) by taking the Fourier transform of f_ij over G. The NUG framework can be seen as a generalization of the little Grothendieck problem over the orthogonal group and the Unique Games problem and includes many practically relevant problems, such as orientation estimation in cryo-electron microscopy.

Joint work with Yutong Chen and Afonso Bandeira.

Meera Sitharam, University of Florida at Gainesville

Title: Efficient Realization of Linkages via Optimal Recursive Decomposition, Rigidity, and Cayley Convexification

Finding all realizations of distance constraint systems (linkages) is essential for many applications and is a computationally difficult problem already in 2 and 3 dimensions.

(1) As an essential step towards tractability, in the case where the underlying graph is generically independent in the rigidity matroid, we formalize the notion of a canonical recursive decomposition of an input graph into its (proper) maximal rigid subgraphs, and give a polynomial time algorithm for finding it. The recursive decomposition is a tree with the leaves being edges and the internal nodes being rigid subgraphs (or linkages). The decomposition is optimal in that it minimizes the maximum fanin, which accurately captures the algebraic complexity of the realization problem. The formalization of canonical decomposition, and its optimality extend to general abstract rigidity matroids, and the polynomial time algorithm extends to sparsity matroids.

(2) The realization of a parent linkage in the decomposition tree is achieved by recombining the realizations of its child linkages, thus the problem now reduces to realizing indecomposable linkages. We suggest a new method of optimal modification by dropping edges so that the resulting flexible linkage has a convex, so-called Cayley or nonedge parameterized realization space and moreover, adding in the Cayley nonedges as edges gives a decomposable graph. The convexity and decomposability vastly simplify the search for the required distances of the dropped edges and thus the realizations of the original graph. While the question of dropping the minimum number of edges (and thus minimizing the dimension of the search space) appears to be NP-hard, we formalize a different optimality condition that ensures an efficient and stable search for realizations.

(3) If time permits, a very brief glimpse of highly related new results by the speaker and coauthors will be provided. (Related to 1) a newly formulated abstract rigidity matroid called GEM (graded exchange matroid) that will combinatorially capture the 3D rigidity matroid, IF a well-known maximality conjecture is true. (Related to 1) a new type of rigidity related to incidence geometry that give bounds and algorithms for dictionary learning (Related to 2): the close connection between the concept of convex Cayley realization spaces and graph flattenability (introduced for the Euclidean norm by Barvinok and studied by Belk/Connelly) in any norm. And finally (Related to 2): videos demoing opensource software of Cayley realization spaces for molecular assembly and CAD applications.

Ileana Streinu, Smith College

Title: Periodic Rigidity: a Survey

A periodic bar-and-joint framework is an abstraction of atom-and-bond crystal structures. Following a general introduction to the deformation theory of this type of frameworks (introduced in 2010 by Ciprian Borcea and the speaker), I will survey results on Maxwell-type characterizations, the connection to rigidity theory for finite frameworks as well as applications to expansive and auxetic periodic structures.

Jayme L Szwarcfiter, Universidade Federal do Rio de Janeiro

Title: On Graph Convexities Related to Paths and Distances

A graph convexity is a pair (G, C), where G is a finite graph with vertex V (G) and C a family of subsets of V (G) satisfying ∅, V (G) 2 C and being closed under intersections. The sets C ∈ C are called convex sets. The most common graph convexities are those whose convex sets are defined through special paths of the graph. Among them the most prominent are the geodesic convexity, where C is closed under taking shortest paths, the monophonic convexity, where C is closed under induced paths and the P3 convexity, whose convex sets are closed under pairs of common neighbors. We examine some common parameters of graph convexities, as the geodetic number, convexity number, hull number, Helly number, Carathèodory number, Radon number and rank. In particular, we describe complexity results related to the com- putation of these parameters.

Shin-Ichi Tanigawa, Kyoto University

Title: Singularity Degree of the Positive Semidefinite Matrix Completion Problem

The singularity degree of a semidefinite programming problem is the smallest number of facial reduction steps to make the problem strongly feasible. We introduce two new graph parameters, called the singularity degree and the nondegenerate singularity degree, based on the singularity degree of the positive semidefinite matrix completion problem. We give a characterization of the class of graphs whose parameter value is equal to one for each parameter. Specifically, we show that the singularity degree of a graph is equal to one if and only if the graph is chordal, and the nondegenerate singularity degree of a graph is equal to one if and only if the graph is the clique sum of chordal graphs and K4-minor free graphs. We also show that the singularity degree is bounded by two if the treewidth is bounded by two, and exhibit a family of graphs with treewidth three, whose singularity degree grows linearly in the number of vertices.

Antonios Varvitsiotis, NTU Singapore

Title: Graph Cores via Universal Completability

A framework for a graph G=(V,E), denoted G(p), consists of an assignment of real vectors p = (p_1, p_2,..., p_{|V|}) to its vertices. A framework G(p) is called universally completable if for any other framework G(q) that satisfies p_i^T p_j=q_i^T q_j for all i=j and (i,j) in E there exists an isometry U such that Uq_i=p_i for all i in V. A graph is called a core if all its endomorphisms are automorphisms. In this work we identify a new sufficient condition for showing that a graph is a core in terms of the universal completability of an appropriate framework for the graph. To use this condition we develop a method for constructing universally completable frameworks based on the eigenvectors for the smallest eigenspace of the graph. This allows us to recover the known result that the Kneser graph K_{n:r} and the q-Kneser graph qK_{n:r} are cores for n\ge 2r+1. Our proof is simple and does not rely on the use of an Erdös-Ko-Rado type result as do existing proofs. Furthermore, we also show that a new family of graphs from the binary Hamming scheme are cores, that was not known before.

Joint work with Chris Godsil, David Roberson, Brendan Rooney and Robert Sàmal.

Martin Vetterli, EPFL

Title: Euclid's SLAM Dunk

Positioning has been around since the dawn of civilization, from recovering landownership after floods in ancient Egypt or the longitude competition for seafaring in 18th century England, to the ubiquity of GPS today. Positioning dovetails with mapping, again a venture pursued for millennia. Doing the two at the same time is much more recent, and famously epitomized in the SLAM (*) problem. Initially conceived as a modality-generic computational method, §modern SLAM use cases are in computer vision and time of flight (ToF) positioning with light, radio, or sound. With ToFs we get distances from which we can reason about the trajectory and the environment. Thus a fundamental object related to localization and mapping with ToF measurements is the Euclidean distance matrix (EDM). In our work, we consider variations on the theme of EDMs in localization and mapping. The twist is that our ToFs come from echoes which puts forward various challenges. For example, ToFs are not labeledwe do not a priori know which reflector generates which echo.

There are many ways to formulate and address SLAM from echoes. We focus on what we believe is the most general and most challenging setting: a single omni-directional source and a single omni-directional receiver. This, too, can come in many tastes and colors. In this talk I will present results for the case when the source is static and the receiver moves, and for the case when colocated source and receiver move together. The latter abstracts into a new problem similar to metric multidimensional unfolding. The difference is that instead of distances between two point sets, we get distances between a point set and a set of halfspaces. This leads to a new class of invariances and new algorithms.

(*) SLAM stands for simultaneous localization and mapping

Work done in collaboration with Ivan Dokmanic (Langevin/ENS/UIUC) and Miranda Krekovic (EPFL).

Henry Wolkowicz, Univ. of Waterloo, Canada

Title: Facial Reduction in Cone Optimization with Applications to Matrix Completions

Slater's condition -- existence of a ``strictly feasible solution'' -- is at the heart of convex optimization. It is enough to look at the basics: without strict feasibility, first-order optimality conditions may be meaningless, the dual problem may yield little information about the primal, and small changes in the data may render the problem infeasible. In consequence, many off-the-shelf numerical methods can perform poorly; primal-dual interior point methods, in particular. New optimization modelling techniques and convex relaxations for hard nonconvex problems have shown that the loss of strict feasibility is a much more pronounced phenomenon than has previously been realized. Such new developments suggest a reappraisal. In this talk we describe the various reasons for the loss of strict feasibility, whether due to poor modelling choices or (more interestingly) rich underlying structure, and describe ways to cope with it.

In particular, we look at three different views: (i) from the ground set of the application; (ii) from the lifted space of semidefinite matrices in the relaxation; (iii) from the image space of the relaxation.

We consider applications to Euclidean matrix completions for sensor network localization and molecular conformation problems.

(Work with Dmitriy Drusvyatskiy, University of Washington, Seattle WA.)

Previous: Program
Workshop Index
DIMACS Homepage
Contacting the Center
Document last modified on July 22, 2016.