A randomized method for solving discrete ill-posed problems
- PDF / 433,621 Bytes
- 15 Pages / 595.276 x 793.701 pts Page_size
- 24 Downloads / 255 Views
NEW MEANS OF CYBERNETICS, INFORMATICS, COMPUTER ENGINEERING, AND SYSTEMS ANALYSIS A RANDOMIZED METHOD FOR SOLVING DISCRETE ILL-POSED PROBLEMS D. A. Rachkovskija† and E. G. Revunova a‡
UDC 004.942+623.454.862
Abstract. An approach is proposed to the stable solution of discrete ill-posed problems on the basis of a combination of random projection of the initial ill-conditioned matrix with an ill-defined numerical rank and the pseudo-inversion of the resultant matrix. To select the dimension of the projection matrix, we propose to use criteria for the selection of a model and a regularization parameter. The results of experimental studies based on the well-known examples of discrete ill-posed problems are presented. Their solution errors are close to the Tikhonov regularization error, but a matrix dimension reduction owing to projection reduces the expenditures for computations, especially at high noise levels. Keywords: discrete ill-posed problem, random projection, regularization. INTRODUCTION For many practical applications, the solution of a discrete problem of the form Ax » b is required, where a matrix A and a vector b are known and a vector x should be estimated. If singular values of A smoothly decrease up to zero and the ratio between the largest and smallest non-zero singular values is large, then the problem is called a discrete ill-posed problem [1]. Approximate solutions of discrete ill-posed problems as least squares problems with the use of numerical methods of linear algebra such as LU, Cholesky, and QR decompositions are unstable. This means that a minor perturbation of input data leads to large solution perturbations. The solution of ill-posed problems is needed in many fields of science and engineering. Discrete ill-posed problems arise, for example, in discretizing Fredholm and Volterra first-kind integral equations. Important problems of spectrometry [2], gravimetry, magnetometry, electrical prospecting, and others possess properties of discrete ill-posed problems. Regularization methods [1–5] are proposed to overcome the instability and increase the accuracy of solutions of discrete ill-posed problems. Regularization imposes constraints on the sought-for solution that provide its stability. For example, Tikhonov’s regularization [3, 1] imposes a penalty on solutions with large l2 -norms. The drawbacks inherent in methods for solving discrete ill-posed problems on the basis of Tikhonov’s regularization are connected with a high computational complexity and difficulty of selecting an appropriate regularization parameter (penalty weight) exerting influence on solution stability. This determines actual needs for the development of alternative approaches to the solution of discrete ill-posed problems whose accuracy is comparable with Tikhonov’s regularization but computational expenditures are smaller. This paper proposes an approach using ideas of distributed neural net representation of information and random projections [6–9]. Recently, researchers in the field of numerical methods of linear alge
Data Loading...
