# maximum variance unfolding

Consider positive weights $\pi_1, \ldots, \pi_n$ (one can suppose that they add up to $1$) and $n-1$ lengths $d_1, \ldots, d_{n-1}$. Is there an analytical solution to the following problem: find the configuration of $n$ vectors $X_1, \ldots, X_n \in \mathbb{R}^n$ that maximizes the weighted sum $$V(X_1, \ldots, X_n) = \pi_1 \|X_1\|^2 + \ldots + \pi_n \| X_n\|^2$$ under the constraints $\|X_{i+1}-X_i\| \leq d_i$ for $i=1, 2, \ldots, n-1$ and $\sum_i \pi(i) X_i = 0$.

Motivation: as described in this article, this is another formulation of the following problem: among all possible reversible Markov chain in continuous time that have $\Pi=(\pi_1, \ldots, \pi_n)$ as invariant distribution on $\{ 1, \ldots, n\}$ and that can only jump on neighbouring sites, find the one that has maximum spectral gap, under a certain (linear) constraint on the jump intensities.

Remarks:

• one can consider the more general problem where the constraints are $\|X_i-X_j\| \leq d_{i,j}$: one can show that this is equivalent to a semidefinite programming optimization problem. It seems in general hard to solve; see above mentioned article.
• the case $\pi(1) = \ldots = \pi(n)$ is exactly solvable and an optimal configuration is a set of $n$ collinear vectors $X_i = \alpha_i U$, where the $\alpha_i$'s are easily computable; in this case, the problem is equivalent to maximizing $\sum_{i,j} \|X_i-X_j\|^2$.
-
Alekk, the article link is broken... – Joseph O'Rourke Jan 20 '11 at 15:38
thanks: should be fixed now. – Alekk Jan 20 '11 at 16:45