Katlıdizeylerin çokdeğişkenliliği yükseltilmiş çarpımlar üçköşegencil gösterilim yoluyla ayrıştırımı: Kavramcıl taban ve uygulayışlar

Abstract

Bilimsel araştırımlardaki sorunların yapısında bulunan çok değişkenlilik ve çok boyutluluk nedeniyle bilimsel yazında sorunların çoğu uzbilimcil olarak çokyönlü dizi ile gösterilir. Günümüzde veri bilimi çok yaygın olarak çalışılan bir konu olup, özellikle bu alanda çokyönlü dizi ile çok sık karşılaşmaktayız. Verilerin anlamlandırılması, sınıflandırılması ve uzbilimcil olarak modellenmesi vb. sorunlar, dizeylerde olduğu gibi çokyönlü dizilerde de ayrıştırım ve çarpanlarına ayırma konularını ilgi odağı haline getirmiştir. Bilimsel yazında A_{i_1,i_2,...,i_m} simgeleyişi ile verilen çokyönlü diziler, öğeleri, birden çok sayıda da olabilen, altsırasayılarla tanımlanan, öğeler topluluğu olarak bilinir. Her bir altsırasayı ayrı bir yön tanımlar ve bu yönlerin birbirine dik doğrularla betimlendiği düşünülür. Bu bağlamda, sıradan doğrucul cebirin yöneyleri (vektörleri) `bir yönlü`, dizeyleri (matrisleri) ise `iki yönlü` dizilere karşılık gelir. Dizeylerde dönüşüm niteliği de vardır ve yataysıralar dizeyin tanım uzayında bir takım doğrultulara izdüşüm gercekleştiren öğelerdir. Bunların her birinin tanımladığı izdüşüm bileşeni dizeyin düşeysıralarının nasıl doğrucul birleştirim oluşturacağını eşsiz biçimde belirler. Bu doğrucul birleştirim ise dönüşüm sonrası, dizeyin değer uzayında, bir doğrultu tanımlar. Bu durumda, dizey öğelerinin birinci altsırasayısı değer uzayındaki doğrultu ile ilintilendirilebilirken, ikinci altsırasayı tanım uzayından dönüşümü sağlayan öğe olarak düşünülebilir. Bilimsel yazında çok yeni olarak geliştirilen katlı dizey kavramı ise doğrucul cebirin dizey özelliklerinin çokyönlü dizilere aktarılmasını sağlamak ve her yöndeki ayrıştırımın hesaplama maliyetini azaltmak amacıyla geliştirilmiştir. A_{i_1,i_2,...,i_m; j_1,j_2,...,j_n} olarak tanımlanan bir katlıdizey, sıradan doğrucul cebirdeki dizeyin kavramcıl genişletimi olarak düşünülebilir. Böyle bir dizeyin öğelerindeki altsırasayılardan bir kesimi bir çokyönlü diziler tanım uzayıyla ilintilendirilirken; kalan kesimi çokyönlü diziler değer uzayıyla ilintilendirilir. Bu savda geliştirilen yöntemin temelinde, dizey ayrıştırım yöntemi olarak Çokdeğişkenliliği Yükseltilmiş Çarpımlar Üçköşegencil Dizey Gösterilimi (ÇYÇÜDG) bulunmaktadır. Bu yöntem, çekirdeğinde Tekil Değer Ayrıştırımından (TDA) değişik olarak üçköşegencil bir dizey bulunduran, sağ ve sol dizey düşey sıralarında ise dikgen sağ ve sol destek yöneylerinin bulunduğu TDA benzeri bir yontemdir. Bu yöntem, amaç dizeyine Çokdeğişkenliliği Yükseltilmiş Çarpımlar Gösteriliminin (ÇYÇG) özyinelemeli olarak uygulanması sonucu elde edilir. Bu nedenle özyinelemeli bir ayrıştırım yöntemidir. ÇYÇG uygulayışının her adımında üç tane dış çarpım elde edilir. Üçköşegencillik, bu dış çarpımların katkılarını anlatan katsayılardan elde edilir. Temelde bulunan bu yöntemler, istatistiksel kökenli yöntemlerdir. %Bu savda, Çokdeğişkenliliği Yükseltilmiş Çarpımlar Üçköşegencil Dizey Gösterilimi (ÇYÇÜDG) temel alınarak, böl-yönet usbilimi ile çalışan, katlıdizey kavramını odağa alan Çokdeğişkenliliği Yükseltilmiş Çarpımlar Üçköşegencil Katlıdizey Gösterilimi (ÇYÇÜKG) yöntemi geliştirilmiştir. Bu yöntem çokyönlü diziler için yeni ve özgün bir ayrıştırım yöntemi olup, katlıdizey yapısı nedeniyle ikili ayrıştırımdır (ing: binary decomposition). Özyinelemeli (ing: recursive) bir yöntem olan ÇYÇÜKG, ikili ayrıştırım yapısı sayesinde bilimsel yazındaki çoğu yöntemin evriğine her yöndeki ayrıştırımın zorluğundan kaçınmaktadır. Katlı dizey kullanımı, destek yöneyleri kullanımı yerine destek katlıyöney kullanımını gerektirmektedir. Bu nedenle elde edilen ayrıştırım çekirdeğinde katlıyöney dış çarpımlarından gelen katkıyı belirten katsayılar yer almaktadır. Bilimsel yazındaki çoğu ayrıştırım yöntemi (TDA, Tucker, NTF gibi), yanılgı enküçükleme usbilimine dayalı çarpan bulan yineleyişli yöntemlerdir. Bu enküçükleme işlemi gerçekleştirilirken Alternating Least Squares (ALS) yöntemi kullanılmaktadır. Bu yöntem yapısında dizey evriği alma işlemi bulundurmaktadır. ÇYÇÜKG bu yöntemlerden değişik olarak istatistiksel tabanlı, dizey evriği alma işlemi içermeyen, özyinelemeli bir yöntemdir. Yöntemin doğası gereği, iki tür esneklik ortaya çıkmaktadır. Birincisi başlangıç destek katlıyöneylerinin seçimi, ikincisi ise ikili ayrıştırım yapısının seçimi ile ilgilidir. ÇYÇÜKG yönteminde başlangıç destek katlıyöneyleri özelsizde asıl veriden ortalama ile üretilmektedir. Bu biçimdeki seçimler yöntemin etkinliğini artırmaktadır. Bu savda bu esneklikler bağlamında uygulayışlar gerçekleştirilmiş olup, gözlem sonuçları verilmiştir. Ayrıca bu savda, destek yöneyleri kullanılarak geliştirilmiş olan ÇYÇÜDG yönteminde dizey destekleri kullanımı gündeme getirilmiş ve elde edilen bu yeni yöntem Çokdeğişkenliliği Yükseltilmiş Çarpımlar Öbekçil Üçköşegencil Dizey Gösterilimi (ÇYÇÖÜDG) olarak genelleştirilmiştir. Desteklerin dizey olarak ele alınması çekirdek dizeyinde öbekçil üçköşegencil yapıları ortaya çıkarmıştır. Ayrıca destek yöneylerinin birbirine dikliği yerine dizeycil dikgenlik kavramı gündeme getirilmiştir. Elde edilen bu yeni yöntem ile ilgili sınayışlar gerçekleştirilmiş ve sonuçlar paylaşılmıştır. Bu yöntemin yanısıra, ÇYÇÜDG yöntemi temel alınarak yöneyler için de yeni bir ayrıştırım geliştirilmiştir. ÇYÇG'nin özyineli olarak yöneye uygulanması ile elde edilen bu yeni ayrıştırım, Çokdeğişkenliliği Yükseltilmiş Çarpı mlar Üçköşegencil Yöney Gösterilimi (ÇYÇÜYG) olarak adlandırılmıştır. Bu yöney ayrıştırımında ikili Kronecker çarpımlarından yararlanılmış ve bu amaçla, katlılaştırım ve katsızlaştırım eylemlerinden yararlanılmıştır. Geliştirilen bu yeni ayrıştırım için de sayısal sonuçlar verilmiştir. Bu savda kavramcıl tabanın yanısıra, ÇYÇÜKG yönteminin bir çok farklı alanda işlerliğini göstermek amacı ile uygulayışlar gerçekleştirilmiştir. Özellikle sav bağlamında canlandırım verilerinin işlenmesinde ve yeniden yapılandırımında (ing: video processsing), aşkın izgecil verilerin sıkıştırılmasında (ing: hyperspectral data compression) ve uzbilimcil yaklaştırımda uygulamalar verilmiştir. Veri sıkıştırma sorunları için, yöntemin sıkıştırma oranı belirlenmiş olup genel bir bağıntı elde edilmiştir. Ayrıca yöntemin geçerliliğini göstermek amacı ile, bilimsel yazında yaygın olarak kullanılan Tucker ve CP yöntemleri, ÇYÇÜKG ile karşılaştırılmış olup, bu karşılaştırımlar için, çeşitli gerçek kimya verileri ele alınmıştır. Bu sav çalışması kapsamında özgün ayrıştırım yöntemleri geliştirilmiş olup, etki ettirilen veriye veya soruna bağlı olarak etkinlikleri olabildiğince arıntılı olarak verilmeye çabalanmıştır. Bu savda geliştirilen yöntemlerin uygulama alanları geniş olup sav sonrasında da farklı alanlarda kullanımı irdelenecektir.

Multivariance, multidimensionality and multiway concepts have been at the one of attraction foci since many scientific modellings need to deal with these issues. Decomposition and factorization of multiway arrays (tensors) are pretty much concerned by many scientists and engineers nowadays. In many scientific areas such as signal processing, chemometry, neuroscience, data mining, etc., problems are ended up with data and these data generally mathematically defines matrices or multiway/multidimensional arrays (tensors). General component of a multiway array such as $/boldsymbol{/mathcal{A}}/in/mathbb{R}^{I_1/times I_2 /times/cdots/times I_N}$ is symbolized as A_{i_1,i_2,...,i_n} in the literature. Each subscript of A_{i_1,i_2,...,i_n} defines a way (i.e. direction) and these ways are mutually orthogonal. Within this framework the ordinary linear algebraic entities, vectors and matrices can be considered one way and two way arrays, respectively. Due to the difficulty of decomposing multiway arrays having more than two ways on each direction separately, adapting the properties of ordinary matrix algebra to the multiway arrays is important. In order to overcome this difficulty Demiralp proposed new algebraic concepts defined as `folded matrix (Folmat)` and `folded vectors (Folvec)`.Folmat which is a folded form of an ordinary algebraic matrix is shown as A_{i_1,i_2,...,i_m;j_1,j_2,...,j_n}. In ordinary linear algebra a matrix can be given by its general term in the form like a_{i,j} where i and j are `row locator` and `column locator` respectively. Analogously, the m-tuple (i) and the n-tuple (j) can be considered the row and column locators of the folmat. Semicolon separates indices of multiway array into two groups. Left side indices are correlated to somehow row space and the right-side indices are somehow correlated with the column space. Folded vectors (folvecs) are special form of the folmats. If we specifically choose n = 0 in the above definitions then we obtain no grid for columns. In other words, the folmat under consideration becomes an entity which has just a single folded column. We call these entities `folvec`s within an analogy to the matrix-vector discrimination in ordinary linear algebra.The most important property of a folmat is its construction style enabling the analogy between multiway arrays and matrices for the matrix properties in ordinary linear algebra. Within this framework we use folmats and folvecs to get rid of very high computational complexity of each-way-separation-style decomposition of multiway arrays. Semicolon in the folmat notation enables binary decomposition by separating indices into two groups. In this thesis we formed a new decomposition method for multiway arrays which is called `Tridiagonal Folmat Enhanced Multivariance Products Representation (TFEMPR)`. TFEMPR method can be considered as higher order analogue of matrix decomposition since it focuses on folmats and folvecs which are in fact high order (way) arrays counterparts of ordinary linear algebraic matrices and vectors. Unlike the decomposition methods in the literature, TFEMPR is a statistics-rooted method. It has been developed for decomposing multidimensional arrays with the philosophy behind Tridiagonal Matrix Enhanced Multivariance Products Representation (TMEMPR). TMEMPR method decomposes a matrix having finitely or infinitely many rows and columns to a sum of outer products whose coefficients can be gathered into a core matrix which is tridiagonal. Tridiagonality is provided by applying Enhanced Multivariance Products Representation (EMPR) recursively to a matrix. EMPR works with the philosophy of representing a multiway array in terms of less variate arrays by using support vectors such that EMPR representation of a matrix is given via sum of four terms; constant, univariate terms (terms through column and row) and bivariate term. EMPR produces four additive terms representations for such entities and the additive truncation approximations may not be considered sufficiently efficient numerical agents. This has been urged Demiralp and his group to produce more-than-four-terms representations based on EMPR on multiway arrays. This could have been accomplished by generating a set of left and right support functions (or vectors) and then to build a Singular Value Decomposition (SVD) like formula. The birth of Tridiagonal Matrix Enhanced Multivariance Products Representation (TMEMPR) has been settled on this idea. Many decomposition schemes standing in the scientific literature, like Tucker, SVD, NMF, are based on the philosophy of expressing a matrix as the product of certain factors or sum of certain products in such a way that the decomposition components reveal many important features of the matrix. To deal with practically meaningful objects in many problems of this category input matrix is composed of nonnegative elements and the basic goal is to get matrix factors of nonnegative elements. Hence this type of decompositions are called `Nonnegative Matrix Factorization`. The matrix factor of the binary product is generally evaluated by minimizing the Frobenius norm of the error matrix. The `Alternating Least Squares Method (ALS) is generally used in this optimisation procedure. A matrix inversion procedure which has an evaluating cost increasing with the growth of the data dimension is needed in these evaluations. These are iterative methods even for the columnwise and rowwise evaluation of left and right factors of the binary product. There is almost no possibility of noniterative recursions. In contrast to these methods, TFEMPR components can be evaluated recursively starting from the lowest multivariance in ascending multivariance direction without any iterations and the truncation approximants can be efficiently used. On the other hand TFEMPR components need not be (in fact can not be due to orthogonality) composed of all nonnegatived elements. At least some of which may contain opposite signed elements. This is a flexibility and together with the recursive nature tremendously decreases the computational complexity. The price is paid by a need to take more TFEMPR additive terms to get a prescribed precision in some cases even though many circumstances allow us to use low level truncations. The support components are very good elements to conrol the truncation qualities.Structure of TFEMPR method has two flexibilities. One of them is decomposition type. The employment of binary decomposition in other words folmat brings the question of how to choose left and right grids. This is called as `decomposition type` in this thesis. There are options for type as much as binary combination of directions (ways). So the more direction the more choice you have to examine. Implementations have been done on this issue. According to the implementations presented here, the results indicate that the nature of problem impresses the choice of type. Digital video is a good instance for this issue due to the choice of i,j;k which decomposes frames and frame locations. The other flexibility is the choice of support folvecs at the beginning step of recursion. We have used four different supports in this thesis, but these are not optimized supports. But we know that kernel matrix factor's diagonal dominancy in TFEMPR can be controlled via appropriate definitions of the support entities. The use of the target folmat, its transpose, its multiplicatively symmetrized counterparts as scaling matrix factors facilitates the obtention of higher diagonal dominancy as our implementations imply. In this thesis, also a new Tridiagonal Matrix Enhanced Multivariance Products Representation (TMEMPR) which uses not Cartesian vectors but matrices as the support entities is designed and named as Block Tridiagonal Matrix Enhanced Multivariance Products Representation (BTMEMPR). What we obtain after the construction of the representation has been a singular value decomposition like structure where the core matrix becomes a block tridiagonal matrix in contrast to the diagonal and tridiagonal matrix structures of the Singular Value Decomposition (SVD) of matrices and Tridiagonal Matrix Enhanced Multivariance Products Representation (TMEMPR) respectively. We have used support matrices in the construction and not directly orthogonality of the constructed support matrices but block orthogonality which means the mutual orthonormality of the columns of produced support matrices. Certain confirmative implementations are given for novel method. A new decomposition method for vectors, whose construction is based on Kronecker product with a relation to the philosophy of TMEMPR has been proposed within the context of this thesis. This method, which is called Tridiagonal Vector Enhanced Multivariance Products Representation (TVEMPR), works with the logic of decomposing the target vector as summation of binary Kronecker products. Due to the method in the background, TVEMPR has a recursive structure and uses the folding and unfolding concepts. All decomposition methods in this thesis (TVEMPR, BTMEMPR, TFEMPR) are developed inventively. Performance of the methods change depending on the nature of the problem, data type and correlation between the input data. To this end, besides the methodology, applications in different areas are taken into consideration in the thesis. The proposed method, TFEMPR, has widespread application area, such as signal, image and video processing. It is a natural candidate as a data compression method. TFEMPR is applied on colored and grayscale video data to confirm the efficiency in reconstruction and video processing problems. Video data implementations bring out a new study for further development of TFEMPR. This study has arisen from the very nature of 8-bit quantized video data. Because TFEMPR is not a restricted method on target array, overflow values are observed during the implementations. To tackle with this problem modular arithmetic can be used. By this way overflows can be squeezed into the interval [0,255]. It is well known that hyperspectral imaging features an important issue in remote sensing and applications. Requirement to collect high volumes of hyperspectral data in remote sensing algorithms poses a compression problem. To this end, many techniques or algorithms have been developed and continues to be improved in scientific literature. In this thesis, also we propose TFEMPR as a lossy compression method by applying TFEMPR on hyperspectral images. Compression performance of TFEMPR is compared with state-of-the-art methods such as Compressive-Projection Principal Component Analysis (CPPCA), Matching Pursuit (MP) and Block Compressed Sensing (BCS) algorithms etc. via average peak signal-to-noise ratio. Experiments with AVIRIS dataset indicate a superior reconstructed image quality for the proposed technique in comparison to state-of-the-art hyperspectral data compression methods. In order to verify the feasibility of TFEMPR on more than-three-ways arrays, not only 3-way arrays are taken into consideration but also 4-way arrays are taken. TFEMPR is applied on 4-way real climate data and artificial data. In addition to these, comparative analysis of TFEMPR and state-of-the-art decomposition methods, Tucker and CP, is given in the thesis. Methods are applied on chemical datasets. The results in terms of relative errors are given and computation times of the each method are analysed.