तकनीकी सारांश: मैनिफोल्ड्स पर रिमैनियन निस्ट्रॉम सन्निकटन (Riemannian Nyström Approximation)

1. समस्या विवरण

मशीन लर्निंग और सिग्नल प्रोसेसिंग में कई बड़े पैमाने की समस्याएं स्वाभाविक रूप से मैनिफोल्ड बाधाओं (manifold constraints) के साथ निर्मित होती हैं। जबकि मैनिफोल्ड संरचना जटिल ज्यामिति के सटीक मॉडलिंग की अनुमति देती है, स्पर्श रेखा स्थान (tangent spaces) पर संबद्ध रैखिक बीजगणितीय संचालन अक्सर कम्प्यूटेशनल बाधा बन जाते हैं, विशेष रूपकर उच्च-आयामी परिदृश्यों में।

विशेष रूप से, रिमैनियन मैनिफोल्ड्स पर पुनरावृत्ति विधियों (iterative methods) को अक्सर एक स्पर्श रेखा-संयोजक ऑपरेटर $H_x: T_xM \to T_xM$ (आमतौर पर स्व-संयोजक और धनात्मक अर्ध-निश्चित, जैसे कि रिमैनियन हेसियन) का निर्माण करने और उसके व्युत्क्रम या छद्म-व्युत्क्रम (pseudoinverse) की गणना करने की आवश्यकता होती है। उदाहरणों में न्यूटन-प्रकार के अनुकूलन के लिए रैखिक प्रणालियों को हल करना और सहप्रसरण टेंसर (covariance tensors) पर प्रिंसिपल जियोडेसिक एनालिसिस (PGA) करना शामिल है। इन ऑपरेटरों को स्पष्ट रूप से बनाना और उनका व्युत्क्रम निकालना अक्सर निषेधात्मक या अव्यवहार्य होता है। मौजूदा तकनीकें, जैसे कि स्पेक्ट्रल ट्रंकेशन, मल्टीग्रिड सॉल्वर, और रिमैनियन क्वासी-न्यूटन विधियाँ, इसे कम करने का प्रयास करती हैं लेकिन यह प्रश्न उठाती हैं कि क्या एक कुशल सन्निकटन का निर्माण किया जा सकता है जिसके पास सिद्ध त्रुटि सीमाएँ हों जो ऑपरेटर के अंतर्निहित ज्यामितीय गुणों को सुरक्षित रखे।

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

2.1 रिमैनियन निस्ट्रॉम सन्निकटन (Riemannian Nyström Approximation)

लेखक एक $d$-आयामी रिमैनियन मैनिफोल्ड $(M, g)$ पर स्व-संयोजक धनात्मक अर्ध-निश्चित (PSD) ऑपरेटरों के लिए एक समन्वय-मुक्त (coordinate-free) रिमैनियन निस्ट्रॉम सन्निकटन प्रस्तावित करते हैं।

एक बिंदु $x \in M$ और एक ऑपरेटर $H_x$ दिया गया है, सन्निकटन $\hat{H}_{x, B, \Xi}$ को दो $\ell$-आयामी उप-स्थानों $B, \Xi \subset T_xM$ और एक पूर्ण-रैंक रैखिक मानचित्र $F: B \to \Xi$ का उपयोग करके निर्मित किया जाता है (जहाँ $\ell \leq d$)।

1. स्केचिंग ऑपरेटर (Sketching Operator): एक स्केचिंग ऑपरेटर $P_{x, B, \Xi}: T_xM \to T_xM$ को $P_{x, B, \Xi}[v] = F \Pi_B [v]$ के रूप में परिभाषित किया गया है, जहाँ $\Pi_B$ $B$ पर लंबवत प्रक्षेप (orthogonal projection) है। इसका एडजॉइंट (adjoint) $P^*_{x, B, \Xi}[u] = F^* \Pi_\Xi [u]$ है।
2. सन्निकटन सूत्र: रिमैनियन निस्ट्रॉम सन्निकटन को इस प्रकार परिभाषित किया गया है:
   $$\hat{H}_{x, B, \Xi}[u] = \left( H_x P_{x, B, \Xi} (P^*_{x, B, \Xi} H_x P_{x, B, \Xi})^\dagger P^*_{x, B, \Xi} H_x \right)[u]$$
   जहाँ $(\cdot)^\dagger$ मूर-पेनरोज़ छद्म-व्युत्क्रम (Moore–Penrose pseudoinverse) को दर्शाता है। यह सूत्रीकरण प्रभावी रूप से रैखिक प्रणाली को निम्न-आयामी उप-स्थान $B$ में संकुचित करता है, वहां इसे हल करता है, और परिणाम को वापस स्पर्श रेखा स्थान में ले जाता है।

2.2 स्केचिंग स्थितियाँ (Sketching Conditions)

अनियमित त्रुटि विश्लेषण को सक्षम करने के लिए, पेपर दो स्केचिंग स्थितियों को पेश करता है:

• गौसियन स्केचिंग (Gaussian Sketching): यूक्लिडियन मामले के समान, जहाँ मानचित्र $F$ आंतरिक गुणनों (inner products) पर एक गौसियन वितरण प्रेरित करता है।
• हार-ग्रासम स्केचिंग (Haar–Grassmann Sketching): एक नवीन, अंतर्निहित स्थिति जो किसी विशिष्ट समन्वय प्रणाली पर निर्भर किए बिना सीधे ज्यामिति के संदर्भ में परिभाषित है। इसके लिए आवश्यक है:
  1. उप-स्थान $\Xi$ ग्रासमैन मैनिफोल्ड $\text{Gr}(\ell, T_xM)$ पर हार-समान (Haar-uniform) हो।
  2. $F$ के पोलर अपघटन (polar decomposition) का सममितीय घटक (isometric component) $B$ और $\Xi$ के बीच हार-समान रैखिक सममितियों के सेट पर हो।
  3. $F$ के रेडियल कारक (radial factor) को विशिष्ट मोमेंट बाउंड्स (moment bounds) को संतुष्ट करना चाहिए।

इस स्थिति को परिवहन-संगत (transport-compatible) सिद्ध किया गया है: यदि एक स्केचिंग ऑपरेटर $x$ पर हार-ग्रासम स्थिति को संतुष्ट करता है, तो एक सममितीय वेक्टर परिवहन (isometric vector transport) के माध्यम से इसे निकटतम बिंदु $x'$ पर ले जाने पर भी यह स्थिति बनी रहती है। यह अनुकूलन एल्गोरिदम में "लेज़ी रिफ्रेश" (lazy refresh) रणनीतियों के उपयोग की अनुमति देता है जहाँ स्केच को हर चरण में पुन: उत्पन्न करने के बजाय उसे ट्रांसपोर्ट किया जाता है।

2.3 अनुकूलन एल्गोरिदम (Optimization Algorithm)

लेखक एक रैंडमाइज्ड रिमैनियन निस्ट्रॉम क्यूबिक न्यूटन (RRNCN) विधि प्रस्तावित करते हैं।

• रिमैनियन हेसियन $H_x$ को इसके निस्ट्रॉम सन्निकटन $\hat{H}_{x, B, \Xi}$ द्वारा प्रतिस्थापित किया जाता है।
• खोज दिशा (search direction) को उप-स्थान $B$ में एक संक्षिप्त रैखिक प्रणाली को हल करके कंप्यूट किया जाता है।
• वैश्विक अभिसरण (global convergence) सुनिश्चित करने के लिए, यह विधि क्यूबिक रेगुलराइजेशन को शामिल करती है, जो इस प्रकार के उप-समस्या को हल करती है:
  $$\min_{v \in B} \left( \langle h, v \rangle_x + \frac{1}{2}\langle J[v], v \rangle_x + \frac{\sigma}{6}\|v\|_x^3 \right)$$
  जहाँ $h$ और $J$ स्केच्ड ग्रेडिएंट और हेसियन घटक हैं।

3. मुख्य योगदान

1. अंतर्निहित निर्माण (Intrinsic Construction): एक समन्वय-मुक्त रिमैनियन निस्ट्रॉम सन्निकटन का विकास जो धनात्मक अर्ध-निश्चितता (PSD), स्व-संयोजकता और लोएनर ऑर्डर मोनोटोनिसिटी (Loewner order monotonicity) सहित मौलिक ऑपरेटर गुणों को सुरक्षित रखता है।
2. हार-ग्रासम स्केचिंग (Haar–Grassmann Sketching): एक ज्यामितीय स्केचिंग स्थिति का परिचय जो मैनिफोल्ड्स पर गौसियन स्केचिंग का सामान्यीकरण करती है। यह स्थिति अंतर्निहित, समन्वय-मुक्त है और सममितीय वेक्टर परिवहन के साथ संगत है, जो मैनिफोल्ड्स पर कैनोनिकल निर्देशांकों की कमी को संबोधित करती है।
3. सन्निकटन त्रुटि सीमाएँ (Approximation Error Bounds): ऑपरेटर नॉर्म में स्पेक्ट्रल सन्निकटन त्रुटि सीमाओं की स्थापना। हार-ग्रासम स्थिति के तहत, अपेक्षित त्रुटि $H_x$ के आइजन मानों (eigenvalues) और स्केच आकार $\ell$ के एक फलन द्वारा सीमित है। विशेष रूप रूप से, त्रुटि स्पेक्ट्रम की पूंछ (tail) और ऑपरेटर के "स्थिर रैंक" (stable rank) पर निर्भर करती है।
4. परिवहन संगतता (Transport Compatibility): यह प्रमाण कि हार-ग्रासम स्थिति सममितीय वेक्टर परिवहन के तहत संरक्षित रहती है, जो स्केचिंग संरचनाओं के कुशल पुन: उपयोग को सक्षम बनाती है, जिससे अनुकूलन एल्गोरिदम में कम्प्यूटेशनल ओवरहेड कम होता है।
5. अनुकूलन ढांचा (Optimization Framework): एक प्रस्तावित रैंडमाइज्ड न्यूटन-प्रकार की विधि जो रिमैनियन निस्ट्रॉम सन्निकटन का उपयोग करती है, जो वैश्विक जटिलता विश्लेषण ($O(d/(\ell \epsilon))$) और स्ट्रॉन्ग जियोडेसिक कॉनवेक्सिटी के तहत स्थानीय रैखिक अभिसरण दर के साथ आती है।

4. परिणाम

पेपर प्रस्तावित कार्यप्रणाली को SPD और ग्रासमैन मैनिफोल्ड्स पर संख्यात्मक प्रयोगों के माध्यम से मान्य करता है।

• प्रिंसिपल जियोडेसिक एनालिसिस (PGA): HDM05 डेटासेट (आकार $93 \times 93$ की SPD मैट्रिसेस) पर प्रयोगों से पता चलता है कि निस्ट्रॉम सन्निकटन डाउनस्ट्रीम सांख्यिकीय प्रदर्शन को बनाए रखता है।
  • सटीकता: मल्टीक्लास क्लासिफिकेशन सटीकता (लॉजिस्टिक्स रिग्रेशन, SVM, और MLP का उपयोग करके) और हॉटलिंग्स $T^2$ सांख्यिकी, स्केच आकार $\ell \in \{20, 40, 80\}$ के लिए सटीक PGA के तुलनीय बनी रही।
  • दक्षता: विधि ने मेमोरी उपयोग को काफी कम कर दिया, जिसमें सटीक ऑपरेटर से जुड़े मेमोरी वृद्धि का केवल 4.30%–9.64% ही आवश्यक था, जबकि प्रतिस्पर्धी सांख्यिकीय गुणवत्ता बनाए रखी।
• SPD मैनिफोल्ड्स पर अनुकूलन: सहप्रसरण अनुमान (covariance estimation) के लिए एक जियोडेसिक रूप से उत्तल (geodesically convex) अनुकूलन समस्या पर प्रयोगों ने दिखाया कि मध्यम स्केच आकार (जैसे, $\ell=80$) सन्निकटन की गुणवत्ता और प्रति-इटरेशन कम्प्यूटेशनल लागत के बीच सबसे अच्छा संतुलन प्रदान करते हैं, जिससे सटीक क्यूबिक न्यूटन विधि की तुलना में वॉल-क्लॉक समय में तेज़ अभिसरण प्राप्त हुआ।
• ग्रासमैन मैनिफोल्ड्स पर ट्रांसपोर्टेड स्केचिंग: ग्रासमैन मैनिफोल्ड ($n=20000, p=20$) पर प्रयोगों ने प्रदर्शित किया कि ट्रांसपोर्टेड स्केचिंग का उपयोग करने से (प्रत्येक 2-3 इटरेशन में रिफ्रेश करना) पूरी तरह से रिफ्रेश किए गए निस्ट्रॉम विधि के लगभग समान इटरेशन अभिसरण प्राप्त हुआ, लेकिन इसने हर चरण में स्केच को पुन: उत्पन्न करने की लागत से बचकर महत्वपूर्ण रनटाइम स्पीड-अप प्रदान किया।

5. महत्व और दावे

पेपर दावा करता है कि यह शास्त्रीय यूक्लिडियन निस्ट्रॉम सिद्धांत को स्पर्श रेखा-ऑपरेटरों (tangent-space operators) के रिमैनियन मैनिफोल्ड सेटिंग में विस्तारित करता है। इसका प्राथमिक महत्व यह है कि यह एक अंतर्निहित रूप से निर्मित निम्न-रैंक सन्निकटन तकनीक प्रदान करता है, जो ज्यामितीय संरचना (PSD गुण, स्व-संयोजकता) को सुरक्षित रखता है और एक ज्यामितीय रूप से प्राकृतिक स्केचिंग स्थिति (हार-ग्रासम) के तहत सिद्ध सन्निकटन त्रुटियां प्रदान करता है।

लेखक इस बात पर जोर देते हैं कि यह दृष्टिकोण पूर्ण ऑपरेटर बनाए बिना कुशल स्पर्श रेखा-ऑपरेटरों और उनके व्युत्क्रमों की गणना की अनुमति देता है, जिससे उच्च-आयामी मैनिफोल्ड अनुकूलन और विश्लेषण (जैसे PGA) कम्प्यूटेशनल रूप से व्यवहार्य हो जाता है। स्केचिंग स्थिति की परिवहन संगतता (transport compatibility) एक प्रमुख सक्षमकर्ता के रूप में उजागर की गई है, जो इटरेशन के दौरान स्केचिंग संरचनाओं के कुशल पुन: उपयोग को सक्षम करती है, जिससे सैद्धांतिक गारंटियों को बनाए रखते हुए कम्प्यूटेशनल ओवरहेड कम होता है। यह कार्य रैंडमाइज्ड लीनियर अल्जेब्रा और रिमैनियन ऑप्टिमाइजेशन के बीच के अंतर को पाटता है, जो सटीक सेकंड-ऑर्डर विधियों के लिए एक स्केलेबल विकल्प प्रदान करता है।