DOI:https://doi.org/10.15407/kvt210.04.026
Cybernetics and Computer Engineering, 2022, 4(210)
E.G. REVUNOVA1, DSc (Engineering),
Leading Researcher, Department of Neural Information Processing Technologies
e-mail: egrevunova@gmail.com
O.V. TYSHCHUK2,
Senior Software Engineer,
e-mail: avtyshcuk@gmail.com
O.O. DESIATERYK3, PhD (Phys&Math),
Assistant Professor, Faculty of Mechanics and Mathematics,
e-mail: sasha.desyaterik@gmail.com
1International Research and Training Center for Information Technologies and Systems of the National Academy of Sciences of Ukraine and the Ministry of Education and Science of Ukraine, 40, Acad. Glushkov av., Kyiv, 03187, Ukraine
2Roku Inc., Kyiv, Ukraine,
3Taras Shevchenko National University of Kyiv, 4e, Ave Glushkov, Kyiv, 03127, Ukraine
THE TECHNOLOGY OF THE STABLE SOLUTION FOR DISCRETE ILL-POSED PROBLEMS BY MODIFIED RANDOM PROJECTION METHOD
Introduction. Ill-posed problems solution is actual for many areas of science and technology. For example, discrete ill-posed problems (DIP) appears after discretization of the integral equations in the spectrometry, gravimetry, magnitometry, electrical prospecting and others.
In the case of linear DIP the matrix, which model some measuring system, makes a linear transformation of input vector to the output vector. Usually DIP output vector contains noise and singular values series of the matrix smoothly decrease to zero. In this case, the solution (input vector estimation) using the inversion of the transformation matrix is unstable and inaccurate. To overcome instability and increase accuracy we use regularization methods.
We develop an approach which uses regularizing properties of random projection to obtain a stable solution of DIP. However, the development of effective sustainable methods for solving DIP continues to be a problem of current interest.
The purpose of the paper is to increase the accuracy of DIP solution by the random projection method.
Results. In this paper we developed the method of stable solution of DIP by the modified method of random projection. For this modification the regularization by random projection is complemented by the regularization in the ridge regression style.
For the our method we obtained expressions which connect in the direct way the solution error components with the matrix specter and the regularization parameter. For the developed method the experimental research of the accuracy is conducted on the test problems.
Conclusions. The modified method of random projecting is characterized by stability and increased accuracy of the solution. This achieved by simultaneous ridge regression style regularization and random projecting. The representation of the solution error in the form where error components are related to the matrix specter and regularization parameter is important for further study of the error.
Keywords: random projection method, simultaneous ridge regression, regularization, stable solution, discrete ill-posed problems.
REFERENCES
1 Revunova E.G., Rachkovskij D.A. Using randomized algorithms for solving discrete ill-posed problems. Intern. Journal Information Theories and Applications. 2009. Vol. 2, N. 16. P.176-192.
2 Durrant R.J., Kaban A. Random projections as regularizers: learning a linear discriminant from fewer observations than dimensions. Machine Learning, vol. 99, N 2, 2015, P. 257-286.
https://doi.org/10.1007/s10994-014-5466-8
3 R.J. Durrant and A. Kaban. Compressed Fisher Linear Discriminant Analysis: Classification of Randomly Projected Data. In Proceedings16th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD 2010), 2010.
https://doi.org/10.1145/1835804.1835945
4 Xiang H., Zou J. Regularization with randomized SVD for large-scale discrete inverse problems. Inverse Problems. 29(8):085008, 2013.
https://doi.org/10.1088/0266-5611/29/8/085008
5 Xiang H., Zou J. Randomized algorithms for large-scale inverse problems with general Tikhonov regularizations. Inverse Problems. 2015. Vol. 31, N 8:085008. P. 1-24.
https://doi.org/10.1088/0266-5611/31/8/085008
6 Wei Y., Xie P., Zhang L. Tikhonov regularization and randomized GSVD. SIAM J. Matrix Anal. Appl. 2016. Vol. 37, N 2. P. 649-675.
https://doi.org/10.1137/15M1030200
7 Hansen, P. Rank-deficient and discrete ill-posed problems. Numerical aspects of linear inversion. Philadelphia: SIAM. 1998. 247 p.
https://doi.org/10.1137/1.9780898719697
8 Tikhonov A., Arsenin, V. Solution of ill-posed problems. Washington: V.H. Winston. 1977. 231 p.
9 Hansen, P.C. The truncated SVD as a method for regularization. BIT 27, (1987), 534-553.
https://doi.org/10.1007/BF01937276
10 Rachkovskij D.A., Revunova E.G. Randomized method for solving discrete ill-posed problems. Cybernetics and Systems Analysis. 2012. Vol. 48, N. 4. P. 621-635.
https://doi.org/10.1007/s10559-012-9443-6
11 Revunova EG, Rachkovskij DA, Stable transformation of a linear system output to the output of system with a given basis by random projections, The 5th Int. Workshop on Inductive Modelling (IWIM’2012), Kyiv, 2012, p. 37-41 (in Russian).
12 Revunova EG, Randomization approach to the reconstruction of signals resulted from indirect measurements, Proc. 4th International Conference on Inductive Modelling (ICIM’2013), Kyiv, 2013, p. 203-208 (in Russian).
13 Revunova E.G., Tyshchuk A.V. A model selection criterion for solution of discrete ill-posed problems based on the singular value decomposition, The 7th International Workshop on Inductive Modelling (IWIM’2015), Kyiv-Zhukyn, 2015, p.43-47(in Russian).
14 Revunova E.G. Analytical study of the error components for the solution of discrete ill-posed problems using random projections. Cybernetics and Systems Analysis. 2015. Vol. 51, N. 6. P. 978-991.
https://doi.org/10.1007/s10559-015-9791-0
15 Revunova E.G. Model selection criteria for a linear model to solve discrete ill-posed problems on the basis of singular decomposition and random projection. Cybernetics and Systems Analysis. 2016. Vol. 52, N.4. P.647-664.
https://doi.org/10.1007/s10559-016-9868-4
16 Revunova E.G. Averaging over matrices in solving discrete ill-posed problems on the basis of random projection. Proc. CSIT’17. 2017. Vol. 1. P. 473 – 478.
https://doi.org/10.1109/STC-CSIT.2017.8098831
17 Revunova E.G. Solution of the Discrete ill-posed problem on the basis of singular value decomposition and random projection. Advances in Intelligent Systems and Computing II. Cham: Springer. 2017. P. 434-449.
https://doi.org/10.1007/978-3-319-70581-1_31
18 Revunova E.G. Improving the accuracy of the solution of discrete ill-posed problem by random projection. Cybernetics and Systems Analysis. 2018. Vol. 54, N 5. P. 842-852 (in Russian).
https://doi.org/10.1007/s10559-018-0086-0
19 Revunova E.G., Tyshcuk O.V., Desiateryk О.О. On the generalization of the random projection method for problems of the recovery of object signal described by models of convolution type. Control Systems and Computers. 2021. N 5-6. P. 25-34.
https://doi.org/10.15407/csc.2021.05-06.025
20 Tyshchuk O.V., Desiateryk O.O., Volkov O.E., Revunova E.G., Rachkovskij D.A., A linear system output transformation for sparse approximation. Cybernetics and Systems Analysis. 2022. Vol. 58, N. 5. P. 840-850.
https://doi.org/10.1007/s10559-022-00517-3
21 Marzetta T., Tucci G., Simon S. A random matrix-theoretic approach to handling singular covariance estimates. IEEE Trans. Information Theory. 2011. Vol. 57, N 9. P. 6256-6271.
https://doi.org/10.1109/TIT.2011.2162175
22 Hansen P. C. Regularization Tools: A Matlab package for analysis and solution of discrete ill-posed problems. Numer. Algorithms. 1994. Vol. 6, N 1. P. 1-35.
https://doi.org/10.1007/BF02149761
23 Rachkovskij D.A, Revunova E.G. Intelligent gamma-ray data processing for environmental monitoring. In: Intelligent data analysis in global monitoring for environment and security. Kiev-Sofia: ITHEA. 2009. P. 124-145.
Received 04.10.2022