t-SVD چیست؟

t-SVD نسخه‌ای از تجزیهٔ مقادیر تکین برای تانسورهای مرتبهٔ سه است که کیلمر و مارتین در سال ۲۰۱۱ معرفی کردند. این تجزیه تانسور را به شکل A = U ∗ S ∗ V^T می‌نویسد که در آن ∗ ضرب t است،‏ U و V تانسورهای متعامدند و S اف‌قطری است. در عمل در راستای مُد سوم FFT می‌گیریم،‏ برای هر اسلایس روبه‌رو یک SVD معمولی حساب می‌کنیم و برمی‌گردیم؛‏ نگه داشتن k جملهٔ اول،‏ بهترین تقریب با رتبهٔ تیوبی حداکثر k را در نرم فروبنیوس می‌دهد.

چرا یک ضرب تازه؟

SVD ماتریسی سه ویژگی دارد که همه به آن‌ها تکیه می‌کنیم: عامل‌های متعامد،‏ عامل میانی قطری و برش بهینه (قضیهٔ اکارت-یانگ). تعمیم‌های کلاسیک تانسوری هرکدام دست‌کم یکی از این‌ها را از دست می‌دهند. تجزیهٔ تاکر،‏ وقتی با HOSVD محاسبه شود،‏ عامل‌های متعامد دارد،‏ اما هسته‌اش پُر است و برشش هم بهینه نیست. تجزیهٔ CP جمع تمیزی از جمله‌های رتبه‌یک می‌دهد،‏ اما تعامد ندارد و محاسبه‌اش سخت است. t-SVD راه دیگری می‌رود: به‌جای شکل عامل‌ها،‏ خود ضرب را عوض می‌کند. با ضرب t،‏ گزاره‌های آشنای SVD تقریباً کلمه‌به‌کلمه درست می‌مانند.

ضرب t

تانسور A با ابعاد n₁×n₂×n₃ را دسته‌ای از اسلایس‌های روبه‌رو ببینید: A₁،‏ A₂ و الی آخر. دو عملیات کمکی حساب‌وکتاب را انجام می‌دهند:

• unfold اسلایس‌های روبه‌رو را زیر هم می‌چیند و ماتریسی با n₁n₃ سطر و n₂ ستون می‌سازد؛‏ fold همین کار را برعکس انجام می‌دهد.
• bcirc یک ماتریس بلوکی چرخشی می‌سازد که ستون بلوکی اولش اسلایس‌ها را به ترتیب زیر هم دارد. هر ستون بلوکی بعدی همان ستون قبلی است که یک بلوک پایین رفته و بلوک آخرش به بالا برگشته است.

اگر B تانسوری با ابعاد n₂×l×n₃ باشد،‏ ضرب t به این شکل تعریف می‌شود و حاصلش تانسوری n₁×l×n₃ است:

A ∗ B = fold(bcirc(A) · unfold(B))

اگر n₃ برابر یک باشد،‏ این همان ضرب معمولی ماتریس‌هاست.

ماتریس بلوکی چرخشی پشت ضرب t،‏ کنار اسلایس‌های روی هم چیده‌شدهٔ تانسور دوم.

این ضرب را طور دیگری هم می‌شود دید. A را ماتریسی n₁×n₂ فرض کنید که درایه‌هایش به‌جای عدد،‏ تیوب‌هایی به طول n₃ هستند. ضرب t همان ضرب معمولی ماتریس‌هاست،‏ با این تفاوت که به‌جای ضرب دو عدد،‏ پیچش چرخشی دو تیوب را حساب می‌کنیم. همین چرخشی بودن هم سرعت این ضرب را توضیح می‌دهد و هم فرض اصلی‌اش را.

اگر ضرب را با bcirc بنویسیم،‏ گران به نظر می‌رسد: ماتریس بلوکی چرخشی n₃ برابر خود تانسور درایه دارد و ضرب مستقیم از مرتبهٔ ‎O(n₁n₂l n₃²)‎ است. اما تبدیل فوریهٔ گسسته ماتریس‌های چرخشی را قطری و ماتریس‌های بلوکی چرخشی را بلوک‌قطری می‌کند. پس از هر دو تانسور در راستای مُد سوم FFT می‌گیریم،‏ اسلایس‌های روبه‌روی متناظر را دوبه‌دو در هم ضرب می‌کنیم (n₃ ضرب ماتریسی مستقل) و با FFT معکوس برمی‌گردیم. هزینهٔ تبدیل‌ها ‎O((n₁n₂ + n₂l + n₁l) n₃ log n₃)‎ است و ضرب اسلایس‌ها روی هم ‎O(n₁n₂l n₃)‎؛‏ این ضرب‌ها را می‌شود موازی اجرا کرد. برای دادهٔ حقیقی،‏ اسلایس‌های فوریه جفت‌های مزدوج مختلط‌اند و محاسبهٔ حدود نیمی از آن‌ها کافی است.

ترانهاده،‏ همانی و تعامد

• ترانهادهٔ t،‏ یعنی A^T با ابعاد n₂×n₁×n₃،‏ هر اسلایس روبه‌رو را ترانهاده می‌کند و بعد ترتیب اسلایس‌های ۲ تا n₃ را برعکس می‌کند.
• تانسور همانی تانسوری است که اسلایس روبه‌روی اولش ماتریس همانی است و بقیهٔ اسلایس‌هایش صفرند.
• تانسور Q متعامد است اگر ‎Q^T ∗ Q = Q ∗ Q^T = I‎ باشد.
• تانسوری که همهٔ اسلایس‌های روبه‌رویش ماتریس قطری باشند اف‌قطری است.

خود تجزیه

هر تانسور حقیقی n₁×n₂×n₃ را می‌شود به شکل ‎A = U ∗ S ∗ V^T‎ نوشت. در این تجزیه U با ابعاد n₁×n₁×n₃ و V با ابعاد n₂×n₂×n₃ متعامدند و S با ابعاد n₁×n₂×n₃ اف‌قطری است. تیوب‌های قطری S،‏ یعنی تیوب‌های تکین،‏ جای مقادیر تکین را می‌گیرند و اسلایس‌های جانبی U و V جای بردارهای تکین را. دستور محاسبه کوتاه است:

1. از A در راستای مُد سوم FFT بگیرید.
2. برای هر اسلایس روبه‌رو یک SVD ماتریسی معمولی حساب کنید.
3. از عامل‌های به‌دست‌آمده FFT معکوس بگیرید.

شمای t-SVD برای تانسوری n₁×n₂×n₃. بخش‌های رنگی همان چیزی است که در برش با رتبهٔ k نگه داشته می‌شود و ردیف پایین همین تجزیه را بعد از تبدیل در راستای مُد سوم،‏ به شکل یک SVD ماتریسی برای هر اسلایس روبه‌رو نشان می‌دهد.

برش و رتبهٔ تیوبی

درست مثل ماتریس‌ها،‏ می‌شود فقط k اسلایس جانبی اول U و V و k تیوب تکین اول را نگه داشت:

A_k = U_k ∗ S_k ∗ V_k^T = ∑_i=1..k U(:, i, :) ∗ S(i, i, :) ∗ V(:, i, :)^T

کیلمر و مارتین نشان دادند که A_k در نرم فروبنیوس بهترین تقریب A در میان همهٔ تانسورهایی با رتبهٔ تیوبی حداکثر k است؛‏ رتبهٔ تیوبی یعنی تعداد تیوب‌های تکین غیرصفر. این همتای قضیهٔ اکارت-یانگ در چارچوب ضرب t است. البته این تضمین فقط در همین چارچوب معنا دارد و دربارهٔ رتبهٔ CP یا رتبهٔ تاکر چیزی نمی‌گوید. از نظر محاسباتی،‏ برش یعنی در هر اسلایس فوریه فقط بزرگ‌ترین k مقدار تکین را نگه داریم.

همین ویژگی است که t-SVD را،‏ علاوه بر فشرده‌سازی،‏ به ابزاری برای یادگیری هم تبدیل می‌کند. در پایان‌نامه‌ام هر تصویر آموزشی یک اسلایس جانبی بود و k اسلایس جانبی اول U پایه‌ای می‌شد که تصویرها پیش از طبقه‌بندی روی آن تصویر می‌شدند.

هزینه

t-SVD کامل یعنی n₃ تجزیهٔ SVD مستقل روی ماتریس‌های n₁×n₂،‏ به‌علاوهٔ تبدیل‌های در راستای مُد سوم که ‎O(n₁n₂n₃ log n₃)‎ هزینه دارند. برای ورودی حقیقی فقط ‎⌊n₃/2⌋ + 1‎ تا از این SVDها لازم است،‏ چون بقیه مزدوج مختلط همان‌ها هستند. ماتریس بلوکی چرخشی هیچ‌وقت واقعاً ساخته نمی‌شود و SVD اسلایس‌ها به‌سادگی موازی می‌شوند.

پیاده‌سازی کوتاه با NumPy

این نسخه عامل‌ها را در اندازهٔ اقتصادی برمی‌گرداند و رتبهٔ برش k را هم به‌صورت اختیاری می‌گیرد. تنها بخش ظریف،‏ حلقهٔ دوم است: برای ورودی حقیقی،‏ عامل‌ها باید جفت‌های مزدوج را رعایت کنند،‏ وگرنه خروجی FFT معکوس حقیقی نمی‌شود. با t_svd(A, k=2)‎ هم مستقیم عامل‌های بریده‌شده با رتبهٔ تیوبی ۲ را می‌گیرید.

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)
    return np.real(np.fft.ifft(Cf, axis=2))

def t_transpose(A):
    At = np.transpose(A, (1, 0, 2))
    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):
        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):
        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

فرضی که FFT با خودش می‌آورد

ساختار چرخشی یک انتخاب را در خودش دارد: مُد سوم دور خودش می‌چرخد،‏ یعنی اسلایس آخر همسایهٔ اسلایس اول حساب می‌شود. برای بعضی داده‌ها این بی‌ضرر است. برای تصویر،‏ سیگنال و سری زمانی،‏ شبیه این است که فرض کنیم لبهٔ راست عکس ادامهٔ لبهٔ چپش است. نتیجهٔ t-SVD به این هم بستگی دارد که کدام مُد را سوم بگذارید و اسلایس‌ها به چه ترتیبی بیایند؛‏ این تجزیه نسبت به مُدهایش متقارن نیست. نسخه‌ای که خودم ساختم،‏ tc-SVD،‏ همهٔ آنچه را در این راهنما آمد نگه می‌دارد،‏ اما چرخش را با آینه و FFT را با DCT عوض می‌کند.

در مقایسهٔ CP،‏ تاکر و t-SVD این تجزیه کنار دو رقیب کلاسیکش قرار می‌گیرد. توضیح مفصل‌تر،‏ با شکل و کد،‏ از قسمت اول یادداشت‌های تانسوری شروع می‌شود و بقیهٔ قسمت‌ها در بخش یادداشت‌ها آمده‌اند.

پرسش‌های رایج

t-SVD را چه کسی معرفی کرد؟

t-SVD و ضرب t را کیلمر و مارتین در سال ۲۰۱۱ معرفی کردند. در همان کار نشان داده شد که t-SVD بریده‌شده،‏ در نرم فروبنیوس،‏ بهترین تقریب با رتبهٔ تیوبی داده‌شده را می‌دهد.

اف‌قطری یعنی چه؟

تانسوری اف‌قطری است که همهٔ اسلایس‌های روبه‌رویش ماتریس قطری باشند. در t-SVD عامل میانی S اف‌قطری است و تیوب‌های قطری‌اش،‏ یعنی تیوب‌های تکین،‏ نقش مقادیر تکین را دارند.

چرا t-SVD را با FFT حساب می‌کنند؟

ضرب t روی ماتریس‌های بلوکی چرخشی بنا شده و تبدیل فوریهٔ گسسته این ماتریس‌ها را بلوک‌قطری می‌کند. بعد از FFT در راستای مُد سوم،‏ مسئلهٔ تانسوری به چند SVD ماتریسی مستقل،‏ یکی برای هر اسلایس روبه‌رو،‏ تبدیل می‌شود.

آیا t-SVD بریده‌شده بهینه است؟

بله،‏ در چارچوب ضرب t: نگه داشتن k تیوب تکین بهترین تقریب در نرم فروبنیوس را در میان تانسورهایی با رتبهٔ تیوبی حداکثر k می‌دهد. این حکم دربارهٔ رتبهٔ CP یا رتبهٔ تاکر چیزی نمی‌گوید.

رتبهٔ تیوبی چیست؟

رتبهٔ تیوبی تعداد تیوب‌های تکین غیرصفر در t-SVD یک تانسور است. همان نقشی را دارد که رتبهٔ ماتریس برای SVD معمولی دارد.

در همین بخش

• CP، تاکر یا t-SVD؟
• تانسور چیست؟
• tc-SVD چیست؟