Two optimisation ideas for locating a target

22 May 2018

João Xavier ISR

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.



João Xavier is a professor at the Department of Electrical Engineering, Instituto Superior Técnico, University of Lisbon, and a researcher at the Instituto de Sistemas e Robótica (ISR), Lisbon. He delights in being continually surprised by unexpected links between statistical signal processing, probability theory and stochastic control.