Control Systems and Computers

https://doi.org/10.15407/csc.2021.05-06.025

Control Systems and Computers, 2021, Issue 5-6 (295-296), pp. 25-34.

UDK 004.22 + 004.032.26 

Revunova O.G., Doctor (Eng.),  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: egrevunova@gmail.com,

Tyshcuk O.V., Ph.D.student, International Research and Training Center for Information Technologies and Systems of the NAS and MES of Ukraine, Glushkov ave., 40, Kyiv, 03187, Ukraine,

Desiateryk О.О., Ph.D. (Ph.-Mat.), Taras Shevchenko National University of Kyiv, Glushkov ave., 4g, 03022, Kyiv, Ukraine

On the Generalization of the Random Projection Method for Problems of the Recovery of Object Signal Described by Models of Convolution Type

 Introduction. In technical systems, there is a common situation when transformation input-output is described by the integral equation of convolution type. This situation accurses if the object signal is recovered by the results of remote measurements. For example, in spectrometric tasks, for an image deblurring, etc. Matrices of the discrete representation for the output signal and the kernel of convolution are known. We need to find a matrix of the discrete representation of a signal of the object. The well known approach for solving this problem includes the next steps. First, the kernel matrix has to be represented as the Kroneker product. Second, the input-output transformation has to be presented with the usage of Kroneker product matrices. Third, the matrix of the discrete representation of the object has to be found.

The object signal matrix estimation obtained with the help of pseudo inverting of Kroneker decomposition matrices is unstable. The instability of the object signal estimation in the case of usage of Kroneker decomposition matrices is caused by their discrete ill posed matrix properties (condition number is big and the series of the singular numbers smoothly decrease to zero). To find solutions of discrete ill-posed problems we developed methods based on the random projection and the random projection with an averaging by the random matrices. These methods provide a stable solutions with a small computational complexity.

We consider the problem of object signals recovering in the systems where an input-output transformation is described by the integral equation of a convolution. To find a solution for these problems we need to build a generalization for two-dimensional signals case of the random projection method.

Purpose. To develop a stable method of the recovery of object signal for the case in which an input-output transformation is described by the integral equation of a convolution.

Results and conclusions. We developed the method of a stable recovery of object signal for the case in which an input-output transformation is described by the integral equation of a convolution. The stable estimation of the object signal is provided by Kroneker decomposition of the kernel matrix of convolution, computation of random projections for Kroneker factorization matrices and a selection of the optimal dimension of a projector matrix. The method is illustrated by its application in technical problems.

Perspectives. The direction of further research is the development of methods for the selection of the optimal dimension of the projector matrix.

 Download full text! (On English)

Keywords: signal recovery, random projections, integral convolution-type equation, spectrometry problems, optimal dimension of the projector matrix.

1. Revunova E.G., Rachkovskij D.A., 2009. “Using randomized algorithms for solving discrete ill-posed problems”. Journal Information Theories and Applications. Vol. 2, N. 16, pp.176–192.
2. Revunova E.G., Rachkovskij D.A., 2009. “Increasing the accuracy of solving the inverse problem using random projections”. International Conference Knowledge-Dialogue-Solution (KDS-2), pp. 93–98.
3. Durrant R.J., Kaban A., 2015. “Random projections as regularizers: learning a linear discriminant from fewer observations than dimensions”. Machine Learning, vol. 99, N 2, pp. 257-286.
   https://doi.org/10.1007/s10994-014-5466-8
4. Durrant R.J., Kaban A., 2010. “Compressed Fisher Linear Discriminant Analysis: Classification of Randomly Projected Data”. In Proceedings16th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD 2010).
   https://doi.org/10.1145/1835804.1835945
5. Xiang H., Zou J., 2013. “Regularization with randomized SVD for large-scale discrete inverse problems”. Inverse Problems. 29(8). https://doi.org/10.1088/0266-5611/29/8/085008
6. Xiang H., Zou J., 2015. “Randomized algorithms for large-scale inverse problems with general Tikhonov regularizations”. Inverse Problems. Vol. 31, N 8:085008, pp. 1-24. 
   https://doi.org/10.1088/0266-5611/31/8/085008
7. Wei Y., Xie P., Zhang L., 2016. “Tikhonov regularization and randomized GSVD”. SIAM J. Matrix Anal. Appl. Vol. 37, N 2, pp. 649-675.
   https://doi.org/10.1137/15M1030200
8. Hansen, P.,1998. “Rank-deficient and discrete ill-posed problems”. Numerical aspects of linear inversion. Philadelphia: SIAM. 247 p.
   https://doi.org/10.1137/1.9780898719697
9. Tikhonov A., Arsenin, V., 1977. Solution of ill-posed problems. Washington: V.H. Winston. 231 p.
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. Revunova E.G., Tishchuk A.V., 2014. “Criterion for choosing a model for solving discrete ill-posed problems on the basis of a singular decomposition”. Control systems and machines, 6, pp. 3–
12. 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 International Workshop on Inductive Modelling (IWIM’2015), Kyiv-Zhukyn, pp.43-47.
13. Revunova E.G., Tishchuk A.V., Desyaterik A.A., 2015. “Criteria for choosing a model for solving discrete ill-posed problems based on SVD and QR decompositions”. Inductive modeling of complex systems, 7, pp. 232–239.
14. Revunova E.G., 2010. “Study of error components for solution of the inverse problem using random projections”. Mathematical Machines and Systems. 4, pp. 33– (in Russian).
15. Rachkovskij D.A., Revunova E.G., 2012. “Randomized method for solving discrete ill-posed problems”. Cybernetics and Systems Analysis. Vol. 48, N. 4, pp. 621-635.
    https://doi.org/10.1007/s10559-012-9443-6
16. 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.
17. Revunova E.G., 2013. “Randomization approach to the reconstruction of signals resulted from indirect measurements”, Proc. 4th International Conference on Inductive Modelling (ICIM’2013), Kyiv, pp. 203-208.
18. 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. Vol. 52, N.4, pp.647-664.
    https://doi.org/10.1007/s10559-016-9868-4
19. 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. Vol. 51, N. 6, pp. 978-991.
    https://doi.org/10.1007/s10559-015-9791-0
20. Revunova E.G., 2017. “Averaging over matrices in solving discrete ill-posed problems on the basis of random projection”. Proc. CSIT’17. Vol. 1, pp. 473 – 478.
    https://doi.org/10.1109/STC-CSIT.2017.8098831
21. Revunova E.G., 2017. “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, pp. 434-449.
    https://doi.org/10.1007/978-3-319-70581-1_31
22. Hansen P.C., Nagy J.G., Leary D.P., 2008. Deblurring Images: Matrices, Spectra and Filtering. SIAM. https://doi.org/10.1117/1.2900557
23. Hansen P.C., 1994. “Regularization Tools: A Matlab package for analysis and solution of discrete ill-posed problems”. Numer. Algorithms. Vol. 6, N 1, pp. 1-35.
    https://doi.org/10.1007/BF02149761
24. Rachkovskij D.A, Revunova E.G., 2009. “Intelligent gamma-ray data processing for environmental monitoring”. In: Intelligent data analysis in global monitoring for environment and security. Kiev-Sofia: ITHEA, pp. 124–145.

Received 29.11.2021