টেনসর-ট্রেন বিয়োজনের মাধ্যমে কাঠামোগত সহপ্রসরণ অনুমান

মৌলিক তথ্য

• পত্র আইডি: 2510.08174
• শিরোনাম: টেনসর-ট্রেন বিয়োজনের মাধ্যমে কাঠামোগত সহপ্রসরণ অনুমান
• লেখক: আর্টসিওম পাটারুসাউ, নিকিতা পুচকিন, ম্যাক্সিম রাখুবা, ফেডর নোসকভ (এইচএসই বিশ্ববিদ্যালয়)
• শ্রেণীবিভাগ: math.ST (পরিসংখ্যান তত্ত্ব)
• প্রকাশনার সময়: ২০২৫ সালের ১৫ অক্টোবর
• পত্র লিঙ্ক: https://arxiv.org/abs/2510.08174v2

সারসংক্ষেপ

এই পত্রটি স্বাধীন সমবিতরণ উচ্চমাত্রিক দৈব়িক ভেক্টর নমুনা থেকে সহপ্রসরণ ম্যাট্রিক্স অনুমানের সমস্যা অধ্যয়ন করে। মাত্রার অভিশাপ এড়াতে, লেখকরা সহপ্রসরণ ম্যাট্রিক্স Σ-এর কাঠামোতে অতিরিক্ত অনুমান প্রয়োগ করেন, বিশেষভাবে Σ যখন টেনসর-ট্রেন (TT) বিন্যাসে ছোট ম্যাট্রিক্সের দ্বিগুণ ক্রোনেকার গুণফলের যোগফল দ্বারা অনুমানিত হতে পারে তা অধ্যয়ন করেন। এই সেটআপ প্রাকৃতিকভাবে সুপরিচিত ক্রোনেকার যোগ এবং CANDECOMP/PARAFAC মডেলকে প্রসারিত করে, কিন্তু পদ্ধতিগুলির মধ্যে আরও সমৃদ্ধ মিথস্ক্রিয়া অনুমতি দেয়। লেখকরা TT-SVD এবং Tucker-2 মিশ্র কাঠামোর জন্য প্রযোজ্য উচ্চতর অর্থোগোনাল পুনরাবৃত্তি (HOOI) ভিত্তিক বহুপদী সময় পুনরাবৃত্তিমূলক অ্যালগরিদম প্রস্তাব করেন, এবং লুকানো ক্রোনেকার গুণফল এবং টেনসর-ট্রেন কাঠামো বিবেচনা করে সহপ্রসরণ অনুমান নির্ভুলতার অ-অসীমতাবাদী মাত্রা-মুক্ত সীমানা প্রাপ্ত করেন।

গবেষণা পটভূমি এবং প্রেরণা

সমস্যা সংজ্ঞা

স্বাধীন সমবিতরণ কেন্দ্রীভূত দৈব়িক ভেক্টর $X, X_1, \ldots, X_n \in \mathbb{R}^d$ দেওয়া হলে, তাদের সহপ্রসরণ ম্যাট্রিক্স $\Sigma = \mathbb{E}[XX^T] \in \mathbb{R}^{d \times d}$ অনুমান করতে হবে।

গবেষণা প্রেরণা

১. মাত্রার অভিশাপ সমস্যা: উচ্চমাত্রিক ক্ষেত্রে, ধ্রুবক নমুনা সহপ্রসরণ অনুমানক $\hat{\Sigma} = \frac{1}{n}\sum_{i=1}^n X_i X_i^T$ মাত্রার অভিশাপের সম্মুখীন হয়, যখন $d$ বড় হয় তখন কর্মক্ষমতা তীব্রভাবে হ্রাস পায়।

२. কাঠামোগত অনুমানের প্রয়োজনীয়তা: এই সমস্যা অতিক্রম করতে, পরিসংখ্যানবিদরা সাধারণত $\Sigma$-এ অতিরিক্ত কাঠামোগত অনুমান প্রয়োগ করেন ডেটা কাঠামো ব্যবহার করতে এবং অজানা পরামিতির মোট সংখ্যা হ্রাস করতে।

३. বিদ্যমান পদ্ধতির সীমাবদ্ধতা:

• ক্রোনেকার গুণফল মডেল $\Sigma = \Phi \otimes \Psi$ অত্যন্ত সরল
• ক্রোনেকার যোগ মডেল $\Sigma = \sum_{k=1}^K \Phi_k \otimes \Psi_k$ পর্যাপ্ত নমনীয়তার অভাব রাখে
• CANDECOMP/PARAFAC মডেল গণনায় NP-কঠিন সমস্যার সম্মুখীন হয়

এই পত্রের উদ্ভাবন

টেনসর-ট্রেন (TT) বিন্যাসের সহপ্রসরণ মডেল প্রস্তাব করা হয়: $\Sigma = \sum_{j=1}^J \sum_{k=1}^K U_j \otimes V_{jk} \otimes W_k$ যেখানে $U_j \in \mathbb{R}^{p \times p}$, $V_{jk} \in \mathbb{R}^{q \times q}$, $W_k \in \mathbb{R}^{r \times r}$, এবং $pqr = d$।

মূল অবদান

१. নতুন সহপ্রসরণ মডেল: টেনসর-ট্রেন বিয়োজনের উপর ভিত্তি করে সহপ্রসরণ কাঠামো প্রস্তাব করা হয়েছে, যা প্রাকৃতিকভাবে ক্রোনেকার যোগ এবং CANDECOMP/PARAFAC মডেলকে প্রসারিত করে, পদ্ধতিগুলির মধ্যে আরও সমৃদ্ধ মিথস্ক্রিয়া অনুমতি দেয়।

२. দক্ষ অ্যালগরিদম: HardTTh অ্যালগরিদম ডিজাইন করা হয়েছে (হার্ড টেনসর ট্রেন থ্রেশহোল্ডিং), TT-SVD এবং Tucker-2 মিশ্র কাঠামোর জন্য অভিযোজিত HOOI-এর উপর ভিত্তি করে, গণনা জটিলতা $O((J+K)Td_1d_2d_3)$।

३. তাত্ত্বিক গ্যারান্টি: অ-অসীমতাবাদী, মাত্রা-মুক্ত সংবেদনশীলতা সীমানা প্রতিষ্ঠা করা হয়েছে, যা TT কাঠামো টেনসর অনুমানের জন্য প্রথম মাত্রা-মুক্ত তাত্ত্বিক ফলাফল।

४. ব্যবহারিক যাচাইকরণ: সংখ্যাগত পরীক্ষার মাধ্যমে পদ্ধতির কার্যকারিতা যাচাই করা হয়েছে, পুনরাবৃত্তিমূলক উন্নতির প্রয়োজনীয়তা প্রদর্শন করে।

পদ্ধতি বিবরণ

কাজের সংজ্ঞা

ইনপুট: স্বাধীন সমবিতরণ নমুনা $X_1, \ldots, X_n \in \mathbb{R}^{pqr}$আউটপুট: সহপ্রসরণ ম্যাট্রিক্স $\Sigma$ এর অনুমান $\tilde{\Sigma}$সীমাবদ্ধতা: $\Sigma$ TT কাঠামো রাখে, $\Sigma = \sum_{j=1}^J \sum_{k=1}^K U_j \otimes V_{jk} \otimes W_k$ হিসাবে প্রকাশযোগ্য

মডেল স্থাপত্য

টেনসর পুনর্বিন্যাস এবং বিয়োজন

१. পুনর্বিন্যাস অপারেশন: সহপ্রসরণ ম্যাট্রিক্স $\Sigma \in \mathbb{R}^{pqr \times pqr}$ কে তিন-ক্রম টেনসর $\mathcal{R}(\Sigma) \in \mathbb{R}^{p^2 \times q^2 \times r^2}$-এ পুনর্বিন্যাস করা হয়

२. TT বিয়োজন প্রতিনিধিত্ব: $\mathcal{R}(\Sigma) = \sum_{j=1}^J \sum_{k=1}^K \text{vec}(U_j) \otimes \text{vec}(V_{jk}) \otimes \text{vec}(W_k)$

३. সংক্ষিপ্ত রূপ: $\mathcal{R}(\Sigma) = U \times_1 V \times_3 W$ যেখানে $U \in O_{p^2,J}$, $V \in O_{r^2,K}$, $W \in \mathbb{R}^{J \times q^2 \times K}$

HardTTh অ্যালগরিদম

অ্যালগরিদম ১: HardTTh

ইনপুট: টেনসর Y ∈ R^{d₁×d₂×d₃}, TT র‍্যাঙ্ক (J,K), পুনরাবৃত্তি পদক্ষেপ T
আউটপুট: TT অনুমান T̂ = Û ×₁ V̂ ×₃ Ŵ

१. m₁(Y) এর ছাঁটা SVD গণনা করুন: Û₀, Σ₀,₁, Ũ₀ = SVD_J(m₁(Y))
२. m₃(Û₀ᵀ ×₁ Y) এর ছাঁটা SVD গণনা করুন: V̂₀, Σ₀,₂, Ṽ₀ = SVD_K(m₃(Û₀ᵀ ×₁ Y))

t = १, ..., T এর জন্য:
३. Ût, Σt,₁, Ũt = SVD_J(m₁(V̂ₜ₋₁ᵀ ×₃ Y))
४. V̂t, Σt,₂, Ṽt = SVD_K(m₃(Ûtᵀ ×₁ Y))

५. সেট করুন Û = ÛT, V̂ = V̂T, Ŵ = Ûᵀ ×₁ V̂ᵀ ×₃ Y

প্রযুক্তিগত উদ্ভাবন পয়েন্ট

१. Tucker-२ মিশ্র কাঠামো: মান Tucker বিয়োজনের বিপরীতে যা তিনটি অর্থোগোনাল কারণ প্রয়োজন, TT কাঠামো শুধুমাত্র দুটি অর্থোগোনাল কারণ প্রয়োজন, গণনা জটিলতা হ্রাস করে।

२. পুনরাবৃত্তিমূলক উন্নতি কৌশল: পদ্ধতি সাবস্পেসকে বিকল্পভাবে অপ্টিমাইজ করে, ধাপে ধাপে অনুমান নির্ভুলতা উন্নত করে।

३. কঠোর থ্রেশহোল্ড প্রক্রিয়াকরণ: নরম থ্রেশহোল্ডের পরিবর্তে কঠোর থ্রেশহোল্ড ব্যবহার করা হয়, টেনসর নিউক্লিয়ার নর্ম অনুমানের NP-কঠিন সমস্যা এড়ায়।

পরীক্ষামূলক সেটআপ

ডেটা উৎপাদন মডেল

• TT র‍্যাঙ্ক: $J = 7, K = 9$
• মাত্রা: $p = q = r = 10$, মোট মাত্রা $d = 1000$
• উৎপাদন প্রক্রিয়া:
  • দৈব়িক প্রতিসম ম্যাট্রিক্স $A_j \in \mathbb{R}^{p \times p}$, $B_{jk} \in \mathbb{R}^{q \times q}$, $C_k \in \mathbb{R}^{r \times r}$ উৎপাদন করুন
  • দৈব়িক ভেক্টর সংজ্ঞায়িত করা হয়: $\sum_{j=1}^J \sum_{k=1}^K A_j \times_1 B_{jk} \times_2 C_k \times_3 E_{ijk}$
  • যেখানে $E_{ijk}$ মান গাউসীয় টেনসর

মূল্যায়ন মেট্রিক্স

আপেক্ষিক ত্রুটি: $\|\hat{S} - \Sigma\|_F / \|\Sigma\|_F$

তুলনা পদ্ধতি

१. নমুনা গড়: নমুনা সহপ্রসরণ অনুমানক २. TT-HOSVD: HardTTh অ্যালগরিদমের অ-পুনরাবৃত্তিমূলক সংস্করণ ($T=0$) ३. Tucker: মান Tucker বিয়োজন ४. Tucker+HOOI: HOOI পুনরাবৃত্তি সহ Tucker বিয়োজন ५. PRLS: সংশোধিত নিয়মিত সর্বনিম্ন বর্গ পদ্ধতি

বাস্তবায়ন বিবরণ

• পুনরাবৃত্তি সংখ্যা: $T = 10$
• PRLS পরামিতি: লগারিদমিক স্কেল গ্রিডে $\lambda_1, \lambda_2$ সুর করা হয়েছে
• পরীক্ষা পুনরাবৃত্তি: প্রতিটি সেটিং ১६-३२ বার পুনরাবৃত্ত করা হয়েছে

পরীক্ষামূলক ফলাফল

প্রধান ফলাফল

মূল আবিষ্কার

१. পুনরাবৃত্তির প্রয়োজনীয়তা: HardTTh TT-HOSVD এর তুলনায় উল্লেখযোগ্য উন্নতি করে, বিশেষত n=2000 এ, আপেক্ষিক ত্রুটি 0.154 থেকে 0.082 এ হ্রাস পায়।

२. সংবেদনশীলতা আচরণ:

• n=500 এ: $\sin\Theta(\text{Im}\hat{U}_0, \text{Im}U^*) \approx 1$, $\sin\Theta(\text{Im}\hat{U}_T, \text{Im}U^*) \approx 1$
• n=2000 এ: $\sin\Theta(\text{Im}\hat{U}_0, \text{Im}U^*) \approx 1$, $\sin\Theta(\text{Im}\hat{U}_T, \text{Im}U^*) = 0.33±0.08$

३. গণনা দক্ষতা: HardTTh এর সময় জটিলতা মধ্যম, সম্পূর্ণ Tucker বিয়োজনের চেয়ে দ্রুত কিন্তু TT-HOSVD এর চেয়ে ধীর।

তাত্ত্বিক যাচাইকরণ

পরীক্ষা তাত্ত্বিক শর্তের প্রয়োজনীয়তা নিশ্চিত করে: যখন একক মান শর্ত সন্তুষ্ট না হয় (যেমন n=500), অ্যালগরিদম কার্যকরভাবে সাবস্পেস পুনরুদ্ধার করতে পারে না; যখন শর্ত সন্তুষ্ট হয় (যেমন n≥2000), পুনরাবৃত্তি কর্মক্ষমতা উল্লেখযোগ্যভাবে উন্নত করে।

সম্পর্কিত কাজ

ক্রোনেকার গুণফল মডেল

• একক ক্রোনেকার গুণফল: Werner et al. (2008) $\Sigma = \Phi \otimes \Psi$ মডেল প্রস্তাব করেন
• ক্রোনেকার যোগ: Tsiligkaridis & Hero (2013), Puchkin & Rakhuba (2024) $\Sigma = \sum_k \Phi_k \otimes \Psi_k$ মডেল অধ্যয়ন করেন

টেনসর বিয়োজন পদ্ধতি

• CP বিয়োজন: গণনা জটিলতা সমস্যার সম্মুখীন হয়
• Tucker বিয়োজন: Zhang & Xia (2018) ইত্যাদি মাত্রা-সম্পর্কিত সীমানা প্রতিষ্ঠা করেন
• TT বিয়োজন: Oseledets (2011) প্রস্তাব করেন, এই পত্র প্রথম সহপ্রসরণ অনুমানে প্রয়োগ করে

তাত্ত্বিক অগ্রগতি

• মাত্রা-সম্পর্কিত সীমানা: বেশিরভাগ বিদ্যমান ফলাফল পরিবেশগত মাত্রার উপর নির্ভর করে
• মাত্রা-মুক্ত সীমানা: শুধুমাত্র সরল ক্ষেত্রে সীমাবদ্ধ, এই পত্র TT কাঠামোতে প্রসারিত করে

উপসংহার এবং আলোচনা

প্রধান উপসংহার

१. মডেল সুবিধা: TT বিন্যাস সহপ্রসরণ মডেল গণনা সম্ভাব্যতা বজায় রেখে ঐতিহ্যবাহী ক্রোনেকার মডেলের চেয়ে আরও সমৃদ্ধ কাঠামো প্রদান করে।

२. অ্যালগরিদম কার্যকারিতা: HardTTh অ্যালগরিদম বহুপদী সময় জটিলতা অর্জন করে এবং পুনরাবৃত্তির মাধ্যমে অনুমান গুণমান উল্লেখযোগ্যভাবে উন্নত করে।

३. তাত্ত্বিক গ্যারান্টি: TT কাঠামোর জন্য প্রথম মাত্রা-মুক্ত সংবেদনশীলতা সীমানা প্রতিষ্ঠা করা হয়েছে, ভেরিয়েন্স পদ: $\tilde{v} = 96\omega\|\Sigma\|\sqrt{\frac{Jr_1^2(\Sigma) + JKr_2^2(\Sigma) + Kr_3^2(\Sigma) + \log(48/\delta)}{n}}$

সীমাবদ্ধতা

१. একক মান শর্ত: অ্যালগরিদম $\sigma_J(m_1(\mathcal{R}(\Sigma))) \gtrsim \|\Sigma\|\sqrt{r_2^2(\Sigma)r_3^2(\Sigma)/n}$ প্রয়োজন, তাত্ত্বিক সর্বোত্তম শর্তের চেয়ে শক্তিশালী।

२. শব্দ কাঠামো: তাত্ত্বিক বিশ্লেষণ নির্দিষ্ট শব্দ কাঠামো অনুমান করে, সমজাতীয় শব্দ থেকে আলাদা।

३. পরামিতি নির্বাচন: TT র‍্যাঙ্ক $(J,K)$ নির্বাচন পূর্ব জ্ঞান বা ডেটা-চালিত পদ্ধতি প্রয়োজন।

ভবিষ্যত দিকনির্দেশনা

१. অপক্ষপাত পদ্ধতি: অ-সমজাতীয় শব্দ পরিচালনা করার জন্য অপক্ষপাত কৌশল উন্নয়ন।

२. অভিযোজিত র‍্যাঙ্ক নির্বাচন: তাত্ত্বিক গ্যারান্টি সহ র‍্যাঙ্ক নির্বাচন পদ্ধতি প্রতিষ্ঠা।

३. প্রসারিত প্রয়োগ: অন্যান্য কাঠামোগত ম্যাট্রিক্স অনুমান সমস্যায় পদ্ধতি প্রসারিত করা।

গভীর মূল্যায়ন

সুবিধা

१. তাত্ত্বিক উদ্ভাবন: প্রথমবারের মতো TT কাঠামো সহপ্রসরণ অনুমানের জন্য মাত্রা-মুক্ত তাত্ত্বিক সীমানা প্রদান করে, গুরুত্বপূর্ণ তাত্ত্বিক শূন্যতা পূরণ করে।

२. পদ্ধতি ব্যবহারিকতা: HardTTh অ্যালগরিদম যুক্তিসঙ্গত গণনা জটিলতা রাখে, NP-কঠিন সমস্যা এড়ায়।

३. পরীক্ষা সম্পূর্ণ: বিভিন্ন তুলনা পদ্ধতি এবং বিভিন্ন নমুনা আকারের মাধ্যমে পদ্ধতির কার্যকারিতা যাচাই করা হয়েছে।

४. বিশ্লেষণ গভীর: বিস্তারিত তাত্ত্বিক বিশ্লেষণ এবং অ্যালগরিদম সংবেদনশীলতা অধ্যয়ন প্রদান করা হয়েছে।

অপূর্ণতা

१. শক্তিশালী শর্ত: তাত্ত্বিক শর্ত পরিচিত নিম্ন সীমানার চেয়ে কঠোর, পরিসংখ্যান-গণনা ফাঁক বিদ্যমান।

२. মডেল সীমাবদ্ধতা: শুধুমাত্র TT বিন্যাস দ্বারা ভালভাবে অনুমানিত সহপ্রসরণ ম্যাট্রিক্সের জন্য প্রযোজ্য।

३. পরামিতি সংবেদনশীলতা: কর্মক্ষমতা TT র‍্যাঙ্ক পরামিতির সঠিক নির্বাচনের উপর নির্ভর করে।

প্রভাব

१. তাত্ত্বিক অবদান: উচ্চমাত্রিক পরিসংখ্যানে টেনসর পদ্ধতির জন্য নতুন তাত্ত্বিক সরঞ্জাম প্রদান করে।

२. ব্যবহারিক মূল্য: বহু-পদ্ধতি ডেটা বিশ্লেষণ, সংকেত প্রক্রিয়াকরণ ইত্যাদি ক্ষেত্রে সম্ভাব্য প্রয়োগ রয়েছে।

३. পদ্ধতিগত তাৎপর্য: পরিসংখ্যান অনুমান সমস্যায় টেনসর বিয়োজন কৌশল কার্যকরভাবে প্রয়োগ করার পদ্ধতি প্রদর্শন করে।

প্রযোজ্য দৃশ্যকল্প

१. বহু-পদ্ধতি ডেটা: চিত্র, ভিডিও ইত্যাদি প্রাকৃতিক টেনসর কাঠামো সহ ডেটা २. সময়-স্থান ডেটা: সময়-স্থান কাঠামো সহ সহপ্রসরণ অনুমান ३. উচ্চমাত্রিক আর্থিক ডেটা: সম্পদ রিটার্নের কাঠামোগত সহপ্রসরণ মডেলিং ४. সেন্সর নেটওয়ার্ক: বহু-সেন্সর ডেটার সহপ্রসরণ অনুমান

তথ্যসূত্র

१. Werner, K., Jansson, M., & Stoica, P. (2008). ক্রোনেকার গুণফল কাঠামো সহ সহপ্রসরণ ম্যাট্রিক্সের অনুমান সম্পর্কে। २. Tsiligkaridis, T., & Hero, A. O. (2013). ক্রোনেকার গুণফল সম্প্রসারণের মাধ্যমে উচ্চমাত্রায় সহপ্রসরণ অনুমান। ३. Zhang, A., & Xia, D. (2018). টেনসর SVD: পরিসংখ্যানগত এবং গণনা সীমা। ४. Puchkin, N., & Rakhuba, M. (2024). মাত্রা-মুক্ত কাঠামোগত সহপ্রসরণ অনুমান। ५. Oseledets, I. V. (2011). টেনসর-ট্রেন বিয়োজন।