A semidefinite programming approach to the graph realization problem: Theory, applications and extensions

It is a trivial matter to see that given the coordinates of n points in Rk , the distance between any two points can be computed efficiently. However, the inverse problem---given a subset of interpoint distances, find the coordinates of points (called a realization) in Rk (where k ≥ 1 is fixed) that fit those distances---turns out to be anything but trivial. This problem arises from many applications, such as sensor network localization and molecular conformation. Thus, many heuristics have been proposed. However, they either do not have any theoretical guarantees, or they work only for some very restricted classes of instances.; Recently, Biswas and Ye (2004) have proposed a semidefinite programming (SDP) based model for the problem and reported its superb experimental performance. Our work is motivated by the desire to explain this phenomenon in a rigorous manner. We begin by showing that the SDP model will find a realization in the required dimension if the input instance satisfies a certain uniqueness property. This uniqueness property has a straightforward geometric interpretation, and it allows us to identify a large class of efficiently realizable instances. Furthermore, it allows us to make some interesting connections with various notions in the rigidity theory of graphs.; Next, we consider a variant of the SDP model and discuss its connection with the theory of tensegrities in discrete geometry. We show how the theory of SDP can be used as an alternative proof technique for problems in tensegrity theory. Consequently, we are able to obtain qualitatively improved and constructive proofs for some results in tensegrity theory.; Finally, we consider an extension of the SDP model and study the problem of finding a low-rank approximate solution to a system of linear matrix equations. We show that a simple randomized polynomial-time procedure produces a low-rank solution that has provably good approximation qualities. Our result provides a unified treatment of and generalizes several well-known results in the literature. In particular, it contains as special cases results on low-distortion embeddings into low-dimensional Euclidean space, and approximation results on certain quadratic optimization problems.