On the stability of transform-based circular deconvolution

The solution of a set of linear equations involving a circulant matrix is easily accomplished with an algorithm based on fast Fourier transforms. The numerical stability of this algorithm is studied. It is shown that the algorithm is weakly stable; i.e., if the circulant matrix is well conditioned, then the computed solution is close to the exact solution. On the other hand, it is shown that the algorithm is not strongly stable - the computed solution is not necessarily the solution of a nearby circular deconvolution problem.