Tekil değer ayrışımına dayalı ön koşullamanın sıkıştırmalı sınıflamaya etkisi

Öz

Dünyada depolanmakta ve işlenmekte olan veri miktarının hızla artması nedeniyle, veri saklama ve veriden bilgi üretimi alanlarında yenilikçi çözümlere her geçen gün daha fazla gereksinim duyulmaktadır; Sıkıştırmalı Örnekleme (SÖ) ve Sıkıştırmalı Sınıflama (SS) sırasıyla her iki alan için çözüm sunan iki yaklaşımdır. Veriden sınıflama yoluyla bilgi edinilmesinde SS kullanımı, sınıflamanın doğrudan SÖ ile elde edilen ölçüm uzayında gerçekleştirilebilmesini sağladığı için işlem yükünü düşürür. SÖ, Shannon örnekleme teoreminde gerek duyulan miktardan daha az sayıda örnekle kayıpsız bir geri çatımı yüksek olasılıkla mümkün kılmakta olup, kullanılan ölçüm matrisine Ön koşullama (ÖK) uygulanmasıyla geri çatım için gerekli örnek sayısı, dolayısıyla saklanması gereken veri miktarı daha da azaltılabilmektedir. SÖ’de ölçüm matrisi olarak, ölçüm matrisinden Tekil Değer Ayrışımı (TDA) ile türetilen matrisin kullanımının geri çatım başarımına katkısı literatürde salt deneysel olarak incelenmiştir. Bu çalışmada, literatürde bir ilk olarak, TDA’ya dayalı söz konusu yaklaşımın bir ÖK olduğu (TDA-ÖK) ve SÖ’de geri çatım için gerekli örnek sayısını düşüreceği analitik olarak gösterilmiş olup, bu bulguya ilişkin iki farklı Monte Carlo (MC) benzetimi gerçekleştirilmiştir. Benzetimlerle desteklenen TDA-ÖK başarımı deneysel olarak da iki farklı veri kümesi üzerinde ve üç farklı sınıflayıcı kullanılarak gerçekleştirilen SS uygulamaları ile değerlendirilerek, TDA-ÖK kullanımının SS başarımına etkisi yine literatürde ilk defa bu çalışmada incelenmiştir.

Anahtar Kelimeler

• Ön koşullama
• Tekil değer ayrışımı
• Sıkıştırmalı örnekleme
• Sıkıştırmalı sınıflama
• Wielandt eşitsizliği

Effect of singular value decomposition based preconditioning on compressive classification

Öz

Due to the rapid increase in the amount of data being stored and processed in the world, innovative solutions in the fields of data storage and data processing are increasingly needed; Compressive Sampling (CS) and Compressive Classification (CC) are two approaches that provide solutions for both areas, respectively. The use of CC to obtain information from the data through classification reduces the processing load as it enables the classification to be performed directly in the measurement domain obtained by CS. CS makes possible a lossless reconstruction with a high probability of less samples than the amount required by the Shannon sampling theorem, and by applying Preconditioning (PC) to the measurement matrix used, the amount of data required for reconstruction can be further reduced due to the number of samples required for reconstruction. The contribution of the use of the matrix derived from the measurement matrix by Singular Value Decomposition (SVD) as the measurement matrix in the CS, on the reconstruction performance has been studied only experimentally in the literature. In this study, as a first, it has been shown analytically that this approach based on SVD is a PC (SVD-PC) and will reduce the number of samples required for reconstruction in CS, meanwhile two different Monte Carlo (MC) simulations were carried out regarding to this finding. The SVD-PC performance supported by simulations is evaluated experimentally with SS applications performed on two different data sets and using three different classifiers, moreover the effect of SVD-PC on CC performance is investigated for the first time in the literature in this study.

Anahtar Kelimeler

• Preconditioning
• Singular value decomposition
• Compressive sampling
• Compressive classification
• Wielandt inequality

Kaynakça

1. 1. Pustokhina I.V., Pustokhin D.A., Gupta D., Khanna A., Shankar K., Nguyen G.N., An effective training scheme for deep neural network in edge computing enable internet of medical things (IoMT) systems, IEEE Access, 8(2020), 107112-107123, 2020.
2. 2. Younan M., Houssein E.H., Elhoseny M., Ali A.A., Challenges and recommended technologies for the industrial internet of things: A comprehensive review, Measurement, 151(2020) 107198, 1-16, 2020.
3. 3. Yıldırım G., Tatar Y., Uzak kullanıcı destekli bir IoT-WSN sanal laboratuvarı ve test platformu: FıratWSN, Journal of the Faculty of Engineering and Architecture of Gazi University, 34 (4), 1831-1846, 2019.
4. 4. Reinsel D., Gantz J., Rydning J., The digitization of the world from edge to core, IDC White Paper- #US44413318, 2018.
5. 5. Calderbank R. ve Jafarpour S., Finding Needles in Compressed Haystacks, Compressed Sensing: Theory and Applications, Eldar Y.C., Kutyniok G., Cambridge University Press, Cambridge, 439-484, 2012.
6. 6. Calderbank R., Jafarpour S., Schapire R., Compressed learning: Universal sparse dimensionality reduction and learning in the measurement domain, Teknik Rapor, Princeton University, 2009.
7. 7. Reboredo H., Renna F., Calderbank R., Rodrigues M.R.D., Projections designs for compressive classification, 2013 IEEE Global Conference on Signal and Information Processing, Austin, 1029-1032, 3-5 Aralık, 2013.
8. 8. Davenport M.A., Boufounos P.T., Wakin M.B., Baraniuk R.G., Signal processing with compressive measurements, IEEE Journal of Selected Topics in Signal Processing, 4(2), 445-460, 2010.

9. 9. Wimalajeewa T., Chen H., Varshney P.K., Performance limits of compressive sensing-based signal classification, IEEE Transactions on Signal Processing, 60(6), 2758-2770, 2012.
10. 10. Shannon C.E., Communication in the presence of noise, Proc. IEEE, 86(2), 447-457, 1998.
11. 11. Davenport M.A., Duarte M.F., Eldar Y.C., Kutyniok G., Introduction to Compressed Sensing, Compressed Sensing: Theory and Applications, Eldar Y.C. ve Kutyniok G., Cambridge Uni. Press, Cambridge, 1-64, 2012.
12. 12. Candès E., Romberg J., Tao T., Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information. IEEE Trans Inform Theory, 52(2), 489 - 509, 2006.
13. 13. Donoho D., Compressed sensing, IEEE Trans Inform Theory, 52(4), 1289 - 1306, 2006.
14. 14. Baraniuk R., Compressive sensing, IEEE Signal Proc Mag, 24(4), 118 - 120, 124, 2007.
15. 15. Schmidt R., Zur theorie der linearen und nichtlinearen integralgleichungen, Math. Ann., 63, 433-476, 1907.
16. 16. Holtz O.V., Compressive Sensing: A Paradigm Shift in Signal Processing. ArXiv. https://arxiv.org/abs/0812.3137. Yayın tarihi Aralık16, 2008. Erişim tarihi Ağustos 2, 2020.
17. 17. Pati Y.C., Rezaifar R., Krishnaprasad P.S., Orthogonal matching pursuit: Recursive function approximation with applications to wavelet decomposition, 27th Annual Asilomar Conference on Signals Systems and Computers, California, 1-3 Kasım, 1993.
18. 18. Atar Y., Ersoy P., Özyılmaz Y., Hybrid data compression and optical cryptography with orthogonal matching pursuit, Journal of the Faculty of Engineering and Architecture of Gazi University, 32 (1), 131-139, 2017.
19. 19. Zhao J., Bai X., Bi S., Tao R., Coherence-based analysis of modified orthogonal matching pursuit using sensing dictionary, IET Signal Processing, 9(3), 218-225, 2015.
20. 20. Schnass K., Vandergheynst P., Dictionary preconditioning for greedy algorithms, IEEE Transactions on Signal Processing, 56(5), 1994-2002, 2008.
21. 21. Tsiligianni E., Kondi L.P., Katsaggelos A.K., Preconditioning for underdetermined linear systems with sparse solutions, IEEE Signal Processing Letters, 22(9), 1239-1243, 2015.
22. 22. Chen Y., Peng J., Yue S., Preconditioning for orthogonal matching pursuit with noisy and random measurements: The Gaussian case circuits, Systems, and Signal Processing, 37, 4109-4127, 2018.
23. 23. Zhang C., An orthogonal matching pursuit algorithm based on singular value decomposition, Circuits, Systems, and Signal Processing, 39, 492-501, 2020.
24. 24. Olshausen B., Field D., Emergence of simple-cell receptive field properties by learning a sparse code for natural images, Nature, 381, 607-609, 1996.
25. 25. Elad M., Sparse and Redundant Representations: From Theory to Applications in Signal and Image Processing, Springer, New York, A.B.D., 2010.
26. 26. Candes E.J., Wakin M.B., An introduction to compressive sampling, IEEE Signal Processing Magazine, 25(2), 21-30, 2008.
27. 27. Mallat S.G, Zhang Z., Matching pursuits with time-frequency dictionaries, IEEE Transactions On Signal Processing, 41(12), 3397-3415, 1993.
28. 28. Tropp J.A., On the conditioning of random subdictionaries, Applied and Computational Harmonic Analysis, 25(1), 1-24, 2008.
29. 29. Chen Y., Peng J., Influences of preconditioning on the mutual coherence and the restricted isometry property of Gaussian/Bernoulli measurement matrices, Linear and Multilinear Algebra, 64(9), 1750-1759, 2016.
30. 30. Strang G., Introduction to Linear Algebra, Wellesley-Cambridge Press, 5. Basım, 2016.
31. 31. Yan Z., A Unified version of Cauchy-Schwarz and Wielandt inequalities, Linear Algebra and Its Applications, 428(8), 2079-2084, 2008.
32. 32. Lin M., Sinnamon G., The generalized wielandt inequality in inner product spaces, Eurasian Mathematical Journal, 3(1), 72-85, 2012.
33. 33. Pope G., Compressive Sensing a Summary of Reconstruction Algorithms, Yüsek Lisans Tezi, ETH Zürich, Department of Computer Science, Zürich, 2009.
34. 34. Pedregosa F., Varoquaux G., Gramfort A., Michel V., Thirion B., Grisel O., Blondel M., Prettenhofer P., Weiss R., Dubourg V., Vanderplas J., Passos A., Cournapeau D., Brucher M., Perrot M., Duchesnay E., Scikit-learn: Machine learning in Python, The Journal of Machine Learning Research, 12, 2825-2830, 2011.
35. 35. Cover T., Hart P., Nearest neighbor pattern classification, IEEE Trans. Inf. Theory, 13(1), 21-27, 1967.
36. 36. Brieman L., Random Forest, Machine Learning, 45, 5-32, 2001.
37. 37. Vapnik V.N., The Nature of Statistical Learning Theory, Springer-Verlag, New York, A.B.D., 1995.
38. 38. LeCun Y., Bottou L., Bengio Y., Haffner P., Gradient-based learning applied to document recognition, Proc. IEEE, 86(11), 2278-2324, 1998.
39. 39. Luo G., A review of automatic selection methods for machine learning algorithms and hyper-parameter values, Netw Model Anal Health Inform Bioinforma, 5, 18, 2016.
40. 40. Yang A., Kuryloski P., Bajcsy R., WARD: A Wearable Action Recognition Database, CHI Conference on Human Factors in Computing Systems, Boston, MA, ABD, 4-9 Nisan, 2009.
41. 41. Xiao L., Li R., Luo J., Xiao Z., Energy-efficient recognition of human activity in body sensor networks via compressed classification, International Journal of Distributed Sensor Networks, 12(12), 1-8, 2016.
42. 42. Wu J., Xiong H., Chen J., Adapting the right measures for K-means clustering. In Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD '09), Paris-France, 877–886, 28 Haziran-1 Temmuz, 2009.