Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 2 down vote favorite

I'm trying to solve the following minimization problem, and I'm sure there must be a standard methodology that I could use, but so far I couldn't find any good references. Please let me know if you have anything in mind that could help or any references that you think would be useful for tackling this problem.

Suppose you are given $K$ points, $p_i \in R^n$, for $i \in \{1,\ldots,K\}$. Assume also that we are given $K$ constants $\delta_i$, for $i \in \{1,\ldots,K\}$. We want to find the vector $x$ that minimizes:

$\min_{x \in R^n} \sum_{i=1,\ldots,K} || x - p_i ||^2$

subject the following $K$ constraints:

$\frac{ || x - p_i ||^2 } { \sum_{j=1,\ldots,K} ||x - p_j||^2} = \delta_i$

for all $i \in {1,\ldots,K}$.

Any help is extremely welcome!

Bruno

edit: also, we know that $\sum_{i=1,\ldots,K} \delta_i = 1$.

share|improve this question
@Bruno: The standard methodology is to use the method of linear least squares (the linear algebra way). Check out tutorial.math.lamar.edu/Classes/LinAlg/LeastSquares.aspx and en.wikipedia.org/wiki/… – InterestedGuest May 21 '11 at 0:02
@InterestedGuest: Yes, I was trying to solve this using least squares, but it's not clear to me how to deal with the constraints. I thought it could be a variation of the typical setting but with a slightly different loss function, but I'm not sure how to model it. In a way it looks like the opposite of LLE (Locally-Linear Embedding): here we are given an embedding (the space where the $p_i$'s live) and we want to find a point in it that is at some given relative distance of its K neighbors. However, while in LLE the embedding is being constructed, here the topology and geometry are fixed – Bruno May 21 '11 at 6:07
@Will: What do you mean, the function cannot change? For each $x$ that we could pick, it will be at a given distance of each of the $p_i$'s; we want the $x$ that minimizes the sum of those distances. However, at the same time we are constraining it in a way that the ratio of the distance of $x$ to a given $p_i$, relative to the total distances involved, is fixed. This is because we might want $x$ to be, for instance, 2 times closer to $p_1$ than to $p_2$. Could you please elaborate on your answer? – Bruno May 21 '11 at 6:10
@Will: you are right; I actually forgot to include the constraint that the given $\delta_i$'s for sure sum up to 1. The basic idea is this: we have K points $v_i$ in a given space, and are given some other point Y. Y might be 2x closer to $v_1$ than to $v_2$; so $\delta_1 = 1/3$ and $\delta_2 = 2/3$. Now we are given K points $p_i$ in some other space, of different dimensionality, such that their coordinates are basically $v_i$'s coordinates, scaled. Thus, all relative distances are preserved. We want to find the point $x$ in the 2nd space that would correspond to $Y$. We do so (...) – Bruno May 21 '11 at 7:00
(...) by looking for a point $x$ whose relative distance to each of its K neighbors in the new space is consistent with the relative distance of $Y$ to its K neighbors in the original space. If $v_1$ was mapped to $p_1$ and $v_2$ to $p_2$, $x$ should be 2x closer to $p_1$ than to $p_2$. Note that if the dimensionality of the 2nd space is much larger than the dimensionality of the 1st space, there could be several $x$'s that respect those contraints; we define that we want to find the one that is closer to the actual points that are given (the $p_i$'s), so we minimize the total sum of distances – Bruno May 21 '11 at 7:03
show 5 more comments

2 Answers

up vote 1 down vote

You can try using Lagrange multiplier method - see wikipedia.

share|improve this answer
up vote 1 down vote

Yes, this works. If $n \leq K-2,$ you have no guarantee of any legal solution, even when the $\delta_i$ sum to 1, as required. It may be that the sample points, your $v_j$ and $Y,$ were in a Euclidean space of much lower dimension, however, that does not guarantee you can repeat that piece of luck if the new $n$ in $\mathbf R^n$ is too small.

If $n = K -1,$ there should be a single feasible point, "near" the simplex with the $K$ points as vertices. No need (or ability) to minimize anything. Actually, unless the $\delta$'s are all equal, it appears there is a second feasible point far away. If all angles in the simplex are acute, there is a feasible point in its interior.

So, my advice is, figure out how to find a feasible point when $n=K-1.$ If circumstance forces $n \geq K,$ rotate so the hyperplane containing all the $p_i$ becomes the hyperplane $x_1, x_2, \ldots, x_{K-1}, 0,0,\ldots,0,$ solve the problem there, then rotate back.

Meanwhile, I see nothing wrong with a numerical method for finding the single feasible point near the simplex when $n=K-1.$ Easier than finding the intersection of a large number of spheres and planes. Note that, when $n=K,$ the full set of all feasible points is either a straight line (if all $\delta_i$ are equal) or, in fact, an actual circle. Go figure. In either case, meeting the hyperplane that contains the $p_i$'s orthogonally.

For that matter, your easiest program is just to solve the problem in the original $v_i, Y$ location, that is, a numerical method that finds the point $Z$ near the $v_i$ simplex with the correct $\delta$'s. Then you can just map $Z$ along with the $v_i.$

share|improve this answer
Thanks, Will. Let me think about your suggestions. In my case, $n >> K$ and the 2nd space is much larger than the 1st one. I am considering using a variation of how LLE constructs its embedding: assume that points lie on a manifold and reconstruct each one via a linear combination of its neighbors. Then, transfer "linear patches" of points from one space to the other, preserving the weights in that combination. If we constraint the best weights to be between 0 and 1, the mapping is invariant to rotations, scalings and translations, which makes the problem much easier. Thanks, once again! – Bruno May 22 '11 at 17:15
My email can be found by searching with my last name at $$ $$ ams.org/cml $$ $$ You seem to have a way to go in finding the right mathematical description of this. – Will Jagy May 22 '11 at 17:49

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.