Abstract: In this paper, we develop an approach for improving the accuracy and speed of the solution of discrete ill-posed problems using the pseudo-inverse method. It is based on a random projection of the initial coefficient matrix. First, a brief introduction is given to least squares and discrete ill-posed problems, approximate matrix decompositions with randomized algorithms, and randomized least squares approximations. Then, we describe the techniques used in this paper to solve discrete ill-posed inverse problems, including the standard Tikhonov regularization and pseudo-inverse after a random projection. The bias-variance decomposition of solution errors is provided for different solution techniques and it is shown experimentally that the error has a minimum at some value of the varied smaller dimension of the random projection matrix. Taking two well-known test examples of the discrete ill-posed problems of Carasso and Baart, we obtain experimental results of their solution. The comparison shows that the minimal error of the pseudo-inverse solution after a random projection is close to the error of the standard Tikhonov regularization, but the former solution is obtained faster, especially at the larger noise values.

Keywords: discrete ill-posed problems, pseudo-inverse, regularization, random projection, bias, variance

ACM Classification Keywords: I.5.4 Signal processing, I.6 SIMULATION AND MODELING (G.3), G.1.9 Integral Equations

Link:

USING RANDOMIZED ALGORITHMS FOR SOLVING DISCRETE ILL-POSED PROBLEMS

Elena G. Revunova, Dmitri A. Rachkovskij

http://foibg.com/ijita/vol16/IJITA16-2-p06.pdf