A novel sine transform based preconditioned conjugate gradient (PCG) method for signal restoration is presented. If the bandwidth 2/3+ 1 in the model matrix is a constant, then the asymptotic complexity for the new algorithm is O(N) per iterative step, where N is the order of the model. This complexity is reduced by an order of magnitude in comparison with the known fast Fourier transform (FFT) technique proposed recently in the literature. Moreover, if/3 has a size similar to N, then the new PCG method is accomplished by the fast sine transform (FST) and the fast Hartley transform (FHT). The computational and storage cost per preconditioning step for the new PCG method is reduced by 50 as compared to the FFT approach. To stabilize the computation, a special Tikhonov regularization is introduced. Numerical experimentations show that the new PCG method is of a speedy convergence rate. The new PCG methods maintain less computational complexity per iterative step and have a better convergence rate than the other known PCG methods.# 1999 Society of Photo-Optical Instrumentation Engineers. S0091-3286(99)00911-3
展开▼
