2
$\begingroup$

Let $A$ and $B$ be two sets of $d$-dimensional coordinates of comparible (though not necessarily equal length). For example, here we can set $d = 3$ and have normalized values like:

A = {{0.446362, 0.811292, 0.0922594},{0.244159, 0.260142, 0.304582}, {0.122547, 0.269019, 0.0644819},
     {0.448114, 0.828661, 0.733406},{0.347111, 0.296056, 0.398861}, {0.219952, 0.653454, 0.09107},
     {0.592839, 0.0333978, 0.210341},{0.0970157, 0.132429, 0.366429}, {0.294297, 0.527056, 0.403706},
     {0.196355, 0.115887, 0.636247},{0.993047, 0.51482, 0.229379}, {0.251266, 0.135959, 0.178469},
     {0.789068, 0.182785, 0.338934}, {0.42705, 0.151849, 0.671407}, {0.796922, 0.229053, 0.946328},
     {0.292144, 0.148314, 0.116313}, {0.589524, 0.474425, 0.0958731}, {0.181622, 0.140052, 0.958391},
     {0.0376616, 0.614436, 0.394617}};

B = {{0.690322, 1.17215, 0.961834}, {0.271458, 0.942832, 0.745714}, {0.508862, 1.03457, 0.3475}, 
     {0.81515, 0.378891, 0.465227}, {0.6036, 1.34974, 0.426426}, {0.405347, 0.463069, 1.27554},
     {1.12031, 0.604772, 1.19204}, {0.373017, 0.343105, 0.595875}, {0.642332, 0.602587, 0.678469},
     {0.884344, 0.746337, 0.38915}, {1.22961, 0.47189, 0.712069}, {0.56058, 0.755362, 0.648201},
     {0.596699, 0.465542, 0.646428}, {0.48087, 0.522362, 0.315634}, {0.752854, 1.17231, 0.421088},
     {0.693156, 0.546617, 0.9851}, {0.507197, 0.426626, 0.847138}, {0.584263, 0.452749, 0.422986},
     {0.545495, 0.427736, 0.494085}};

(Note that the order of the elements in $A$ and $B$ are of no consequence.)

While a bijection isn't possible, I would like to find the best possible "rigid mapping" between the elements in $A$ and $B$ where we add some fixed real number vector $Q=(q_1,q_2,q_3)$ to each coordinate in $B$ to minimize a weighted distance between pairs of coordinates in $A$ and $B$ according to some axis-specific cost function. Consider that in the above example, I've rigged things to make $Q = (q_1,q_2,q_3) \approx (0.3,0.3,0.3)$ about optimal (the largest error is of magnitude $\approx 0.1$).

To specify this cost function, we select array $A$ if it has more points than $B$ and vice versa. For convenience, let's say this array is $A$. Now let $(d_{(1,i)},d_{(2,i)},d_{(3,i)})$ be the shortest distance between a point $b_i \in B$ and $a_j \in A$. I'd like to have a cost function that looks something like:

$C = \sum_{i=1}^{||B||} || ((d_{(1,i)})^{z_1},(d_{(2,i)})^{z_2},(d_{(3,i)})^{z_3}) ||$

Where $(z_1,z_2,z_3)$ represents an arbitrary set of exponents. For a single real numbered value cost, we could compute the Norm of the above sum.

| improve this question | |
$\endgroup$
  • $\begingroup$ What do you mean by $(d_{(1,i)},d_{(2,i)},d_{(3,i)})$ being the shortest distance between ... ? (A distance should be a number >= 0) $\endgroup$ – Dr. belisarius Jun 30 '13 at 15:12
  • $\begingroup$ What's confusing about your question is that you seem to be searching for a vector Q, but Q does not appear in your cost function. $\endgroup$ – bill s Jun 30 '13 at 17:02
  • $\begingroup$ @belisarius Apologies for the slow response. Here, the $d$ values are meant as a nearest-neighbor distance from points in the shorter list to points in the longer list. I write below the cost function that we can compute $C$ as a norm of this distance along each axis (with different axis-specific penalties), but I will make this explicit in the cost function. $\endgroup$ – SparsePine Jun 30 '13 at 17:49
  • $\begingroup$ you seem to be working on finding something like principal components for your data set. $\endgroup$ – Rorschach Jun 30 '13 at 17:57
  • $\begingroup$ @Blackbird Yes, that's closely related - one could compute a set of principle components in one data set and then attempt to look for the corresponding components in the other. However, if possible, I'd sort of like to know how to do the optimization I specify without appealing to any image processing algorithms. It's also important to me to assign unique weights for displacement along the $d$ different axes. $\endgroup$ – SparsePine Jun 30 '13 at 18:00
3
$\begingroup$

Here is my interpretation of the stated problem. You will see that the solution found for $Q$ has the opposite sign than indicated in the OP, so perhaps something is not yet right. I interpreted "where we add some fixed real number vector $Q=(q_1,q_2,q_3)$ to each coordinate in $B$" to mean that $B$ is transformed by $b \mapsto b + Q$ for each $b \in B$; and that this transformation has occurred when we read "let $(d_{(1,i)},d_{(2,i)},d_{(3,i)})$ be the shortest distance between a point $b_i\in B$ and $a_j\in A$", so that $(d_{(1,i)},d_{(2,i)},d_{(3,i)}) = b_i + Q - a_j$, where $a_j$ is the point in $A$ nearest the transformed point $b_i + Q$ in $B$. (Keep in mind this is the interpretation that made the most sense to me, who does not understand where this problem comes from. So feel free to correct me. Better yet, clarify the statement of the problem.)

Here is the code (with A and B as in the OP):

Q = Array[q, 3];
nf = Nearest[A];
z = {1, 1, 1};

Clear[cost];
cost[q_?(VectorQ[#, NumericQ] &)] := Sum[Norm[(b + q - First@nf[b + q])^z], {b, B}];

FindMinimum[cost[Q], Evaluate@Transpose@{Q, ConstantArray[0.3, 3]}]
(* {1.71399, {q[1] -> -0.289018, q[2] -> -0.310557, q[3] -> -0.287473}} *)

Note the variables and initial values in FindMinimum are as follows:

Transpose @ {Q, ConstantArray[0.3, 3]}
(* {{q[1], 0.3}, {q[2], 0.3}, {q[3], 0.3}} *)

The distance vector is b + q - First@nf[b + q], where the NearestFunction nf returns the nearest $a_j \in A$ to b + q.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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