Cybernetics And Systems Analysis logo
Editorial Board Announcements Abstracts Authors Archive
Cybernetics And Systems Analysis
International Theoretical Science Journal
Volume 58 >>> № 5 SEPTEMBER — OCTOBER 2022
-->

UDC 004.22 + 004.93'11
O.V. Tyshchuk1, O.O. Desiateryk2, O.E. Volkov3,
E.G. Revunova4, D.A. Rachkovskij5


1 Roku Inc., Kyiv, Ukraine

 avtyshcuk@gmail.com

2 Taras Shevchenko National University of Kyiv, Kyiv, Ukraine

 sasha.desyaterik@gmail.com

3 International Research and Training Center
for Information Technologies and Systems
of the NAS of Ukraine and the MES of Ukraine,
Kyiv, Ukraine

 alexvolk@ukr.net

4 International Research and Training Center for Information Technologies and Systems
of the NAS of Ukraine and the MES of Ukraine, Kyiv, Ukraine

 egrevunova@gmail.com

5 International Research and Training Center for Information Technologies and Systems of the NAS of Ukraine and the MES of Ukraine, Kyiv, Ukraine, and Lulea Technological University, Sweden

 dar@infrm.kiev.ua

A LINEAR SYSTEM OUTPUT TRANSFORMATION
FOR SPARSE APPROXIMATION

Abstract. We propose an approach that provides a stable transformation of the output of a linear system into the output of a system with a desired basis. The matrix of basis functions of a linear system has a large condition number, and the series of its singular numbers gradually decreases to zero. Two types of methods for stable output transformation are developed using approximation of matrices based on the truncated Singular Value Decomposition and on the Random Projection with different types of random matrices. It is shown that the use of the output transformation as a preprocessing makes it possible to increase the accuracy of solving sparse approximation problems. An example of using the method in the problem of determining the activity of weak radiation sources is considered.

Keywords: sparse approximation, discrete ill-posed problem, random projection, singular value decomposition.


FULL TEXT

REFERENCES

  1. Pytiev Yu.P. Mathematical methods of interpretation of the experiment. Moscow: Vysshaya shkola, 1989. 351 p. (In Russian).

  2. Pytiev Yu.P. Measuring and computing converter as a multipurpose measuring instrument. Measurements World. 2013. N 6 (148). P. 3–8. (In Russian). URL: https://books.google.com.ua .

  3. Revunova E.G. Stable transformation of the output of a linear system into the output of a system with a given basis. Control Systems and Computers. 2013. N 6. P. 28–35. URL: http://nbuv.gov.ua/UJRN/USM_2013_6_6. (In Russian).

  4. Rachkovskij D.A., Revunova E.G. A 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 .

  5. 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 .

  6. 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.

  7. Revunova E.G. Increasing the accuracy of solving discrete ill-posed problems by the random projection method. Cybernetics and Systems Analysis. 2018. Vol. 54, N 5. P. 842–852. https://doi.org/10.1007/s10559-018-0086-0 .

  8. Revunova E.G. Averaging over matrices in solving discrete ill-posed problems on the basis of random projection. 12th International Scientific and Technical Conference on Computer Sciences and Information Technologies (CSIT’17) (5–8 September 2017, Lviv, Ukraine). Lviv, 2017. Vol. 1. P. 473–478.

  9. Revunova O.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.

  10. 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. AISC book series, Vol. 689. Cham: Springer, 2018. P. 434–449.

  11. Revunova E.G., Rachkovskij D.A. Stable transformation of a linear system output to the output of system with a given basis by random projections. Proc. 5th International Workshop on Inductive Modelling (IWIM’2012) (8–14 July 2012, Kyiv–Zhukyn, Ukraine). Kyiv–Zhukyn, 2012. P. 37–41.

  12. Revunova E.G. Finding the minimum error using model selection criteria for the problem of transformation of a linear system output to the output of system with a given basis. Control Systems and Computers. 2013. N 2. P. 28–32. (In Russian).

  13. Elad M. Sparse and redundant representations: from theory to applications in signal and image processing. New York: Springer, 2010. 397 p.

  14. Gribonval R., Figueras i Ventura R.M., Vandergheynst P. A simple test to check the optimality of a sparse signal approximation. Signal Processing. 2006. Vol. 86, N 3. P. 496–510.

  15. Mallat S.G., Zhang Z. Matching pursuits with time-frequency dictionaries. IEEE Transactions on Signal Processing. 1993. Vol. 41, N 12. P. 3397–3415.

  16. Volkov O., Komar M., Volosheniuk D. Devising an image processing method for transport infrastructure monitoring systems. Eastern-European Journal of Enterprise Technologies. 2021. Vol. 4, N 2 (112). P. 18–25. https://doi.org/10.15587/1729-4061.2021.239084.

  17. Gritsenko V., Volkov O., Komar M., Voloshenyuk D. Integral adaptive autopilot for an unmanned aerial vehicle. Aviation. 2018. Vol. 22, N. 4. P. 129–135. https://doi.org/10.3846/aviation.2018.6413.

  18. Volkov O., Komar M., Synytsya K., Volosheniuk D. The UAV simulation complex for operator training. Proc. 13th International Conference on e-Learning (17–19 July 2019, Porto, Portugal). Porto, 2019. P. 313–316.

  19. Fainzilberg L.S. Restoration of a standard sample of cyclic waveforms with the use of the Hausdorff metric in a phase space. Cybernetics and Systems Analysis. 2003. Vol. 39, N 3. P. 338–344. https://doi.org/10.1023/A:1025749208571.

  20. Fainzilberg L.S. New approaches to the analysis and interpretation of the shape of cyclic signals. Cybernetics and Systems Analysis. 2020. Vol. 56, N 4. P. 665–674. https://doi.org/10.1007/ s10559-020-00283-0.

  21. Rachkovskij D.A. Real-valued embeddings and sketches for fast distance and similarity estimation. Cybernetics and Systems Analysis. 2016. Vol. 52, N 6. P. 967–988. https://doi.org/10.1007/s10559-016-9899-x .

  22. Rachkovskij D.A. Formation of similarity-reflecting binary vectors with random binary projections. Cybernetics and Systems Analysis. 2015. Vol. 51, N 2. P. 313–323. https://doi.org/10.1007/s10559-015-9723-z .

  23. Rachkovskij D.A. Binary vectors for fast distance and similarity estimation. Cybernetics and Systems Analysis. 2017. Vol. 53, N 1. P. 138–156. https://doi.org/10.1007/s10559-017-9914-x .

  24. Kussul E.M., Rachkovskij D.A., Wunsch D.C. The random subspace coarse coding scheme for real-valued vectors. Proc. International Joint Conference on Neural Networks IJCNN’99. (10–16 July 1999, Washington, DC, USA). Washington, DC, 1999. P. 450–455.

  25. Kussul E.M., Kasatkina L.M., Rachkovskij D.A., Wunsch D.C. Application of random threshold neural networks fordiagnostics of micro machine tool condition. Proc. IEEE International Joint Conference on Neural Networks. IEEE World Congress on Computational Intelligence (IJCNN’98) (4–9 May 1998, Anchorage, AK, USA). Anchorage, AK, 1998. Vol. 1. P. 241–244.

  26. Kleyko D., Osipov E., Rachkovskij D.A. Modification of holographic graph neuron using sparse distributed representations. Procedia Computer Science. 2016. Vol. 88. P. 39–45.

  27. Kleyko D., Rachkovskij D.A., Osipov E., Rahimi A. A survey on hyperdimensional computing aka vector symbolic architectures, part I: models and data transformations. ACM Computing Surveys. 2022. https://doi.org/10.1145/3538531.

  28. Kleyko D., Rachkovskij D.A., Osipov E., Rahimi A. A survey on hyperdimensional computing aka vector symbolic architectures, part II: applications, cognitive models, and challenges. ACM Computing Surveys. 2022.




Editorial Board Announcements Abstracts Authors Archive
about scope office editorial board instructions for authors subscriptions contacts
© 2022 Kibernetika.org. All rights reserved.