Next: conclusion
Up: Guitton: Huber solver
Previous: LBFGS update
The Huber norm Huber (1973, 1981) is a hybrid l^{1}l^{2} measure.
We expect to find the minimum of the function using a
quasiNewton method with a LBFGS update of the Hessian Guitton and Symes (1999). The Huber norm is
 

 (12) 
 
where
commands the limit between an l^{1} or l^{2} treatment of the residual; we call it
the Huber threshold and it must be given by the user. The gradient of the objective function
is given by
 
(14) 
where is the vector whose ith component is
Because the Huber function is not twice continuously differentiable, it does not satisfy the three necessary
conditions that guarantee the convergence to a minimum. However, we only need to compute the gradient for
the BFGS update of the Hessian. Furthermore, given that the approximated Hessian is certainly a vague
approximation of the real one (Symes, 1999, Personal communication), the violation of the initial conditions is mild.
In addition, results Guitton (2000) show that this method converges to a minimum.
Li (1995) shows that the Huber function has a unique minimizer for any meaningful choice of .
Indeed, if the l^{1} problem has multiple solutions Tarantola (1987),
then the Huber problem, provided that is small enough, also has multiple solutions. This is
annoying since we want to find a global minimum for the problem using quasiNewton updates.
In practice, however, it seems that
is a good choice for the threshold Darche (1989).
The threshold being set properly, the Huber function has mathematical properties
that allow the use of quasiNewton methods. We can now define an efficient algorithm in order to
solve the Huber problem:
Algorithm2
 1.
 Choose and the threshold . Set k=0
 2.
 Compute using equation 14
 3.
 Compute using a LBFGS update (Algorithm 1, step 3)
 4.
 Compute the step using a MoreThuente line search ( tried first)
 5.
 Update the solution
 6.
 Go to step 2
This algorithm will converge to the minimizer , as proven by Liu and Nocedal (1989).
Next: conclusion
Up: Guitton: Huber solver
Previous: LBFGS update
Stanford Exploration Project
4/27/2000