तकनीकी सारांश: लो-रैंक डिस्ट्रीब्यूशनल मैट्रिक्स कंप्लीशन

समस्या की परिभाषा

यह शोध पत्र डिस्ट्रीब्यूशनल मैट्रिक्स कंप्लीशन की समस्या को संबोधित करता है, जो शास्त्रीय लो-रैंक मैट्रिक्स कंप्लीशन कार्य का एक सामान्यीकरण है। इस सेटिंग में, लक्षित मैट्रिक्स $\rho^* \in \mathcal{P}(\mathcal{X})^{m_1 \times m_2}$ के प्रविष्टियों (entries) में एक डोमेन $\mathcal{X}$ पर आधारित प्रायिकता वितरण (probability distributions) होते हैं, न कि स्केलर मान।

अवलोकन मॉडल दो स्तरों की अपूर्णता द्वारा अभिलक्षित है:

1. आंशिक अवलोकन (Partial Observation): केवल मैट्रिक्स प्रविष्टियों का एक उपसमुच्चय ही देखा जाता है, जिसे एक बाइनरी मास्क $T(i,j)$ द्वारा दर्शाया गया है।
2. अप्रत्यक्ष अवलोकन (Indirect Observation): देखी गई प्रविष्टियों के लिए भी, अंतर्निहित वितरण $\rho^*(i,j)$ सीधे सुलभ नहीं होता है। इसके बजाय, एक i.i.d. नमूनों का एक सीमित सेट $\{X^{(ij)}_1, \dots, X^{(ij)}_{N_{ij}}\}$ देखा जाता है, जो $\rho^*(i,j)$ से लिए गए हैं, जहाँ नमूना आकार $N_{ij}$ विभिन्न प्रविष्टियों के लिए भिन्न हो सकता है।

लक्ष्य पूर्ण वितरण-मूलित मैट्रिक्स $\rho^*$ (या उसके प्रतिनिधित्व) को इन आंशिक और अप्रत्यक्ष अवलोकनों से पुन: प्राप्त करना है। यह समस्या ट्रैफ़िक प्रवाह की परिवर्तनशीलता को मॉडल करने या विभिन्न वित्तीय तिमाहियों और संस्थानों के बीच आय पूर्वानुमानों के वितरण का विश्लेषण करने जैसे अनुप्रयोगों में उत्पन्न होती है।

कार्यप्रणाली

कर्नेल मीन एम्बेडिंग्स (KME)

अनंत-आयामी प्रायिकता वितरणों को संभालने और घनत्व फलनों (density functions) से जुड़े मैनिफोल्ड बाधाओं से बचने के लिए, लेखक प्रत्येक वितरण $\rho^*(i,j)$ को एक रिप्रोड्यूसिंग कर्नेल हिल्बर्ट स्पेस (RKHS) $\mathcal{H}$ में अपने कर्नेल मीन एम्बेडिंग (KME) के माध्यम से निरूपित करते हैं:
$$\mu^*(i, j, \cdot) = \mathbb{E}_{X \sim \rho^*(i,j)} [K(X, \cdot)] \in \mathcal{H}$$
$\rho^*$ को पुन: प्राप्त करना KME मैट्रिक्स $\mu^* \in \mathcal{H}^{m_1 \times m_2}$ को पुन: प्राप्त करने के समतुल्य है। वितरणों के बीच की दूरी को मैक्सिमम मीन डिसक्रेपेंसी (MMD) का उपयोग करके मापा जाता है।

फंकशनल अनफोल्डिंग के माध्यम से लो-रैंक मॉडलिंग

लेखक वितरण-मूलित मैट्रिक्स के लिए एक टकर रैंक (Tucker rank) संरचना का प्रस्ताव करते हैं। वे $\mu^*$ को $\mathbb{R}^{m_1} \otimes \mathbb{R}^{m_2} \otimes \mathcal{H}$ स्पेस में एक थ्री-वे टेंसर के रूप में देखते हैं। चूंकि $\mathcal{H}$ अक्सर अनंत-आयामी होता है, इसलिए मानक टेंसर रैंक परिभाषाएँ सीधे लागू नहीं होती हैं।

इस समस्या के समाधान के लिए, शोध पत्र फंकशनल अनफोल्डिंग ऑपरेटर्स ($U_1, U_2, U_3$) पेश करता है जो टेंसर को दो स्पेस के उत्पादों में मैप करते हैं (जैसे, $U_1: \mathbb{R}^{m_1} \otimes \mathbb{R}^{m_2} \otimes \mathcal{H} \to \mathbb{R}^{m_1} \otimes (\mathbb{R}^{m_2} \otimes \mathcal{H})$)। ये ऑपरेटर्स रैखिक ऑपरेटरों को प्रेरित करते जिनके रैंक मल्टीलीनर रैंक $(r_1, r_2, r_3)$ को परिभाषित करते हैं।

• संरचनात्मक निहितार्थ: एक लो मल्टीलीनर रैंक यह दर्शाता है कि KMEs के फंकशनल घटक एक निम्न-आयामी उप-स्थान (subspace) में स्थित हैं, और संबंधित एक्सपेक्टेशन फंकशनल मैट्रिसेस (जैसे, मीन मैट्रिसेस) लो-रैंक हैं।

अनुमान ढांचा (Estimation Framework)

लेखक एक नियमितकृत M-एस्टीमेटर $\hat{\mu}$ का प्रस्ताव करते हैं जिसे लॉस फंक्शन और न्यूक्लियर-नोम पेनल्टी को मिनिमाइज़ करके परिभाषित किया जाता है:
$$\hat{\mu} = \arg\min_{\mu} \left[ \frac{1}{m_1 m_2} \sum_{(i,j): T(i,j)=1} \left\| \mu(i, j, \cdot) - \hat{\mu}_{emp}(i, j, \cdot) \right\|_{\mathcal{H}}^2 + \lambda \Psi(\mu) \right]$$

• लॉस टर्म: अनुमानित KME और देखे गए नमूनों से प्राप्त एम्पिरिकल KME के बीच का स्क्वेर्ड MMD।
• नियमितीकरण (Regularization): $\Psi(\mu) = \sum_{j=1}^3 \beta_j \|U_j \mu\|_*$, जहाँ $\|\cdot\|_*$ प्रेरित रैखिक ऑपरेटर के न्यूक्लियर नोर्म को दर्शाता है। यह तीनों मोड्स में लो-रैंकनेस को बढ़ावा देता है।

कम्प्यूटेशनल समाधान

$\mathcal{H}$ की अनंत-आयामी प्रकृति के बावजूद, रिप्रेजेंटर थ्योरम (Representer Theorem) यह सुनिश्चित करता है कि समाधान $\hat{\mu}$ देखे गए कर्नेल फलनों के परिमित-आयामी स्पैन (span) में स्थित है।

1. समस्या को एक कोएफिशिएंट टेंसर $B \in \mathbb{R}^{m_1 \times m_2 \times \tilde{N}}$ पर आधारित परिमित-आयामी टेंसर ऑप्टिमाइज़ेशन समस्या में पुन: पैरामीटराइज़ किया गया है।
2. बड़े नमूना आकार को संभालने के लिए, लेखक कर्नेल एप्रोक्सिमेशन तकनीकों (जैसे, न्यस्ट्रॉम विधि या रैंडम फूरियर फीचर्स) का उपयोग करके ग्राम मैट्रिक्स को अनुमानित करने का सुझाव देते हैं।
3. अनुकूलित एल्टरनेटिंग डायरेक्शन मेथड ऑफ मल्टीप्लायर्स (ADMM) का उपयोग करके अनुकूलन (optimization) को हल किया जाता है।

मुख्य योगदान

1. नवीन समस्या सूत्रीकरण: शोध पत्र वितरण-मूलित प्रविष्टियों के लिए मैट्रिक्स कंप्लीशन को औपचारिक रूप देता है, जो आंशिक और शोर वाले नमूना डेटा से वितरणों को पुन: प्राप्त करने की चुनौती को संबोधित करता है।
2. सैद्धांतिक ढांचा: यह फंकशनल अनफोल्डिंग ऑपरेटर्स का उपयोग करके वितरण-मूलित टेंसरों के लिए टकर रैंक परिभाषा पेश करता है, जो अनंत-आयामी फंकशनल डेटा और परिमित-आयामी टेंसर विश्लेषण के बीच के अंतर को पाटता है।
3. एल्गोरिदमिक नवाचार: प्रस्तावित एस्टीमेटर प्रेरित रैखिक ऑपरेटरों पर न्यूक्लियर-नोम रेगुलराइजेशन का उपयोग करता है। महत्वपूर्ण रूप से, लेखक सिद्ध करते हैं कि समाधान एक परिमित-आयामी प्रतिनिधित्व रखता है, जिससे यह कॉनवेक्स ऑप्टिमाइज़ेशन के माध्यम से कम्प्यूटेशनल रूप से व्यवहार्य हो जाता है।
4. सांख्यिकीय गारंटी: शोध पत्र एग्रीगेट स्क्वेर्ड MMD के लिए नॉन-एसिम्प्टोटिक एरर बाउंड्स स्थापित करता है।
   • अभिसरण दर (convergence rate) शास्त्रीय न्यूक्लियर-नोम रेगुलराइज्ड मैट्रिक्स कंप्लीशन (स्केलर मैट्रिसेस के लिए) के समान है।
   • मौजूदा निकटतम-पड़ोसी (nearest-neighbor) दृष्टिकोणों (जैसे, Feitelberg et al., 2024) के विपरीत, प्रस्तावित विधि की कंसिस्टेंसी के लिए प्रति प्रविष्टि नमूनों की संख्या ($N_{ij}$) के बढ़ने की आवश्यकता नहीं है। इसके बजाय, कंसिस्टेंसी मैट्रिक्स आयामों ($m_1, m_2$) के बढ़ने के साथ प्राप्त की जाती है, जो सूचना साझा करने के लिए वैश्विक लो-रैंक संरचना का लाभ उठाती है।

प्रयोगात्मक परिणाम

सिंथेटिक डेटा

• सेटअप: गाऊसी मिश्रण वितरण (Gaussian mixture distributions) के साथ सिम्युलेटेड मैट्रिसेस। तुलना एक निकटतम-पड़ोसी (NN) विधि (Feitelberg et al., 2024) और शास्त्रीय मैट्रिक्स कंप्लीशन (SOFTIMPUTE) के विरुद्ध की गई, जिसे नमूना माध्य/विचलन पर लागू किया गया था।
• निष्कर्ष:
  • प्रस्तावित विधि (LRKME) ने देखे गए और अनदेखे दोनों प्रविष्टियों में NN विधि की तुलना में लगातार बेहतर प्रदर्शन किया, विशेष रूप से वेरिएंस और उच्च-क्रम सांख्यिकी (higher-order statistics) का अनुमान लगाने में।
  • LRKME ने SOFTIMPUTE से भी बेहतर प्रदर्शन किया, जो केवल स्केलर सारांशों के बजाय पूर्ण वितरण संबंधी जानकारी का उपयोग करने के लाभ को प्रदर्शित करता है।
  • 2D सेटिंग्स में, मल्टीवेरिएट वासरस्टीन दूरियों की कम्प्यूटेशनल जटिलता के कारण NN विधि को बाहर रखा गया था, जबकि LRKME प्रभावी बना रहा।

वास्तविक दुनिया का अनुप्रयोग

• डेटासेट: NYC टैक्सी ट्रिप डेटा, जो 265 स्रोत और गंतव्य स्थानों के बीच दैनिक यात्रा गणना के वितरण को मॉडल करता है।
• चुनौती: उच्च मिसिंग रेट (>39%) और प्रति प्रविष्टि अत्यधिक परिवर्तनशील नमूना आकार (1 से 3672)।
• निष्कर्ष: LRKME ने टेस्ट सेट पर NN विधि (0.0212) की तुलना में काफी कम एम्पिरिकल रिलेटिव एरर (0.0015) प्राप्त किया। विशिष्ट मामलों के विजुअल निरीक्षण ने दिखाया कि LRKME ने SOFTIMPUTE की तुलना में भारी-पूंछ वाले वितरणों (heavy-tailed distributions) और एकाग्रता पैटर्न को बेहतर ढंग से कैप्चर किया।

महत्व और दावे

शोध पत्र का दावा है कि यह पहली ऐसी विधि प्रदान करता है जो:

1. परिवर्तनशील नमूना आकारों के साथ सामान्य अवलोकन पैटर्न को समायोजित करती है।
2. वासरस्टीन-आधारित विधियों की कम्प्यूटेशनल बाधाओं के बिना स्वाभाविक रूप से बहु-आयामी वितरणों तक विस्तारित होती है।
3. वैश्विक कंसिस्टेंसी गारंटी प्रदान करती है जो प्रति प्रविष्टि नमूनों के एसिम्प्टोटिक विकास पर निर्भर नहीं करती, बल्कि मैट्रिक्स की लो-रैंक संरचना पर निर्भर करती है।
4. परिमित-आयामी प्रतिनिधित्व और कॉनवेक्स ऑप्टिमाइज़ेशन के माध्यम से एक कम्प्यूटेशनल रूप से कुशल समाधान प्रदान करती है।

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