The source files for all examples can be found in /examples.

Euclidean Distance Matrix Completion

This example illustrates how to use Chordal.jl to complete a partially-specified Euclidean Distance Matrix (or determine no such completion exists).

Euclidean Distance Matrices

Given $N$ vectors $x_1,\dots,x_n$ in $\mathbb{R}^n$, the associated Euclidean Distance Matrix (EDM) $D \in \mathbb{R}^{N \times N}$ records the squared distance between each pair $x_i, x_j$. Specifically,

\[D_{ij} = \|x_i - x_j\|_2^2.\]

Given a partially-specified EDM $D$ which has a chordal sparsity pattern, we would like to find the missing entries.

using Chordal
using LinearAlgebra, SparseArrays

Small Example

This small example is taken from Jon Dattorro's Convex Optimization & Euclidean Distance Geometry eq (1041). First, we construct the partially-specified EDM.

D = sparse([
    0.0 1 5 0;
    1 0 4 1;
    5 4 0 1;
    0 1 1 0
])
@show D

# Next, we complete the matrix
D_complete = sparse(edm_completion(D))
println("\nCompletion:")
@show D_complete

4×4 SparseArrays.SparseMatrixCSC{Float64, Int64} with 12 stored entries:
  ⋅   1.0  5.0  2.0
 1.0   ⋅   4.0  1.0
 5.0  4.0   ⋅   1.0
 2.0  1.0  1.0   ⋅ 

Larger Random Example

First, we generate an EDM from 17 vectors in $\mathbb{R}^3}$.

n = 17
r = 3
V = randn(n, r)
VV = V*V'
D_full = diag(VV)*ones(n)' + ones(n)*diag(VV)' - 2VV;

Next, we remove entries. and complete the The sparsity pattern is from Figure 4.2 in Lieven Vandenberghe and Martin S. Andersen's Chordal Graphs and Semidefinite Optimization.

ijs = [(3,1), (3,2), (4,1), (4,2), (4,3), (5,1), (5,3), (5,4), (8,7),
       (9,5), (9,6), (9,7), (9,8), (11,10), (13,10), (13,11), (13,12),
       (14,10), (14,11), (14,12), (14,13),
       (15, 1), (15,3), (15,4), (15,5), (15,7), (15,8), (15,9),
       (16,5), (16,6), (16,9), (16,12), (16,13), (16,14), (16,15),
       (17,10), (17,11), (17,12), (17,13), (17,14), (17,15), (17,16)]
append!(ijs, [(i,i) for i in 1:n])
II, JJ = Chordal.unzip(ijs)
sp = sparse(II, JJ, ones(length(II)))
sp = sp + tril(sp)'

# Remove entries s.t. the remaining entries have a chordal sparsity pattern
D = sp .* D_full

# Complete the matrix
@show Chordal.is_edm(edm_completion(D))

true

This page was generated using Literate.jl.