Mahdi Molavit-SVD, Kilmer ve Martin (2011) tarafından ortaya konan, üçüncü mertebeden tensörler için bir tekil değer ayrışımıdır. Bir tensörü A = U ∗ S ∗ VT biçiminde yazar; burada ∗ t-çarpımı, U ve V ortogonal tensörler, S ise f-köşegendir. Pratikte üçüncü mod boyunca bir FFT alır, her ön dilimin sıradan SVD'sini hesaplar ve geri dönüştürürsünüz; ilk k terimi tutmak, tüp rankı en fazla k olan en iyi Frobenius normu yaklaşımını verir.
Neden yeni bir çarpım?
Matris tekil değer ayrışımının üç özelliğine güvenilir: ortogonal çarpanlar, köşegen bir orta çarpan ve optimal kesme (Eckart–Young teoremi). Klasik tensör genellemelerinin her biri bunlardan en az birinden vazgeçer. HOSVD ile hesaplanan Tucker ortogonal çarpanları korur, ama çekirdek tensörü yoğundur ve kesmesi optimal değildir. CP, rank-bir terimlerin temiz bir toplamını verir, ama ortogonallik yoktur ve hesaplanması zordur. t-SVD başka bir yol izler ve çarpma işleminin kendisini değiştirir. t-çarpımı altında, bilinen SVD önermeleri neredeyse kelimesi kelimesine geçerlidir.
t-çarpımı
n1×n2×n3 boyutundaki bir A tensörünü A1, A2, … ön dilimlerinden oluşan bir yığın olarak düşünün. Bu düzenlemeyi iki yardımcı işlem üstlenir:
- unfold(A) ön dilimleri üst üste yığarak n1n3×n2 boyutunda bir matris oluşturur; fold bunu geri alır.
- bcirc(A), ilk blok sütununda dilimleri sırayla tutan n1n3×n2n3 boyutundaki blok dairesel matristir. Sonraki her blok sütun, bir öncekinin bir blok aşağı kaydırılmış hâlidir; son blok başa sarılarak en üste geçer.
n2×l×n3 boyutundaki ikinci bir B tensörü için t-çarpımı, n1×l×n3 boyutundaki şu tensördür:
A ∗ B = fold(bcirc(A) · unfold(B))
n3 = 1 olduğunda bu, sıradan matris çarpımıdır.
t-çarpımının arkasındaki blok dairesel matris ve yanında ikinci tensörün üst üste yığılmış ön dilimleri.
Bunu okumanın ikinci bir yolu da var. A tensörünü, elemanları n3 uzunluğunda tüpler olan n1×n2 boyutunda bir matris olarak görün. Bu durumda t-çarpımı, sayıları çarpmak yerine tüplerin dairesel evrişiminin kullanıldığı sıradan bir matris çarpımıdır. Bu dairesellik, hem çarpımın neden hızlı olduğunu hem de ana varsayımının nerede saklandığını açıklar.
bcirc ile yazıldığında çarpım pahalı görünür: blok dairesel matris tensörden n3 kat fazla eleman içerir ve doğrudan çarpım O(n1n2l n3²) maliyetlidir. Ancak ayrık Fourier dönüşümü dairesel matrisleri köşegenleştirir, blok dairesel matrisleri de blok köşegenleştirir. Bu yüzden iki tensörün de üçüncü mod boyunca FFT'sini alır, eşleşen ön dilimleri n3 bağımsız matris çarpımı olarak çarpar ve ters FFT alırsınız. Dönüşümler O((n1n2 + n2l + n1l) n3 log n3), dilim çarpımları ise toplamda O(n1n2l n3) maliyetlidir ve çarpımlar paralel çalışabilir. Reel veride Fourier dilimleri karmaşık eşlenik çiftler hâlinde gelir; bu yüzden yalnızca yaklaşık yarısının hesaplanması gerekir.
Transpoz, birim tensör ve ortogonallik
- t-transpoz AT, n2×n1×n3 boyutundadır; her ön dilimin transpozunu alır, ardından 2 ile n3 arasındaki dilimlerin sırasını tersine çevirir.
- Birim tensör, ilk ön dilimi birim matris olan ve geri kalan her yerde sıfır içeren tensördür.
- Bir Q tensörü, QT ∗ Q = Q ∗ QT = I olduğunda ortogonaldir.
- Her ön dilimi köşegen bir matris olan tensöre f-köşegen denir.
Ayrışım
Her reel n1×n2×n3 tensör A = U ∗ S ∗ VT biçiminde yazılabilir; burada U (n1×n1×n3) ve V (n2×n2×n3) ortogonal, S (n1×n2×n3) ise f-köşegendir. S tensörünün köşegen tüpleri, yani tekil tüpler, tekil değerlerin yerini alır; U ve V tensörlerinin yanal dilimleri de tekil vektörlerin yerini alır. Tarif kısadır:
- A tensörünün üçüncü mod boyunca FFT'sini alın.
- Her ön dilimin sıradan matris SVD'sini hesaplayın.
- Yığılmış çarpanların ters FFT'sini alın.
n1×n2×n3 boyutundaki bir tensörün t-SVD'si. Renkli kısımlar k ranklı bir kesmenin tuttuğu parçalardır; alt satır, üçüncü mod boyunca bir dönüşümden sonra aynı çarpanlara ayırmanın ön dilim başına bir matris SVD'si olarak gösterimidir.
Kesme ve tüp rankı
Matrislerde olduğu gibi, U ve V tensörlerinin yalnızca ilk k yanal dilimini ve ilk k tekil tüpü tutabilirsiniz:
Ak = Uk ∗ Sk ∗ VkT = ∑i=1..k U(:, i, :) ∗ S(i, i, :) ∗ V(:, i, :)T
Kilmer ve Martin, tüp rankı en fazla k olan tüm tensörler arasında A tensörüne Frobenius normunda en iyi yaklaşımın Ak olduğunu gösterdi; tüp rankı, sıfırdan farklı tekil tüplerin sayısıdır. Bu, Eckart–Young teoreminin t-çarpımındaki karşılığıdır. Garanti bu cebirin içinde geçerlidir ve CP rankı ya da Tucker rankı hakkında hiçbir şey söylemez. Hesaplama açısından kesme, Fourier uzayındaki her dilimde en büyük k tekil değeri tutmak demektir.
t-SVD'yi yalnızca sıkıştırma için değil öğrenme için de kullanışlı kılan bu özelliktir. Tezimde her eğitim görüntüsü bir yanal dilimdi ve U tensörünün ilk k yanal dilimi, görüntülerin sınıflandırmadan önce üzerine izdüşürüldüğü taban oldu.
Maliyet
Tam bir t-SVD, n1×n2 boyutlu matrislerin n3 bağımsız SVD'sine ve üçüncü mod boyunca O(n1n2n3 log n3) süren dönüşümlere mal olur. Reel girdi için bu SVD'lerin yalnızca ⌊n3/2⌋ + 1 tanesi gerekir, çünkü geri kalanlar karmaşık eşleniklerdir. Blok dairesel matris hiçbir zaman oluşturulmaz ve dilim SVD'leri zahmetsizce paralelleştirilir.
Bir NumPy taslağı
Bu sürüm ekonomik boyutlu çarpanlar döndürür ve isteğe bağlı bir kesme rankı k alır. Tek ince nokta ikinci döngüdür: reel girdide çarpanlar eşlenik çiftlere uymalıdır, aksi hâlde ters FFT reel bir sonuç vermez.
import numpy as np
def t_product(A, B):
Af, Bf = np.fft.fft(A, axis=2), np.fft.fft(B, axis=2)
Cf = np.einsum("ijk,jlk->ilk", Af, Bf) # one product per slice
return np.real(np.fft.ifft(Cf, axis=2))
def t_transpose(A):
At = np.transpose(A, (1, 0, 2)) # transpose each slice
return np.concatenate([At[:, :, :1], At[:, :, :0:-1]], axis=2)
def t_svd(A, k=None):
n1, n2, n3 = A.shape
r = min(n1, n2) if k is None else k
Af = np.fft.fft(A, axis=2)
Uf = np.zeros((n1, r, n3), complex)
Sf = np.zeros((r, r, n3), complex)
Vf = np.zeros((n2, r, n3), complex)
half = n3 // 2 + 1
for i in range(half): # SVD of each Fourier slice
u, s, vh = np.linalg.svd(Af[:, :, i], full_matrices=False)
Uf[:, :, i] = u[:, :r]
Sf[:, :, i] = np.diag(s[:r])
Vf[:, :, i] = vh[:r].conj().T
for i in range(half, n3): # real input: conjugate pairs
Uf[:, :, i] = Uf[:, :, n3 - i].conj()
Sf[:, :, i] = Sf[:, :, n3 - i].conj()
Vf[:, :, i] = Vf[:, :, n3 - i].conj()
back = lambda T: np.real(np.fft.ifft(T, axis=2))
return back(Uf), back(Sf), back(Vf)
A = np.random.rand(6, 5, 4)
U, S, V = t_svd(A)
print(np.allclose(A, t_product(t_product(U, S), t_transpose(V)))) # True
U2, S2, V2 = t_svd(A, k=2) # tubal rank 2
A2 = t_product(t_product(U2, S2), t_transpose(V2))
print(np.linalg.norm(A - A2) / np.linalg.norm(A)) # relative error
FFT'de saklı varsayım
Dairesel yapı bir tercihi kodlar: üçüncü mod başa sarar, yani son ön dilim ilkinin komşusu sayılır. Bazı veriler için bu zararsızdır. Görüntüler, sinyaller ve zaman serileri içinse bu, bir fotoğrafın sağ kenarının sol kenarından devam ettiğini varsaymak gibidir. Sonuç, hangi modu üçüncü sıraya koyduğunuza ve dilimlerin sırasına da bağlıdır, çünkü t-SVD modlarına göre simetrik değildir. Kendi varyantım tc-SVD, yukarıdaki her şeyi korur ama başa sarmayı bir aynayla, FFT'yi de DCT ile değiştirir.
Karşılaştırma rehberi t-SVD'yi CP ve Tucker ile karşılaştırıyor. Tensor Notları'nın 1. bölümü daha uzun seriyi başlatıyor; sonraki bölümler Notlar bölümünde listeleniyor.
Sık sorulan sorular
t-SVD'yi kim ortaya koydu?
t-SVD ve t-çarpımı, 2011'de Kilmer ve Martin tarafından ortaya konmuştur. Çalışmaları, t-SVD'yi kesmenin, belirli bir tüp rankı için Frobenius normunda en iyi yaklaşımı verdiğini de göstermiştir.
f-köşegen ne demektir?
Her ön dilimi köşegen bir matris olan tensöre f-köşegen denir. t-SVD'de ortadaki S çarpanı f-köşegendir ve onun köşegen tüpleri, yani tekil tüpler, tekil değerlerin rolünü üstlenir.
t-SVD neden FFT ile hesaplanır?
t-çarpımı blok dairesel matrislerden kurulur ve ayrık Fourier dönüşümü bu matrisleri blok köşegenleştirir. Üçüncü mod boyunca bir FFT uygulandıktan sonra tensör problemi, her ön dilim için bir tane olmak üzere bağımsız matris SVD'lerine ayrılır.
Kesilmiş t-SVD optimal midir?
Evet, t-çarpımı anlamında: k tekil tüpü tutmak, tüp rankı en fazla k olan tensörler arasında Frobenius normunda en iyi yaklaşımı verir. Bu garanti CP rankını veya Tucker rankını kapsamaz.
Bir tensörün tüp rankı nedir?
Tüp rankı, bir tensörün t-SVD'sindeki sıfırdan farklı tekil tüplerin sayısıdır. Sıradan tekil değer ayrışımında matris rankının oynadığı rolü oynar.