Stability of the IRLS algorithm in deconvolution

The results concerning the conditioning and the eigenvalues of the equations  (6) are unfortunately less accurate. The matrix A^TWA is no longer Toeplitz. To compute its eigenvalues would require us to know the singular-value decomposition of A, which increases the cost of the computations.

I could only observe that A^TA and A^TWA have more or less the same condition number during the IRLS algorithm; consequently, the weighted least-squares problems are also ill-conditioned if the original power spectrum of the filter a is band-limited. However, I have no general results concerning the repartition of the eigenvalues of A^TWA.

The choice of $\varepsilon$ is not completely free. The synthetic examples I used showed that the more ill-conditioned the initial matrix A^TA is, the larger $\varepsilon$ should be taken, otherwise the IRLS algorithm does not converge. For example, with a condition number equal to 1000, I took $\varepsilon = \mbox{Max}\vert y\vert/100$, and the convergence (rate 1/10000) was reached in 10 iterations; with a condition number equal to 10000, I took $\varepsilon = \mbox{Max}\vert y\vert/10$, even with double precision. Increasing $\varepsilon$ makes W closer to the identity matrix, in which case the problem corresponds more to a L² minimization: we would be solving a mixed L¹-L² problem, as I will explain later.

In conclusion, I may expect the convergence of the CG algorithms to be slow if the power spectrum of the filter a contains some small values. Despite the suggestion to limit the number of iterations in order to cope with the ill-conditioning, I prefer to increase their number, to be closer to the numerical limits. However, the speed of convergence is greatly increased if it is possible to give a first estimate of the unknown x: that is the case in predictive deconvolution, where the first estimate would be the L²-Wiener filter.