Two optimisation ideas for locating a target
We want to guess the position of a target, based only on how weakly or strongly its emitted wireless signal is received at a few places. Assuming usual probabilistic properties of wireless channels, we proceed to frame this problem as a maximum likelihood (ML) estimation problem. The ML estimate, however, is deceptively hard to compute, for it lies in the bowels of a difficult nonconvex minimisation problem. With dim hopes of quickly computing the global minimiser, we honourably retreat to a realistic goal – computing a local minimiser.
We suggest two paths. The first path was opened by a sift through the toolbox of convex trickery that revealed two inequalities fitting our problem structure; combining those inequalities allows to compute a local minimiser by solving a sequence of easy convex problems. For the second path, we reformulate the nonconvex optimisation problem in such a way that it begs to be solved by a randomised algorithm that moves along by solving proximal operators of nonconvex functions. Both paths perform surprisingly well in practice, although we don’t have a clue on how to prove it theoretically – just as in deep learning.