Control Systems and Computers

DOI: https://doi.org/10.15407/usim.2018.01.016

Upr. sist. maš., 2018, Issue 1 (273), pp. 16-27.

UDC 004.942+6232.454.862

Revunova Elena G., PhD in Technical Sciences,  Deputy Director on Research, International Research and Training Center for Information Technologies and Systems of the NAS and MES of Ukraine, Glushkov ave., 40, Kyiv, 03187, Ukraine, E-mail: helab@i.com.ua

Studying the Accuracy for the Solution of Discrete Ill-Posed Problems Using the Method of Random Projection

Introduction. Discrete ill-posed problems (DIP) often arise when restoring signals obtained as a result of indirect measurements. A stable solution of DIP can be obtained, for example, by the method of truncated singular value decomposition and by the method of random projection (RP). The accuracy of solving DIP by the RP method is determined by the influence of two independent random variables: additive noise in the output vector and a random variable that forms a random matrix. The change in the number of rows of a random matrix leads to a change in the accuracy of the DIP solution. Noisiness of the output vector leads to the appearance of a component of the error, the value of which increases with the number of rows of the random matrix and is scaled by the noise level. Therefore, the dependence of the error of DIP solution on the number of rows of the random matrix at certain noise levels has a minimum at  (row number of the random matrix less then row number of the DIP matrix). Averaging over random matrices leads to a smoothing of the dependence of the solution error on k and to a decrease in the number of local minima. The study of bias and variance of the error, arising from averaging over the realizations of the random matrix, made it possible to obtain a much more accurate estimate of the input vector.

Purpose. The aim is develop a method for determining the optimal size of a random matrix for the method of DIP solving based on the refined evaluation of the input vector.

Results and conclusions. The method of DIP solving based on the analytical averaging of random projection has been proposed. For this method, we have developed the criterion  for determining the number of rows of a random matrix which provides the error of DIP solution close to the minimum. We conducted an experimental investigation of the accuracy of DIP solution by a deterministic method based on the analytical averaging of random projection with the search for the optimal solution by the model selection criteria of Mallows, Akaike, Minimum description length, and . The experiments showed that  and Akaike criteria provide the error value close to the minimum.

Perspective. The direction of further work is the use of a deterministic method for DIP solution based on analytical averaging of random projection in applied problems.

Keywords: discrete ill-posed problem, regularization, random projection.

 Download full text! (In Russian).

1. Hansen, P., 1998. Rank-deficient and discrete ill-posed problems. Numerical aspects of linear inver-sion. Philadelphia: SIAM, 247 p. https://doi.org/10.1137/1.9780898719697
2. Tikhonov, A., Arsenin, V., 1977. Solution of ill-posed problems. Washington: V.H. Winston, 1977, 231 p.
3. Starkov, V., 2002. Constructive methods of computational physics in interpretation problems. Kiev: Nauk. Dumka, 263 p.
4. ZABULONOV, Yu.L., KOROSTYL, Yu.M., REVUNOVA, E.G., 2006. “Optimization of the solution of the inverse problem for the restoration of the density distribution function of surface contaminants”, Sb. nauchn. trudov IPME NAN Ukrainy. Modeling and information technology, 39, pp. 77–83. (In Russian).
5. Rachkovskij, D.A., Revunova, E.G., 2009. “Intelligent gamma-ray data processing for environ-mental monitoring”. Intelligent data analysis in global monitoring for environment and security, Kiev–Sofia, ITHEA, pp. 124–145.
6. Hansen, P.C., 1987. “The truncated SVD as a method for regularization”. BIT 1987, 27, pp. 534–553. https://doi.org/10.1007/BF01937276
7. REVUNOVA, E.G., TYSHCUK, A.V., 2014. “Model Selection Criterion for the Solution of Discrete Ill-Posed Problems Based on Singular Value Decomposition”. Upr. sist. maš., 6, pp. 3–11. (In Russian).
8. Revunova, E.G., Tyshchuk, A.V., 2005. “A model selection criterion for solution of discrete ill-posed problems based on the singular value decomposition”. The 7th Int. Workshop on Inductive Modelling (IWIM’2015), Kyiv–Zhukyn, pp. 43–47.
9. Revunova, E.G., 2016. “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, 52 (4), pp. 647–664. https://doi.org/10.1007/s10559-016-9868-4
10. Revunova, E.G., Rachkovskij, D.A., 2009. “Using randomized algorithms for solving discrete ill-posed problems”. Int. J. Information Theories and Applications, 2 (16), pp. 176–192.
11. Revunova, E.G., 2010. “Study of error components for solution of the inverse problem using random projections”. Mathematical Machines and Systems, 4, pp. 33–42.
12. Rachkovskij, D.A., Revunova, E.G., 2012. “Randomized method for solving discrete ill-posed problems”. Cybernetics and Systems Analysis, 48 (4), pp. 621–635. https://doi.org/10.1007/s10559-012-9443-6
13. Revunova, E.G., Rachkovskij, D.A., 2012. “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, pp. 37–41.
14. Revunova, E.G., 2013. “Randomization approach to the reconstruction of signals resulted from indi-rect measurements”. Proc. 4th Int. Conf. on Inductive Modelling (ICIM’2013), Kyiv, 2013, pp. 203–208.
15. Revunova, E.G., 2015. “Analytical study of the error components for the solution of discrete ill-posed problems using random projections”. Cybernetics and Systems Analysis, 51 (6), pp. 978–991. https://doi.org/10.1007/s10559-015-9791-0
16. REVUNOVA, E.G., 2017. “Averaging over matrices in solving discrete ill-posed problems on the basis of random projection”. Proc. CSIT’17, 2017, 1, pp. 473–478. https://doi.org/10.1109/STC-CSIT.2017.8098831
17. Revunova, E.G., 2017. “Solution of the Discrete ill-posed problem on the basis of singular value de-composition and random projection”. Advances in Intelligent Systems and Computing II. Cham: Springer, 2017, pp. 434–449.
18. Methods of Sustainable Solving the Problem of Transforming the Output of a Measurement System to Improve Measurement Precision, 2017. Report on NIR (2nd stage). International Research and Training Center for Information Technologies and Systems of the NAS and MES of Ukraine. no. 0116U002481, Kyiv, 26 p. (In Russian).
19. Marzetta, T., Tucci, G., Simon, S., 2011. “A random matrix-theoretic approach to handling singu-lar covariance estimates”. IEEE Trans. Information Theory, 2011, 57, 9, pp. 6256–6271. https://doi.org/10.1109/TIT.2011.2162175
20. Tucci, G.H., Vega, M.V., 2013. “A note on averages over Gaussian random matrix ensembles”. J. of Probability and Statistics, Article ID 941058, pp. 1–6.
21. Carasso, A.S., 1982. “Determining surface temperatures from interior observations”. SIAM J. Appl. Math. 1982, n 42, pp. 558–574. https://doi.org/10.1137/0142040
22. Phillips, D.L., 1962. “A technique for the numerical solution of integral equation of the first kind”. J. ACM, 1962, 9, pp. 84–97. https://doi.org/10.1145/321105.321114
23. Geman S., Bienenstock E., Doursat R., 1992. “Neural networks and the bias variance dilemma”. Neural Computation, 4 (1), pp. 1–58. https://doi.org/10.1162/neco.1992.4.1.1
24. Haykin, S.S., 1999. Neural networks: a comprehensive foundation. Prentice Hall, 1999. 842 p.
25. Hansen, P.C., 1994. Regularization Tools: A Matlab package for analysis and solution of discrete ill-posed problems. Numer. Algorithms, 1994, 6 (1), pp. 1–35. https://doi.org/10.1007/BF02149761

Received 31.01.2018