Control Systems and Computers

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

Upr. sist. maš., 2016, Issue 5 (265), pp. 10-24.

UDC 004.942+6232.454.862

E.G. Revunova, 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

Recovering Signals Obtained by Indirect Measurements Based on Truncated Singular Value Decomposition and Random Projection

Introduction. The solution of the ill-posed inverse problem by the least squares method is unstable with a large solution error. Tikhonov regularization, truncated singular value decomposition, and random projection were used to overcome the instability and to increase the accuracy of the solution.

Purpose. We provide an experimental comparison of the solution accuracy for the ill-posed inverse problem by Tikhonov regularization, truncated singular value decomposition, and random projection.

Methods. Tikhonov’s regularization imposes some restrictions on the solution, i.e. penalty on its Euclidean norm, that improves stability. Another approach approximates the original data by a model linear with respect to parameters. Selection of the optimal number of components of the linear model minimizes the error of solution and ensures stability. To obtain the optimal number of model components, model selection criteria are used.

Results and Conclusion. A comparative analysis of the accuracy shows that the truncated singular value decomposition method with the CRSVD criterion and the random projection method with the CRQ and AIC criteria ensured the accuracy at the level of Tikhonov regularization with the regularization parameter selected by the discrepancy method. The advantage of the random projection method is a lower computational complexity due to the dimensionality reduction.

Perspective. The directions for further research include the decreasing of the computational complexity and averaging over the realizations of the random matrix. 

Download full text! (In Russian)

Keywords: discrete ill-posed problem, regularization, truncated singular value decomposition, random projection.

1. Khmelevsky, V.K., Bondarenko, V.M., 1999. Electrical prospecting. M .: Nedra, 438 p. (In Russian).
2. Zabulonov, Yu.L., Korostil, Yu.M., Revunova, EG, 2006. Optimization of the solution of the inverse problem of the restoration of the density function of the distribution of surface contaminants. Sat scientific tr. IPME NAS of Ukraine “Modeling and Information Technologies”, pp. 77–83. (In Russian).
3. Rachkovskij, D.A., Revunova, E.G., 2009. Intelligent Gamma-Ray Data Processing for Environmental Monitoring. Intel. data analysis in global monitoring for environmental and security, pp. 124–145.
4. Revunova, E.G., Rachkovskij, D.A., 2009. Using randomized algorithms for solving discrete ill-posed problems. Int. J. Inform. Theor. and Appl., 16 (2), pp. 176–192.
5. 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
6. 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
7. 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
8. Revunova, E.G., Tyshchuk, A.V., 2015. 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 on July 20–24, pp. 43–47.
9. Revunova, EG, Tishchuk, AV, 2014. A criterion for choosing a model for solving discrete ill-posed problems based on singular decomposition. Upravlausie sistemy i masiny, 6, pp. 3–11. (In Russian).
10. Hansen, P.C., 1987. The truncated SVD as a method for regularization. BIT 27, pp. 534–553.
    https://doi.org/10.1007/BF01937276
11. Hansen, P.C., 1998. Rank-deficient and discrete ill-posed problems. Numerical Aspects of Linear Inversion, SIAM, Philadelphia, 247 p.
    https://doi.org/10.1137/1.9780898719697
12. Tikhonov, A.N., Arsenin, V.Y., 1977. Solution of ill-posed problems. V.H. Winston, Washington, 231 p.
13. Carasso, A.S., 1982. Determining surface temperatures from interior observations. SIAM J. Appl. Math., 42, pp. 558–574.
    https://doi.org/10.1137/0142040
14. Delves, L.M., Mohamed, J.L., 1985. Computational methods for integral equations. Cambridge: Cambridge Univ. Press, 388 p.
    https://doi.org/10.1017/CBO9780511569609
15. Phillips, D.L., 1962. A technique for the numerical solution of integral equation of the first kind J. ACM, 9, pp. 84–97.
    https://doi.org/10.1145/321105.321114
16. Hansen, P.C., 1994. Regularization Tools: A Matlab package for analysis and solution of discrete ill-posed problems. Numer. Algorithms, 1994, 6, pp. 1–35.
    https://doi.org/10.1007/BF02149761
17. Hansen, P.C., O’Leary, D.P., 1993. The use of L-curve in the regularization of discrete ill-posed problems. SIAM J. Sci. Comput. 14, pp. 1487–1503.
    https://doi.org/10.1137/0914086
18. Morozov, V.A., 1987. Regular methods for solving ill-posed problems. M .: Science, 239 p. (In Russian).
19. Golub, G.H., Heath, M., Wahba, G., 1979. Generalised cross-validation as a method for choosing a good ridge parameter. Technometrics, 21 (2), pp. 215–223.
    https://doi.org/10.1080/00401706.1979.10489751
20. Chan, T.F., Hansen, P.C., 1992. Some applications of the rank revealing QR factorization. SIAM J. Sci. Stat. Comput., 13, pp. 727–741.
    https://doi.org/10.1137/0913043
21. Chan, T.F., Hansen, P.C., 1994. Low-rank revealing QR factorizations. Numer Linear Algebra Appl., 1, pp. 33–44.
    https://doi.org/10.1002/nla.1680010105
22. Ivakhnenko, A.G., 1982. Inductive method of self-organization of complex systems.Kiev: Naukova dumka, 296 p. (In Russian).
23. Stepashko, V.S., 2003. Theoretical aspects of GMDH as a method of inductive decomposition modeling. Upravlausie sistemy i masiny, 2, pp. 31–38. (In Russian).
24. Belloni, A., Chernozhukov, V., 2013. Least Squares after Model Selection in High-Dimensional Sparse Models. Bernoulli.
    https://doi.org/10.3150/11-BEJ410
25. Mohsen, Bayati, Murat, A., 2013. Erdogdu, Andrea Montanari. Estimating LASSO Risk and Noise Level. NIPS 2013, Proc. of Advances in Neural Information Processing Syst., T.19, 2, pp. 512–547.
26. Fan, J., Guo, S., Hao, N., 2012. Variance estimation using refitted cross-validation in ultrahigh dimensional regression. J. of the Royal Stat. Society: Series B (Statistical Methodology), 74, pp. 1467–9868.
27. Fedorov, V.V., 1972. Theory of optimal experiments. New York: Acad. Press.
28. E.M. Kussul, T.N. Baidyk, V.V. Lukovich et al., 1993. Adaptive neural network classifier with multifloat input coding. Proc. Neuro-Nimes’93, pp. 209–216.
29. Lukovich, V.V., Goltsev, A.D., Rachkovskij, D.A., 1997. Neural Network Classifiers for Micromechanical Equipment Diagnostics and Micromechanical Product Quality Inspection. Proc. EUFIT’97, 1, pp. 534–536.
30. E.M. Kussul, L.M. Kasatkina, D.A. Rachkovskij et al., 1998. Application of random threshold neural networks for diagnostics of micro machine tool condition. Neural Networks Proc., 1998. IEEE World Congr. on Comp. Intel, 1, pp. 241–244.
    https://doi.org/10.1109/IJCNN.1998.682270
31. D.A. Rachkovskij, S.V. Slipchenko, E.M. Kussul et al., 2005. Properties of numeric codes for the scheme of random subspaces RSC. Cybernetics and Systems Analysis, 41(4), pp. 509–520.
    https://doi.org/10.1007/s10559-005-0086-8
32. Rachkovskij, D.A., Misuno, I.S., Slipchenko, S.V., 2012. Randomized projective methods for construction of binary sparse vector representations. Cybernetics and Systems Analysis, 48 (1), pp. 146–156.
    https://doi.org/10.1007/s10559-012-9384-0
33. V.I. Gritsenko, D.A. Rachkovskij, A.D. Goltsev et al., 2013. Neural distributed representation for intelligent information technologies and modeling of thinking. Cybernetics and Computer Engineering, 173, pp. 7–24.
34. Stewart, G.W., 1997. On the perturbation of pseudo-inverses, projections and linear least squares problems. SIAM Review, 19 (4), pp. 634–662.
    https://doi.org/10.1137/1019104

Received  09.04.2015