0
$\begingroup$

I would like to find a target point in a 3-dimensional space. I do not know the exact location of the target, but I can measure to it from some of the points in the space with a metric that roughly approximates distance to the target (smaller metric values are closer to the target). The metric is noisy and it's safe to assume variance is normally distributed. Measuring to the target is expensive and can only be done serially/iteratively.

This feels like a minimization problem, but I'm struggling to see how I can best choose my source points. Intuitively, if I measure to the target and I appear to be far away, I would want to select another source that's far away from where I just measured. Likewise, if I measure to the target and appear to be very close, I should next attempt to measure from a source that's close by to see if it's closer. What is a good approach to this problem?

Inputs to the algorithm are a set of point, P where the locations of the points are know and the target to measure to, T. The objective is to perform as few measurements as possible (iteratively) to find the closest point in the set of P to the target T. Bonus points if it's possible to establish some sort of error bounds that would presumably improve as more points are tested ultimately resulting in the finding the closest point (lowest measurement) if all points in P where tested.

$\endgroup$
3
  • $\begingroup$ I'm not very clear on the problem setup. What are the inputs to the algorithm? What are the black-box subroutines/oracles/queries that the algorithm can make? Are the locations of the other points (other than the target point) known? Can the algorithm pick any other point $P$ and measure an approximate distance from $P$ to the target, or is that only possible for a small subset of the other points? Is it more important to have a simple, easy-to-code algorithm or to minimize the number of times you measure an approximate distance? $\endgroup$
    – D.W.
    Feb 9 at 21:26
  • $\begingroup$ Can you say more about the approximate distance measure? If $D$ is the true distance and $A$ is your approximate measure, how are they related? Are they related by $A=D+N$ where $N$ is some noise with a known distribution, e.g., Gaussian with mean 0 and standard deviation $\sigma$? By $A=D(1+N)$ where $N$ is Gaussian? Something else? $\endgroup$
    – D.W.
    Feb 9 at 21:28
  • $\begingroup$ Thanks. I've added some description and tried to address your questions. $\endgroup$
    – turtle
    Feb 12 at 13:52

2 Answers 2

1
$\begingroup$

I can see many possible approaches. I don't think there's enough information to tell which will be best, so you might have to try them out and see.

Notation: Let $d(A)$ denote the true distance from $A$ to $T$ (which is not observable), and $\tilde{d}(A)$ for the measured distance from $A$ to $T$.

Method 1: One simple approach might be to apply repeated trilateration. Pick 3 points $A_1,A_2,A_3$ randomly, measure the distances $\tilde{d}(A_i)$, and use trilateration to infer an approximate position $\hat{T}$ of $T$. Repeat multiple times, each time picking points from within some sphere centered around $\hat{T}$ from the previous iteration. Perhaps you halve the radius of the sphere in each iteration, or perhaps you use $2\tilde{d}(\hat{T})$ as the radius of the sphere. Eventually, once the number of points in the sphere is small enough, you can try all of them, and hopefully this finds the point nearest to $T$.

Method 2: You might be able to further reduce the number of measurements by using more sophisticated statistical methods, specifically, maximum likelihood estimation. Let's suppose you have some mathematical error model for $\tilde{d}(A)$, say,

$$\tilde{d}(A) = d(A) + E$$

where $E \sim \mathcal{N}(0,\sigma^2)$ has a Gaussian distribution with known variance $\sigma^2$ (which does not depend on $A$). Then for any point $A$ with observed measurement $\tilde{d}(A)$ you can derive a likelihood function for the location of $T$, namely,

$$p(x) = {1 \over \sigma \sqrt{2\pi}} e^{-((|x-A|_2-\tilde{d}(A))/\sigma)^2/2}$$

gives the likelihood that $T$ is at position $x \in \mathbb{R}^3$. Taking logs of both sides, and ignoring additive constants (which won't matter), the log likelihood given a single measurement is

$$\log p(x) = -\frac{1}{2} ((\|x-A\|_2-\tilde{d}(A))/\sigma)^2 + \text{a constant}.$$

Now if we have multiple measurements, say $\tilde{d}(A_i)$ for $k$ points $A_1,\dots,A_k$, then the log likelihood of $T$ is the sum of the log likelihoods for each $A_i$, and thus

$$\log p(x) = -{1 \over 2 \sigma^2} \sum_{i=1}^k (\|x-A_i\|_2-\tilde{d}(A_i))^2 + \text{a constant}.$$

Our goal will be to find the location $x$. Now the maximum likelihood estimation technique suggests that we find the location $x$ that maximizes $p(x)$, and use that as our best guess at the position of $T$. Equivalently, since the logarithm is a monotonic function, we can maximize $\log p(x)$. Additive or multiplicative constants don't change the location of the maximum. Therefore, we can define

$$\Phi(x) = \sum_{i=1}^k (\|x-A_i\|_2-\tilde{d}(A_i))^2,$$

and then minimizing $\Phi(x)$ will be equivalent to maximizing $\log p(x)$.

So the approach becomes as follows. Pick a few points $A_1,\dots,A_k$ (say, 5 of them or so). Measure $\tilde{d}(A_i)$. Then, use an optimization algorithm to find $x \in \mathbb{R}^3$ that minimizes $\Phi(x)$. This is your estimate $\hat{T}$ of the location of $T$. Basically, this gives you a way to do trilateration that is tolerant of noise and errors in the measurements, and can make use of measurements from $k\ge 3$ points.

Finally, repeat this iteratively. At each stage, given $\hat{T}$, pick a few more points (perhaps as in Method 1), measure the distance to those points, add them to your collection of points (incrementing $k$ for each, so that $A_1,\dots,A_k$ contains all points you have ever done a measurement for), and then use maximum likelihood estimation to estimate $\hat{T}$ given all of those measurements.

To do the optimization, you'll need to minimize a complicated nonlinear function of $x$. One approach is to use Newton's method with some appropriate initialization, e.g., the prior value of $\hat{T}$, or a value obtained by trilateration with the 3 last measurements.

This statistical treatment assumes that the error model for $\tilde{d}(\cdot)$ has a particular mathematical form. If it has some other mathematical form, then you'll need to adjust the above derivation to write down the appropriate expression for the log likelihood and then define $\Phi$ accordingly.

$\endgroup$
1
$\begingroup$

Your problem seems like a Nearest Neighbor Search but with an approximate distance. There are many indexing methods to solve it approximately.

  • IVF Index: divides space into regions and assigns a centroid point to each region. Then it searches first the centroids and then it focus only on the regions assigned to the closest centroids. It's a heuristic, no guarantees, but it works well in practice and you can manage the accuracy/speed trade-off by adjusting the parameter of the number of centroids to expand.
  • Hashing-based methods: use some Locality-Sensitive hashing function to find the right group of points and then look at them. (see Locality Sensitive Hashing (LSH) ). These approaches can offer guarantees thanks to the collision properties of hash functions.
  • Graph-Based method: Build a proximity graph by connecting your points trough edges. Then navigate this graph in a greedy manner to reach the target point in few steps. Ideal graph structures offers guarantee on finding the right answer (up to noise), however you often opt for approximate solutions which are way faster to build
  • Tree-based approaches: kd-trees, vp-trees, k-means trees, spatial-aprroximation tree, etc. They all build trees you can navigate to find the right point, discarding useless points.

These are the main approaches to solve the so-called Approximate Nearest Neighbors Search. The best option depends on many factors (dimensionality of vectors, memory, search speed, construction time, etc).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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