I have the following algorithm designed to find the global minimum of the simple function $y=(x+5)^2$.
cur_x = 3 # the algorithm starts at x=3
rate = 0.01 # learning rate
precision = 0.000001 # this tells us when to stop the algorithm
previous_step_size = 1
max_iters = 10000 # maximum number of iterations
iters = 0 # iteration counter
df = lambda x: 2*(x+5) # gradient of our function
while previous_step_size > precision and iters < max_iters:
prev_x = cur_x # store current x value in prev_x
cur_x = cur_x - rate * df(prev_x) # grad descent
previous_step_size = abs(cur_x - prev_x) # change in x
iters = iters+1 # iteration count
print("Iteration",iters,"\nX value is",cur_x) # print iterations
print("The local minimum occurs at", cur_x)
I'd now like to apply this to a localization problem, the Time Difference of Arrival problem, in 3-dimensions. That is, given the velocity $v$ of some signal, the coordinates $[x_i,y_i]$ of four observers (or, in general, $n+1$ observers for an $n$ dimensional solution), and the time of arrival at each observer, I want to reconstruct the coordinates $[x,y]$ of the signal source.
I've accomplished this in two dimensions using a slight variation of the approximation search algorithm found here: https://stackoverflow.com/questions/63707712/how-to-localize-a-signal-given-the-location-of-three-receivers-and-the-times-at/64318443#64318443. I'd now like to try doing so with gradient descent, although I'm not entirely sure how to apply it here (although I know it has been done).
I also know that the 2-dimensional solution can be described by the following nonlinear system:
$\sqrt{(x-x_1)^2+(y-y_1)^2}+s(t_2-t_1) = \sqrt{(x-x_2)^2 + (y-y_2)^2}$
$\sqrt{(x-x_2)^2+(y-y_2)^2}+s(t_3-t_2) = \sqrt{(x-x_3)^2 + (y-y_3)^2}$
$\sqrt{(x-x_3)^2+(y-y_3)^2}+s(t_1-t_3) = \sqrt{(x-x_1)^2 + (y-y_1)^2}$
How, precisely, might gradient descent be used to solve the problem in 3-dimensions?
I've had a look in the usual places (e.g., Wikipedia: https://en.wikipedia.org/wiki/Gradient_descent#Solution_of_a_non-linear_system), however I'm used to thinking of this "computationally" and I'm not familiar with the terminology/symbolism used there.
Having worked this problem, what I found is that it is much better to work with absolute times in order to decouple the equations.
In three dimensions, eash equation write as $$f_i=\sqrt{(X-x_i)^2+(Y-y_i)^2+(Z-z_i)^2}-v(t_i-T)=0$$ and you need to minimize $$\Phi(X,Y,Z,T)=\frac 12\sum_{i=1}^n f_i^2$$ which is extremely nonlinear; this means that you need "reasonable" estimates of the four variables $(X,Y,Z,T)$ before starting anything.
What I did is to consider in a preliminary step the equations $$g_i=(X-x_i)^2+(Y-y_i)^2+(Z-z_i)^2-v^2(t_i-T)^2$$ and built the $\frac {n(n-1)}2$ equations $(g_j-g_i)$ ($i$ varying from $1$ to $(n-1)$ and $j$ from $(i+1)$ to $n$); they write $$2 (x_j- x_i) X+2 (y_j- y_i) Y+2 (z_j- z_i) Z+2 v^2 (t_i-t_j)T=$$ $$(x_j^2+y_j^2+z_j^2-v^2 t_j^2)-(x_i^2+y_i^2+z_i^2-v^2 t_i^2)$$ This system is very easy to solve in the least-square sense using matrices. So, at this point, we have the estimates for the four variables $(X,Y,Z,T)$.
Now, we need to minimize $\Phi(X,Y,Z,T)$. Writing the partial derivatives, we have to solve the four equations $$\frac{\partial \Phi(X,Y,Z,T)} {\partial X}= \sum_{i=1}^n f_i \,\frac{\partial f_i} {\partial X}=0$$ $$\frac{\partial \Phi(X,Y,Z,T)} {\partial Y}= \sum_{i=1}^n f_i \,\frac{\partial f_i} {\partial Y}=0$$ $$\frac{\partial \Phi(X,Y,Z,T)} {\partial Z}= \sum_{i=1}^n f_i \,\frac{\partial f_i} {\partial Z}=0$$ $$\frac{\partial \Phi(X,Y,Z,T)} {\partial T}= \sum_{i=1}^n f_i \,\frac{\partial f_i} {\partial T}=0$$ with $$\frac{\partial f_i} {\partial X}=\frac{X-x_i}{\sqrt{(X-x_i)^2+(Y-y_i)^2+(Z-z_i)^2}}$$ $$\frac{\partial f_i} {\partial Y}=\frac{Y-y_i}{\sqrt{(X-x_i)^2+(Y-y_i)^2+(Z-z_i)^2}}$$ $$\frac{\partial f_i} {\partial Z}=\frac{Z-z_i}{\sqrt{(X-x_i)^2+(Y-y_i)^2+(Z-z_i)^2}}$$ $$\frac{\partial f_i} {\partial T}=v$$ This system of equations is quite easy to solve with Newton-Raphson method.