Next: Resolution of the normal
Up: L^{p} MINIMIZATION WITH THE
Previous: Normal equations
At the iteration k+1, the algorithm solves:

A^{T}W^{k}A.x^{k+1} = A^{T}W^{k}.y

(6) 
by taking:
 W^{0} = I_{n} (Identity matrix), at the first iteration,
 W^{k} formed with the residuals of iteration k (r^{k}=yAx^{k}), at the
iteration k+1 .
Byrd and Payne (1979) showed that this algorithm is convergent under two
conditions:
 W(i) must be nonincreasing in r(i),
 W(i) must be bounded for all i.
The first condition is satisfied for ; to assure the second
condition, Huber (1981) suggested replacing equation (3) with:
 
(7) 
for a small positive constant .
Equations (6) are the normal equations of the leastsquares
minimization of:
W^{k} has the role of a weighting matrix, the inverse of a
covariance matrix. By giving the large residuals small weights
(or large variances), it reduces their role; on the contrary, well predicted
values will be given large weights (small variances). Aberrant values,
receiving low weights, will have a small influence: this makes the algorithm
robust, less sensitive to noise bursts in the data. This is especially true for
the extreme case p=1, as it had been predicted by Claerbout and Muir (1973).
However, the L^{1} norm is not strictly convex; so, the L^{1} minimization
problem might have nonunique solutions. The IRLS algorithm will lead
us to one of these solutions. The fact that the first iteration (W^{0}=I_{n})
is a leastsquares inversion makes me think that this algorithm will lead us
to a solution close to the L^{2} solution. The choice of W^{0}(i)=y(i)^{p2}
is not reasonable: during the
algorithm, x stays close to 0, and the algorithm converges (if it does) to
a vector also close to zero, the residuals staying close to the
original vector y.
Next: Resolution of the normal
Up: L^{p} MINIMIZATION WITH THE
Previous: Normal equations
Stanford Exploration Project
1/13/1998