gt.geometric topology - Topological scaling (?)

Let $x_i$ be the coordinate of point $i$ and imagine there is an edge $e_{ij}$ between any pair of neighbors. The optimization problem

$$begin{array}{rl} underset{x}{mathrm{argmin}} & displaystylesum_{e_{ij}} left( x_j - x_i right)^2 \ mathrm{s.t.} 0 leq x_i leq 1 end{array}$$

is a strongly convex optimization problem (namely, a linearly constrained quadratic program or LCQP), hence it has a unique global minimum. Hence, the solution can be computed in polynomial time using an interior point method such as the barrier method. In fact, box-constrained quadratic programs can be solved quite efficiently and implementations are readily available (in MATLAB, for instance). In order to avoid trivial solutions, imagine that some of the $x_i$ are constrained to lie on the boundary, e.g., you can either add constraints like $x_i^1=1$ (where the superscript denotes the component) or simply hold some of the $x_i$ fixed.

Note that this problem attempts to minimize the pairwise distance rather than maximize it. On a compact domain the two problems will yield similar results, but the latter problem is nonconvex and hence it is harder to make guarantees about global optimality.

• Next translation - Transcription of a panel discussion about G.Perelman
• Previous lo.logic - Can you tell if you have escaped from a recursive definition?