DOI:https://doi.org/10.15407/kvt192.03.005
Kibern. vyčisl. teh., 2018, Issue 3 (193), pp.
Revunova E.G., Ph.D. (Engineering),
Senior Researcher Department of Neural Information Processing Technologies
e-mail: egrevunova@gmail.com
Rachkovskij D.A., DSc. (Engineering),
Leading Researcher, Department of Neural Information Processing Technologies
e-mail: dar@infrm.kiev.ua
International Research and Training Center for Information Technologies
and Systems of the National Academy of Sciences of Ukraine
and Ministry of Education and Science of Ukraine,
Acad. Glushkova av., 40, Kiev, 03187, Ukraine
RANDOM PROJECTION AND TRUNCATED SVD FOR ESTIMATING DIRECTION OF ARRIVAL IN ANTENNA ARRAY
Introduction. The need to solve inverse problems arises in many areas of science and technology in connection with the recovery of the object signal based on the results of indirect remote measurements. In the case where the transformation matrix has a high conditional number, the sequence of its singular numbers falls to zero, and the output of the measuring system contains noise, the problem of estimating the input vector is called discrete ill-posed problem (DIP). It is known that the DIP solution using pseudoinverse of the input-output transformation matrix is unstable. To overcome the instability and to improve the accuracy of the solution, regularization methods are used.
Our approaches to ensuring the stability of the DIP solution (truncated singular decomposition (TSVD) and random projection (RP)) use the integer regularization parameter, which is the number of terms of the linear model. Regularization with an integer parameter makes it possible to provide a model close to the best in terms of the accuracy of the input vector recovery, and also to reduce the computational complexity by reducing the dimensionality of the problem.
The purpose of the article is to develop an approach to estimating the direction of arrival of signals in the antenna array using the DIP solution, to compare the results with the well-known MUSIC method, to reveal the advantages and disadvantages of the methods.
Results. Comparison of TSVD and MUSIC (implemented in real numbers) when working with correlated sources and five snapshots showed the advantage of TSVD in terms of the power of the useful signal Pratio by 2.2 times with the number of antenna elements K = 15 and by 4.7 times with K = 90. The advantage of TSVD in Pratio is by 3.7 times for K = 15 and by 4.2 times for K = 90. Comparison of RP and MUSIC (implemented in real numbers), when working with correlated sources and five snapshots, showed the advantage of RP in Pratio by 3 times at K = 15 and by 4.4 times at K = 90. When working with 100 snapshots, the advantage of RP in Pratio is by 3.8 times for K = 15 and by 4.2 times for K = 90.
Conclusions. The approach to determining the direction of arrival based on the l2-regularization methods provides a stable solution in the case of a small number of snapshots, high noise and correlated source signals. Methods of determining the direction of arrival based on l2-regularization, in contrast to l1-regularization, do not impose restrictions on the properties of the input-output transformation matrix, do not require a priori information on the number of signal sources, allow constructing efficient hardware implementations.
Keywords: Direction of arrival estimation, truncated singular value decomposition, random projection, MUSIC.
REFERENCES
1. 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
2. Tikhonov A., Arsenin V. Solution of ill-posed problems. Washington: V.H. Winston, 1977. 231 p.
3. Starkov V. Constructive methods of computational physics in interpretation problems. Kiev: Naukova Dumka, 2002. 263 p. (in Russian)
4. Hansen P.C. The truncated SVD as a method for regularization. BIT. 1987. Vol. 27, N 2. P. 534–553. https://doi.org/10.1007/BF01937276
5. Revunova E.G., Tishchuk A.V. Criterion for choosing a model for solving discrete ill-posed problems on the basis of a singular expansion. Control systems and machines. 2014. N 6. P. 3–11. (in Russian).
6. Revunova E.G., Tyshchuk A.V. A model selection criterion for solution of discrete ill-posed problems based on the singular value decomposition. Proc. IWIM’2015 (20–24th of July, 2015, Kyiv–Zhukyn) . Kyiv–Zhukyn. 2015. P.43–47.
7. 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
8. Revunova E.G. Study of error components for solution of the inverse problem using random projections. Mathematical Machines and Systems. 2010. N 4. P. 33–42 (in Russian).
9. Revunova E.G. Randomization approach to the reconstruction of signals resulted from indirect measurements. Proc. ICIM’13 (16-20th of September, 2013, Kyiv). Kyiv, 2013. P. 203–208.
10. 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
11. Revunova E.G. Averaging over matrices in solving discrete ill-posed problems on the basis of random projection. Proc. CSIT’17(05–08th of September, 2017, Lviv). Lviv, 2017. Vol. 1. P. 473–478. https://doi.org/10.1109/STC-CSIT.2017.8098831
12. 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.
13. Revunova E.G. Increasing the accuracy of the solution of discrete ill-posed problems by the method of random projections. Control systems and machines. 2018. N 1. P. 16–27. (in Ukrainian)
14. Revunova E.G., Tishchuk A.V., Desyaterik A.A. Criteria for choosing a model for solving discrete ill-posed problems based on SVD and QR decompositions. Inductive modeling of complex systems. 2015. N 7. P. 232–239. (in Russian).
15. 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.
16. 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
17. Schmidt R.O. Multiple emitter location and signal parameter estimation. IEEE Trans. Antennas Propagation. 1986. Vol. AP–34. P. 276–280. https://doi.org/10.1109/TAP.1986.1143830
18. Krim H., Viberg M. Two decades of array signal processing research: The parametric approach. IEEE Signal Processing Magazine. 1996. Vol. 13, N 4. P. 67–94. https://doi.org/10.1109/79.526899
19. Schmidt R.O. A signal subspace approach to multiple emitter location spectral estimation. PhD thesis. Stanford University, 1981. 201 p.
20. Bartlett M.S. Smoothing periodograms from time series with continuous spectra. Nature. 1948. Vol. 161. P. 686–687. https://doi.org/10.1038/161686a0
21. Malioutov D.M., Cetin M., Fisher J.W. III, Willsky A.S. Superresolution source localization through data-adaptive regularization. Proc. SAM’02 (6 august, 2002, Rosslyn, Virginia). Rosslyn, Virginia, 2002. P. 194–198. https://doi.org/10.1109/SAM.2002.1191027
22. Malioutov D., Cetin M., Willsky A.S. A sparse signal reconstruction perspective for source localization with sensor arrays. IEEE Transactions on Signal Processing. 2005. Vol. 53, N 8. P. 3010–3022. https://doi.org/10.1109/TSP.2005.850882
23. Panahi A. Viberg M. Fast lasso based DOA tracking. Proc. CAMSAP’11 (13–16th of December, 2011, San Juan, Puerto Rico) . San Juan, Puerto Rico, 2011. P. 397–400.
24. Panahi A. Viberg M. A novel method of DOA tracking by penalized least squares. Proc. CAMSAP’13 (15–18th of December, 2013, St. Martin, France). St. Martin, France, 2013. P. 61–64.
25. Golub G.H., Van Loan C.F. Matrix Computations. Baltimore: The Johns Hopkins University Press, 1996.
26. Ivakhnenko A., Stepashko V. Noise-immunity of modeling. Kiev: Naukova Dumka, 1985. (in Russian)
27. Stepashko V. Theoretical aspects of GMDH as a method of inductive modeling. Control systems and machines 2003. N 2. P. 31–38. (in Russian)
28. Stepashko V. Method of critical variances as analytical tool of theory of inductive modeling. Journal of Automation and Information Sciences. 2008. Vol. 40, N 3. P. 4–22. https://doi.org/10.1615/JAutomatInfScien.v40.i3.20
29. 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
30. 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.
31. 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
32. Zhang L., Wei Y. Randomized core reduction for discrete ill-posed problem. arXiv:1808.02654. 2018.
33. Misuno I.S., Rachkovskij D.A., Slipchenko S.V., Sokolov A.M. Searching for text information with the help of vector representations. Problems of Programming. 2005. N. 4. P. 50–59. (in Russian)
34. 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
35. Ferdowsi S., Voloshynovskiy S., Kostadinov D., Holotyak T. Fast content identification in highdimensional feature spaces using sparse ternary codes. Proc. WIFS’16 (4–7th of December, 2016, Abu Dhabi, UAE). Abu Dhabi, UAE, 2016. P. 1–6.
36. Rachkovskij D.A., Slipchenko S.V., Kussul E.M., Baidyk T. N. Properties of numeric codes for the scheme of random subspaces RSC. Cybernetics and Systems Analysis. 2005. Vol. 41, N. 4. P. 509–520. https://doi.org/10.1007/s10559-005-0086-8
37. Rachkovskij D.A., Slipchenko S.V., Kussul E.M., Baidyk T.N. Sparse binary distributed encoding of scalars. 2005. Journal of Automation and Information Sciences. Vol. 37, N 6. P. 12–23. https://doi.org/10.1615/J
Automat Inf Scien.v37.i6.20
38. Rachkovskij D.A., Slipchenko S.V., Misuno I.S., Kussul E.M., Baidyk T. N. Sparse binary distributed encoding of numeric vectors. Journal of Automation and Information Sciences. 2005. Vol. 37, N 11. P. 47–61. https://doi.org/10.1615/J
Automat Inf Scien.v37.i11.60
39. 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. https://doi.org/10.1016/j.procs.2016.07.404
40. Kleyko D., Osipov E., Senior A., Khan A.I., Sekercioglu Y.A. Holographic graph neuron: A bioinspired architecture for pattern processing. IEEE Trans. Neural Netw. Learn. Syst. 2017.Vol. 28, N 6. P. 1250–1262. https://doi.org/10.1109/TNNLS.2016.2535338
41. Kleyko D., Rahimi A., Rachkovskij D., Osipov E., Rabaey J. Classification and recall with binary hyperdimensional computing: Tradeoffs in choice of density and mapping characteristics. IEEE Trans. Neural Netw. Learn. Syst. 2018.
42. Kleyko D., Osipov E. On bidirectional transitions between localist and distributed representations: The case of common substrings search using vector symbolic architecture. Procedia Computer Science. 2014. Vol. 41. P. 104–113. https://doi.org/10.1016/j.procs.2014.11.091
43. Recchia G., Sahlgren M., Kanerva P., Jones M. Encoding sequential information in semantic space models: Comparing holographic reduced representation and random permutation. Comput. Intell. Neurosci. 2015. Vol. 2015. Art. no. 58. https://doi.org/10.1155/2015/986574
44. Räsänen O.J., Saarinen J.P. Sequence prediction with sparse distributed hyperdimensional coding applied to the analysis of mobile phone use patterns. IEEE Trans. Neural Netw. Learn. Syst. 2016. Vol. 27, N 9. P. 1878–1889. https://doi.org/10.1109/TNNLS.2015.2462721
45. Slipchenko S. V., Rachkovskij D.A. Analogical mapping using similarity of binary distributed representations. Int. J. Information Theories and Applications. 2009. Vol. 16, N 3. P. 269–290.
46. Kanerva P. Hyperdimensional computing: An introduction to computing in distributed representation with high-dimensional random vectors. Cogn. Comput. 2009. Vol. 1, N 2. P. 139–159. https://doi.org/10.1007/s12559-009-9009-8
47. Gallant S. I., Okaywe T.W. Representing objects, relations, and sequences. Neural Comput. 2013. Vol. 25, N 8. P. 2038–2078. https://doi.org/10.1162/NECO_a_00467
48. Gritsenko V.I., Rachkovskij D.A., Goltsev A.D., Lukovych V.V., Misuno I.S., Revunova E.G., Slipchenko S.V., Sokolov A.M., Talayev S.A. Neural distributed representation for intelligent information technologies and modeling of thinking. Kibernetika i vyčislitel’naâ tehnika. 2013. Vol. 173. P. 7–24. (in Russian).
49. Frolov A.A., Rachkovskij D.A., Husek D. On information characteristics of Willshaw-like auto-associative memory. Neural Network World. 2002. Vol. 12, No 2. P. 141–158.
50. Frolov A.A., Husek D., Rachkovskij D.A. Time of searching for similar binary vectors in associative memory. Cybernetics and Systems Analysis. 2006. Vol. 42, No. 5. P. 615–623. https://doi.org/10.1007/s10559-006-0098-z
51. Frady E. P., Kleyko D., Sommer F. T. A theory of sequence indexing and working memory in recurrent neural networks. Neural Comput. 2018. Vol. 30, N. 6. P. 1449–1513. https://doi.org/10.1162/neco_a_01084
52. Kussul N.N., Sokolov B.V., Zyelyk Y.I., Zelentsov V.A., Skakun S.V., Shelestov A.Y. Disaster risk assessment based on heterogeneous geospatial information. J. of Automation and Information Sciences. 2010. Vol. 42, N 12. P. 32–45. https://doi.org/10.1615/JAutomatInfScien.v42.i12.40
53. Kussul N., Shelestov A., Basarab R., Skakun S., Kussul O., Lavrenyuk M. Geospatial intelligence and data fusion techniques for sustainable development problems. Proc. ICTERI’15. 2015. P. 196–203.
54. Kussul N., Skakun S., Shelestov A., Kravchenko O., Kussul O. Crop classification in Ukraine using satellite optical and SAR images. International Journal Information Models and Analyses. 2013. Vol. 2, N 2. P. 118–122.
55. Kussul N., Lemoine G., Gallego F. J., Skakun S. V, Lavreniuk M., Shelestov A. Y. Parcel-based crop classification in Ukraine using Landsat-8 data and Sentinel-1A data. IEEE J. Sel. Topics Appl. Earth Observ. Remote Sens. 2016. Vol. 9, N 6. P. 2500–2508. https://doi.org/10.1109/JSTARS.2016.2560141
56. Lavreniuk M., Kussul N., Meretsky M., Lukin V., Abramov S., Rubel O. Impact of SAR data filtering on crop classification accuracy. Proc. UKRCON’17 (29th of May — 02th of June, 2017, Kyiv). Kyiv, 2017.2017. P. 912–917. https://doi.org/10.1109/UKRCON.2017.8100381
57. Kussul N., Lavreniuk M., Shelestov A., Skakun S. Crop inventory at regional scale in Ukraine: developing in season and end of season crop maps with multi-temporal optical and SAR satellite imagery. European Journal of Remote Sensing. 2018. Vol. 51, N 1. P. 627–636. https://doi.org/10.1080/22797254.2018.1454265
58. Moreira A., Prats-Iraola P., Younis M., Krieger G., Hajnsek I., Papathanassiou K. A tutorial on synthetic aperture radar. IEEE Geosci. Remote Sensing Mag. 2013. Vol. 1, N 1. P. 6–43. https://doi.org/10.1109/MGRS.2013.2248301
59. Ramakrishnan S., Demarcus V., Le Ny J., Patwari N., Gussy J. Synthetic aperture radar imaging using spectral estimation techniques. Technical Report. University of Michigan, 2002. 34 p.
Received 15.05.2018