🔢 mathematics

A Practical Mode-parallel Implementation of the (H-)Tucker Decomposition via Randomization

यह शोध पत्र उच्च-आयामी डेटा के लिए सटीकता बनाए रखते हुए गणना समय, मेमोरी उपयोग और ऊर्जा खपत को महत्वपूर्ण रूप से कम करने के लिए रैंडमाइजेशन तकनीकों का उपयोग करते हुए टकर (Tucker) और एच-टकर (H-Tucker) टेंसर अपघटन के एक नवीन मोड-समानांतर (mode-parallel) कार्यान्वयन का प्रस्ताव करता है।

मूल लेखक: Martina Iannacito, Sascha Portaro, Davide Palitta, Claudio Arlandini, Domitilla Brandoni

प्रकाशित 2026-03-24

📖 6 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Martina Iannacito, Sascha Portaro, Davide Palitta, Claudio Arlandini, Domitilla Brandoni

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

कल्पना कीजिए कि आपके पास डेटा का एक विशाल, बहु-आयामी (multi-dimensional) पुस्तकालय है। केवल किताबों की एक सूची (1D) या किताबों की एक शेल्फ (2D) के बजाय, एक ऐसा पुस्तकालय कल्पना करें जहाँ हर किताब से एक रंग, एक बनावट (texture), एक गंध, एक ध्वनि और एक अहसास जुड़ा हुआ है। यह एक टेंसर (tensor) है। यह जटिल डेटा (जैसे कि वीडियो, मेडिकल स्कैन, या मौसम के पैटर्न) को एक ही व्यवस्थित पैकेज में स्टोर करने का एक तरीका है।

समस्या क्या है? ये पुस्तकालय बहुत तेजी से विशाल होते जाते हैं। इस डेटा का विश्लेषण करने की कोशिश करना दुनिया के हर एक पन्ने को एक साथ पढ़ने की कोशिश करने जैसा है। इसमें अनंत समय लगता है, बिजली का भारी खर्च होता है, और इसके लिए एक ऐसे स्टोरेज रूम की आवश्यकता होती है जो किसी शहर से भी बड़ा हो।

इस समस्या को हल करने के लिए, गणितज्ञ डिकम्पोजिशन (decomposition) नामक तकनीक का उपयोग करते हैं। इसे एक विशाल, बिखरे हुए पहेली (puzzle) को यह समझने की तरह सोचें कि वह वास्तव में कुछ छोटी, सरल पहेलियों से बनी है जो आपस में पूरी तरह फिट बैठती हैं। यह टकर (Tucker) और H-टकर (H-Tucker) डिकम्पोजिशन है। यह विशाल डेटा राक्षस को एक "कोर" (मुख्य कहानी) और कुछ "फैक्टर मैट्रिसेस" (कहानी कैसे सुनाई जाएगी, इसके नियम) में तोड़ देता है।

पुराने तरीके ऐसे थे जैसे पूरे समुद्र का एक पूर्ण-पैमाने का मॉडल बनाने के बाद ही पुल बनाने की कोशिश करना। आपको प्रोसेस करने के लिए डेटा के एक छोटे से हिस्से को भी पूरी मेमोरी में कॉपी करना पड़ता था। यह धीमा था और मेमोरी का बहुत अधिक उपयोग करता था।

नया समाधान: रैंडम सैंपलिंग के साथ "मोड-पैरेलल" (Mode-Parallel)

यह पेपर एक चतुर नया तरीका पेश करता है: रैंडमाइजेशन (Randomization) के माध्यम से मोड-पैरेलल डिकम्पोजिशन। आइए इन उपमाओं (analogies) के माध्यम से इसे समझते हैं।

1. पुराना तरीका: "कॉपी-पेस्ट" की आपदा

कल्पना कीजिए कि आप शेफ्स (chefs) की एक टीम हैं जो यह पता लगाने के लिए एक विशाल सूप का स्वाद लेना चाहते हैं कि उसमें कौन से सामग्रियां हैं।

पुराना तरीका: सूप का स्वाद लेने के लिए, हर एक शेफ को सूप के पूरे बर्तन की एक प्रति (copy) अपने स्टेशन पर लानी पड़ती थी। यदि आपके पास 8 शेफ हैं, तो आपको 8 विशाल बर्तनों की आवश्यकता होगी। यदि बर्तन समुद्र जितना बड़ा है, तो यह असंभव है।
बाधा (Bottleneck): जब तक हर किसी के पास अपना खुद का बर्तन नहीं होता, आप सूप का स्वाद नहीं ले सकते, और आप उन बर्तनों की प्रतियां उतनी तेजी से नहीं बना सकते।

2. नया तरीका: "सैंपलिंग" (Sampling) रणनीति

लेखक रैंडमाइजेशन (Randomization) और पैरेललिज्म (Parallelism) का उपयोग करके एक स्मार्ट तरीका प्रस्तावित करते हैं।

"फाइबर सैंपलिंग" (चखने वाला चम्मच):
पूरा बर्तन लाने के बजाय, कल्पना करें कि आपको बस एक चम्मच लेकर नमूना लेने की आवश्यकता है।

नया एल्गोरिदम पूरे "अनफोल्डेड" मैट्रिक्स (विशाल बर्तन) का निर्माण नहीं करता है। इसके बजाय, यह मूल टेंसर से कुछ रैंडम "फाइबर्स" (सोचिए ये डेटा की एकल स्ट्रैंड या विशिष्ट पंक्तियाँ हैं) चुनता है।
उपमा: पूरी लाइब्रेरी की कॉपी बनाने के बजाय, आप अलग-अलग शेल्फों से 100 किताबें रैंडमली चुनते हैं। यदि लाइब्रेरी अच्छी तरह से व्यवस्थित है (जो कि अधिकांश वास्तविक दुनिया के डेटा में होता है), तो वे 100 किताबें आपको पूरी लाइब्रेरी के बारे में लगभग सब कुछ बता देंगी।
लाभ: अब आपको 8 विशाल बर्तनों की आवश्यकता नहीं है। प्रत्येक शेफ को केवल सूप के एक छोटे कप की आवश्यकता है। यह मेमोरी की भारी बचत करता है।

"मोड-पैरेलल" (शेफ्स की टीम):

पुराना तरीका: रैंडम सैंपलिंग के बावजूद, कई पुराने एल्गोरिदम अभी भी शेफ्स को एक-एक करके काम करने के लिए मजबूर करते थे। शेफ 1 सूप चखता है, फिर शेफ 2, फिर शेफ 3।
नया तरीका: क्योंकि हम पूरा बर्तन कॉपी नहीं कर रहे हैं, इसलिए सभी 8 शेफ एक ही समय में काम कर सकते हैं। शेफ 1 "रंग" वाले आयाम (dimension) को चखता है, शेफ 2 "बनावट" वाले आयाम को चखता है, और इसी तरह। वे सभी समानांतर (parallel) में काम करते हैं।
परिणाम: काम 8 गुना तेज़ (या उससे भी अधिक) हो जाता है क्योंकि हर कोई एक-दूसरे का इंतज़ार किए बिना एक साथ काम कर रहा है।

3. "रेंज-फाइंडर" (स्मार्ट फ़िल्टर)

एक बार जब शेफ्स के पास उनके सूप के छोटे कप आ जाते हैं, तो उन्हें मुख्य सामग्रियों का पता लगाना होता है।

पेपर एक ऐसी तकनीक का उपयोग करता है जिसे रैंडमाइज्ड रेंज-फाइंडिंग (Randomized Range-Finding) कहा जाता है। कल्पना कीजिए कि शेफ्स के पास एक जादुई फ़िल्टर है जो तुरंत "स्वाद" को "पानी" से अलग कर देता है।
भले ही उन्होंने केवल एक छोटा सा नमूना चखा हो, यह फ़िल्टर उन्हें पूरे सूप के स्वाद प्रोफाइल को उच्च सटीकता के साथ पुनर्गठित करने में मदद करता है। यह एक ऐसे जासूस की तरह है जो केवल कुछ सुरागों को देखकर अपराध को सुलझा सकता है क्योंकि वह जानता है कि बिंदुओं को कैसे जोड़ना है।

यह क्यों महत्वपूर्ण है

गति (Speed): नया तरीका कई मामलों में मौजूदा सर्वोत्तम तरीकों की तुलना में 10 गुना तेज़ है।
मेमोरी (Memory): इसे मेमोरी में पूरा डेटासेट स्टोर करने की आवश्यकता नहीं है। यह छोटे स्लाइस के साथ काम करता है। इसका मतलब है कि आप उस डेटा का विश्लेषण एक मानक कंप्यूटर पर कर सकते हैं जिसके लिए पहले सुपरकंप्यूटर की आवश्यकता होती थी।
स्केलेबिलिटी (Scalability): लेखकों ने एक सुपरकंप्यूटर (Cineca में Leonardo) पर इसका परीक्षण किया। उन्होंने दिखाया कि जैसे-जैसे वे अधिक प्रोसेसर (अधिक शेफ) जोड़ते हैं, गति लगभग पूरी तरह से बढ़ती है। यह शानदार ढंग से स्केल करता है।
सटीकता (Accuracy): रैंडम सैंपल का उपयोग करने के बावजूद, इसके परिणाम धीमे और मेमोरी-गहन तरीकों जितने ही सटीक हैं।

H-Tucker ट्विस्ट

यह पेपर H-Tucker (Hierarchical Tucker) नामक एक अधिक जटिल संरचना पर भी लागू होता है।

उपमा: यदि टकर एक सपाट पहेली है, तो H-Tucker एक पेड़ जैसी संरचना (जैसे फैमिली ट्री) वाली पहेली है।
लेखकों ने इस पेड़ जैसी संरचना के लिए अपने रैंडम सैंपलिंग मेथड का एक संस्करण बनाया है। उन्होंने दिखाया कि इन जटिल, पेड़ जैसी डेटा संरचनाओं के लिए भी, आप पूरे पेड़ को बनाए बिना तेज़ी से और समानांतर में इसे तोड़ सकते हैं।

निचोड़ (The Bottom Line)

यह पेपर डेटा विश्लेषण के लिए ड्रोन डिलीवरी सिस्टम का आविष्कार करने जैसा है।

पहले: आपको पैकेज डिलीवर करने के लिए हर घर तक एक विशाल ट्रक (पुराना एल्गोरिदम) चलाना पड़ता था। यह धीमा था और सड़कों को जाम कर देता था।
अब: आप छोटे ड्रोन्स का एक झुंड (रैंडम सैंपल्स) भेजते हैं जो विशिष्ट घरों में उड़ते हैं, आवश्यक जानकारी लेते हैं, और उसे तुरंत वापस लाते हैं। वे सभी एक साथ उड़ते हैं (पैरेलल), वे सड़कों को जाम नहीं करते (कम मेमोरी), और वे रिकॉर्ड समय में काम पूरा कर देते हैं।

यह हमारे सबसे बड़े, सबसे जटिल डेटासेट्स के भीतर छिपे रहस्यों को अनलॉक करने का एक व्यावहारिक, ऊर्जा-कुशल और अविश्वसनीय रूप से तेज़ तरीका है।

यहाँ इन्नैसिटो (Iannacito) और अन्य द्वारा लिखित शोध पत्र "A Practical Mode-Parallel Implementation of the (H-)Tucker Decomposition via Randomization" का विस्तृत तकनीकी सारांश दिया गया है।

1. समस्या विवरण (Problem Statement)

टेंसर बहु-आयामी डेटा (multidimensional data) को दर्शाने के लिए आवश्यक हैं, और लो-रैंक फैक्टराइजेशन (जैसे Tucker और Hierarchical Tucker) छिपी हुई संरचनाओं को उजागर करने और डेटा को संकुचित करने के लिए अत्यंत महत्वपूर्ण हैं। हालाँकि, उच्च-आयामी टेंसरों के लिए इन डिकम्पोज़िशन को कंप्यूट करना दो प्रमुख बाधाओं का सामना करता है:

गणना लागत (Computational Cost): पारंपरिक एल्गोरिदम (जैसे High-Order SVD या HOSVD) को बड़े टेंसर मैट्रिसाइजेशन (टेंसर को मैट्रिक्स में बदलना/unfolding) पर सिंगुलर वैल्यू डिकम्पोज़िशन (SVD) की गणना करने की आवश्यकता होती है। इन मैट्रिसेस का आकार मोड ( $d$ ) के साथ तेजी से बढ़ता है, जिससे अत्यधिक गणनात्मक जटिलता ( $O(d n^{d+1})$ ) उत्पन्न होती है।
मेमोरी की मांग (Memory Demand): इन SVDs को करने के लिए, मानक एल्गोरिदम को पूर्ण टेंसर मैट्रिसाइजेशन को असेंबल करने की आवश्यकता होती है। एक एकल मैट्रिसाइजेशन को स्टोर करने के लिए अक्सर मूल टेंसर के बराबर मेमोरी की आवश्यकता होती है। यह मोड-पैरेलल (mode-parallel) कार्यान्वयन (जहाँ अलग-अलग नोड्स पर विभिन्न मोड के साथ संचालन किया जाता है) को अव्यवहारिक बनाता है, क्योंकि प्रत्येक नोड को डेटा की एक पूर्ण प्रति स्टोर करने की आवश्यकता होगी।

मौजूदा रैंडमाइज्ड दृष्टिकोण (जैसे R-HOSVD) रैंडमाइज्ड SVD (RSVD) का उपयोग करके गणना समय को कम करते हैं, लेकिन वे अभी भी पूर्ण मैट्रिसाइजेशन बनाने की आवश्यकता रखते हैं, जिससे मोड-पैरेलल निष्पादन के लिए मेमोरी बाधा का समाधान नहीं हो पाता है।

2. कार्यप्रणाली (Methodology)

लेखक एक नया ढांचा प्रस्तावित करते हैं जो फाइबर सैंपलिंग (fiber sampling) और रैंडमाइज्ड रेंज-फाइंडिंग (randomized range-finding) को जोड़ता है ताकि पूर्ण टेंसर मैट्रिसाइजेशन बनाए बिना वास्तविक मोड-पैरेलल डिकम्पोज़िशन सक्षम किया जा सके।

A. Tucker डिकम्पोज़िशन के लिए सबसैम्प्ड रैंडमाइज्ड HOSVD (Sub-R-HOSVD)

प्रत्येक मोड $k$ के लिए पूर्ण मोड- $k$ अनफोल्डिंग $X^{(k)}$ के SVD की गणना करने के बजाय, एल्गोरिदम इस प्रकार आगे बढ़ता है:

फाइबर सैंपलिंग (Fiber Sampling): $X^{(k)}$ को बनाने के बजाय, एल्गोरिदम सीधे टेंसर $X$ से $s_k$ फाइबर (अनफोल्डिंग के कॉलम) को रैंडमली चुनता है। यह एक छोटा मैट्रिक्स $Y_k \in \mathbb{R}^{n_k \times s_k}$ बनाता है जहाँ $s_k \ll \prod_{j \neq k} n_j$ है।
रैंडमाइज्ड रेंज-फाइंडिंग (Randomized Range-Finding): पूर्ण अनफोल्डिंग $X^{(k)}$ के कॉलम स्पेस के करीब एक ऑर्थोनॉर्मल बेसिस $U_k$ की गणना करने के लिए $Y_k$ पर एक गॉसियन स्केच मैट्रिक्स $\Omega_k$ लागू किया जाता है।
कोर कंप्यूटेशन (Core Computation): एक बार सभी फैक्टर मैट्रिसेस $\{U_k\}$ की गणना हो जाने के बाद, कोर टेंसर $S$ को टेंसर-टाइम्स-मैट्रिक्स (TTM) उत्पादों के माध्यम से प्राप्त किया जाता है।

मुख्य नवाचार: $X^{(k)}$ के निर्माण से बचकर, मेमोरी की आवश्यकता पूर्ण टेंसर को स्टोर करने से घटकर केवल फाइबर के एक छोटे उपसमुच्चय (subset) को स्टोर करने तक रह जाती है। यह एक समानांतर सेटिंग में प्रत्येक कम्प्यूटेशनल नोड को डेटा की पूर्ण प्रति की आवश्यकता के बिना, एक अलग मोड को स्वतंत्र रूप से संभालने की अनुमति देता है।

B. H-Tucker डिकम्पोज़िशन के लिए सबसैम्प्ड रैंडमाइज्ड RtL-HT

लेखक इस तर्क को Hierarchical Tucker (H-Tucker) फॉर्मेट, विशेष रूप से रूट-टू-लीव्स (RtL) एल्गोरिदम के लिए विस्तारित करते हैं:

लीफ फैक्टर्स (Leaf Factors): लीफ फैक्टर मैट्रिसेस की गणना ऊपर वर्णित Sub-R-HOSVD विधि का उपयोग करके की जाती है।
इंटरनल नोड्स (Internal Nodes): डायमेंशन ट्री के इंटरनल नोड्स के लिए, एल्गोरिदम उस विशिष्ट मोड सेट के अनुरूप फाइबर को सैंपल करता है, एक छोटा मैट्रिक्स बनाता है, और बेसिस को अनुमानित करने के लिए रैंडमाइज्ड रेंज-फाइंडर लागू करता है।
ट्रांसफर टेंसर (Transfer Tensors): पैरेंट (parent) और चाइल्ड (child) नोड्स के अनुमानित बेसिस के बीच ट्रांसफर टेंसरों की गणना की जाती है।

3. मुख्य योगदान (Key Contributions)

वास्तविक मोड-पैरेललिज्म (True Mode-Parallelism): यह पेपर Tucker और H-Tucker डिकम्पोज़िशन का पहला व्यावहारिक मोड-पैरेलल कार्यान्वयन प्रस्तुत करता है जिसे पूर्ण टेंसर को स्टोर करने की आवश्यकता नहीं है। यह पूर्ण मैट्रिसाइजेशन की आवश्यकता को समाप्त करके प्राप्त किया गया है।
सबसैंपलिंग रणनीति (Subsampling Strategy): एक फाइबर सैंपलिंग चरण का परिचय जो डेटा को मैट्रिक्स में पुनर्व्यवस्थित करने की महंगी प्रक्रिया को दरकिनार करता है।
सैद्धांतिक त्रुटि सीमाएं (Theoretical Error Bounds): लेखक Sub-R-HOSVD एल्गोरिदम के लिए कठोर संभाव्यता त्रुटि सीमाएं (probabilistic error bounds) व्युत्पन्न करते हैं। वे सिद्ध करते हैं कि अनुमान की अपेक्षित त्रुटि ओवरसैंपलिंग पैरामीटर और टेंसर के रो-स्पेस (row space) की कोहेरेंस (coherence) पर निर्भर एक कारक द्वारा सीमित है, जो मानक रैंडमाइज्ड SVD सीमाओं के समान है।
स्केलेबिलिटी (Scalability): यह विधि विशेष रूप से हाई-परफॉर्मेंस कंप्यूटिंग (HPC) वातावरण के लिए डिज़ाइन की गई है, जो मजबूत स्केलिंग गुणों को प्रदर्शित करती है।

4. संख्यात्मक परिणाम (Numerical Results)

लेखकों ने Leonardo HPC सिस्टम (Intel Xeon CPUs और NVIDIA A100 GPUs) का उपयोग करके सिंथेटिक डेटा और वास्तविक दुनिया के डेटासेट (COIL-100 इमेज और मौसम संबंधी डेटा) पर अपनी विधियों का मूल्यांकन किया।

सटीकता (Accuracy): Sub-R-HOSVD और Sub-R-RtL-HT एल्गोरिदम डिटर्मिनिस्टिक विधियों (HOSVD, ST-HOSVD) और अन्य रैंडमाइज्ड बेसलाइन्स (R-HOSVD, SI-HOSVD) के तुलनीय अनुमान त्रुटि प्राप्त करते हैं।
गति (Speed): प्रस्तावित विधियाँ लगातार स्टेट-ऑफ-द-आर्ट रैंडमाइज्ड तकनीकों की तुलना में एक क्रम (one order of magnitude) तेज़ हैं।
- $d=8$ वाले सिंथेटिक टेंसरों के लिए, विधि ने $10\times$ या उससे अधिक की स्पीडअप प्राप्त की।
- उल्लेखनीय रूप से, यह विधि बिना किसी महत्वपूर्ण सटीकता हानि के अत्यंत छोटे सैंपलिंग पैरामीटर (उदाहरण के लिए, डेटा कॉलम के केवल 0.00005% का उपयोग करके) के साथ काम करती है।
पैरेलल स्केलिंग (Parallel Scaling):
- Tucker: जब प्रक्रियाओं (processes) की संख्या को 1 से बढ़ाकर 8 किया गया, तो विधि ने उत्कृष्ट स्ट्रॉन्ग स्केलिंग (लगभग रैखिक स्पीडअप) दिखाई। सीरियल घटक (अंतिम TTM) नगण्य था।
- H-Tucker: हालांकि RtL दृष्टिकोण सभी SVD के समानांतर कंप्यूटेशन की अनुमति देता है, लेखकों ने नोट किया कि लोड बैलेंसिंग (load balancing) महत्वपूर्ण है। रूट ट्रांसफर टेंसर का सीरियल निर्माण और विभिन्न ट्री स्तरों पर SVD की बदलती लागत, यदि सावधानीपूर्वक प्रबंधित न की जाए, तो स्पीडअप को सीमित कर सकती है। फाइबर इंडेक्स जनरेशन को समानांतर करने से प्रदर्शन में और सुधार हुआ।
मेमोरी दक्षता (Memory Efficiency): दृष्टिकोण मेमोरी फुटप्रिंट को नाटकीय रूप से कम करता है, जिससे उन नोड्स पर उच्च-क्रम टेंसरों का डिकम्पोज़िशन संभव हो जाता है जो पूर्ण मैट्रिसाइजेशन को धारण नहीं कर सकते।

5. महत्व (Significance)

यह कार्य टेंसर न्यूमेरिकल लीनियर अल्जेब्रा में एक महत्वपूर्ण बाधा को संबोधित करता है: समानांतरता (parallelism) और मेमोरी खपत के बीच का समझौता।

व्यावहारिक प्रभाव: यह विशाल, उच्च-आयामी डेटासेट्स के डिकम्पोज़िशन को आधुनिक HPC क्लस्टर्स पर सक्षम बनाता है जहाँ मेमोरी प्राथमिक बाधा है।
एल्गोरिद्मिक बदलाव: यह प्रतिमान को "एक पूर्ण मैट्रिक्स के SVD को रैंडमाइज करने" से बदलकर "पहले डेटा को सैंपल करें, फिर रैंडमाइज करें" की ओर ले जाता है, जो वितरित मेमोरी सिस्टम के लिए अधिक कुशल है।
भविष्य की दिशाएं: लेखक एक परिमित परिशुद्धता विश्लेषण (finite precision analysis) की आवश्यकता की पहचान करते हैं ताकि यह समझाया जा सके कि उनकी त्रुटि संचय (error accumulation) डिटर्मिनिस्टिक विधियों की तुलना में आयाम $d$ के साथ बेहतर तरीके से क्यों स्केल करती है, और वे रैंडमाइज्ड H-Tucker योजना के औपचारिक त्रुटि विश्लेषण का आह्वान करते हैं, जो एक खुला चुनौती बना हुआ है।

संक्षेप में, यह पेपर टेंसर डिकम्पोज़िशन के लिए एक मजबूत, मेमोरी-कुशल और अत्यधिक स्केलेबल समाधान प्रदान करता है, जिससे उच्च-आयामी समस्याओं के लिए उन्नत डेटा विश्लेषण संभव हो जाता है जिन्हें पहले कम्प्यूटेशनल रूप से अव्यवहार्य माना जाता था।