Home
Wikimization
Contact Us
Accumulator error feedback
CVX Download
Calculus of Inequalities
Rick Chartrand
Chromosome Structure EDM
Complementarity problem
Compressive Sampling
Compressed Sensing
Conic Independence
Convex Cones
Convex Functions
Convex Geometry
Convex, Affine, Conic: Hulls
Convex Iteration
Convex Optimization
Convex Optimization Group
Dattorro PC Optimization
Dattorro Supercomputer
Distance Geometry
Distance Matrix Cone
Dual Cones
Duality Gap
Eigenvalues/Eigenvectors
Elliptope and Fantope
Euclidean Distance Matrices
EDM cone faces
Extreme Directions
Face Recognition
Farkas Lemma
Fermat point
Fifth Metric Property
Jensen's Inequality
Jobs in Optimization
Kissing Number
Harold W. Kuhn
Linear Algebra
Linear Matrix Inequality
Manifold Learning
MATLAB for Optimization
Matrix Calculus
Molecular Conformation
Moreau's theorem
Isaac Newton
Angelia Nedic
Open Problems
Positive Matrix Factorization
Positive Semidefinite Cone
Projection
Projection on Cone
Proximity Problems
PY4SCIENCE
Quasiconvex Functions
Rank Constraint
Rockafellar
Justin Romberg
Michael Saunders
Schoenberg Criterion
Semidefinite Programming
Sensor Network Localization
Smallest Simplex
Systems Optimization Lab
Stanford SOL
Talks on Optimization
Joshua Trzasko
Video
Wikimization     Meboo     SOL      Video     CVX     Contact     
Felice crystal
Home arrow Distance Geometry
Distance Geometry

Euclidean distance geometry is, fundamentally, a determination of point conformation (configuration, relative position or location) by inference from interpoint distance information.  By inference we mean: eg, given only distance information, determine whether there corresponds a realizable conformation of points; a list of points in some dimension that attains the given interpoint distances.  Each point may represent simply location or, abstractly, any entity expressible as a vector in finite-dimensional Euclidean space.

                    Orion nebula

It is a common misconception to presume that some desired point conformation cannot be recovered in the absence of complete interpoint distance information.  We might, for example, realize a constellation given only interstellar distance (or, equivalently, distance from Earth and relative angular measurement; the Earth as vertex to two stars).  At first it may seem O(N^2) data is required, yet there are many circumstances where this can be reduced to O(N).

If we agree that a set of points can have a shape three points can form a triangle and its interior, for example, four points a tetrahedron), then we can ascribe shape of a set of points to their convex hull.  It should be apparent: these shapes can be determined only to within a rigid transformation (a rotation, reflection, and a translation).

Absolute position information is generally lost, given only distance information, but we can determine the smallest possible dimension in which an unknown list of points can exist; that attribute is their affine dimension (a triangle in any ambient space has affine dimension 2, for example).  In circumstances where fixed points of reference are also provided, it becomes possible to determine absolute position or location.

Geometric problems involving distance between points can sometimes be reduced to convex optimization problems.  Mathematics of this combined study of geometry and optimization is rich and deep.  Its application has already proven invaluable discerning organic molecular conformation by measuring interatomic distance along covalent bonds.  Many disciplines have already benefitted and simplified consequent to this theory; eg, distance-based pattern recognition, localization in wireless sensor networks by measurement of intersensor distance along channels of communication, wireless location of a radio signal source such as a cell phone by multiple measurements of signal strength, the global positioning system (GPS), and multidimensional scaling which is a numerical representation of qualitative data by finding a low-dimensional scale.  Euclidean distance geometry has also found application in artificial  intelligence: to machine learning by discerning naturally occurring manifolds in Euclidean bodies, in Fourier spectra of kindred utterances, and in image sequences.

Read more...

 
Course,   Video
Convex Optimization
     convex optimization
Stephen Boyd 
L. Vandenberghe 


Dattorro      convex optimization Euclidean distance geometry 2ε
Dattorro


Course
Bertsekas
     books by Bertsekas
Dimitri Bertsekas 


See Inside Hiriart-Urruty & Lemaréchal
Hiriart-Urruty
& Lemaréchal


See Inside
Rockafellar Rockafellar