🔢 mathematics

Stochastic Zeroth-Order Method for Computing Generalized Rayleigh Quotients

यह शोध पत्र एक स्टोकेस्टिक ज़ीरो-ऑर्डर रीमानियन एल्गोरिदम प्रस्तुत करता है जो बिना एडजॉइंट या मैट्रिक्स इनवर्स ऑपरेशन्स की आवश्यकता के सामान्यीकृत रेले कोटिएंट (generalized Rayleigh quotient) को अधिकतम करता है, जो सैद्धांतिक अभिसरण गारंटी प्रदान करता है और अत्याधुनिक तरीकों की तुलना में बेहतर प्रदर्शन प्रदर्शित करता है।

मूल लेखक: Jonas Bresch, Oleh Melnyk, Martin Schoen, Gabriele Steidl

प्रकाशित 2026-07-14

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

CC BY 4.0

मूल लेखक: Jonas Bresch, Oleh Melnyk, Martin Schoen, Gabriele Steidl

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

कल्पना कीजिए कि आप एक विशाल, धुंधले पर्वत श्रृंखला में सबसे ऊँची चोटी खोजने की कोशिश कर रहे हैं। यह केवल कोई साधारण पहाड़ नहीं है, बल्कि एक गणितीय परिदृश्य है जिसे सामान्यीकृत रेले कोटिएंट (Generalized Rayleigh Quotient) कहा जाता है। संख्याओं की इस दुनिया में, इस शिखर को खोजना इंजीनियरों और वैज्ञानिकों को जटिल समस्याओं को हल करने में मदद करता है, जैसे कि यह पता लगाना कि एक पुल कितना स्थिर है या किसी छवि (image) को सबसे बेहतर तरीके से कैसे कंप्रेस किया जा सकता है।

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

बड़ा विचार: रास्ता महसूस करते हुए ऊपर चढ़ना
इस शोध पत्र के लेखक, जोनास ब्रेश, ओलेह मेलनिक, मार्टिन शोएन और गेब्रिएल स्टीडल ने उस भारी मानचित्र को फेंक देने का निर्णय लिया। इसके बजाय, उन्होंने एक नया प्रकार का पर्वतारोही बनाया: एक स्टोकेस्टिक ज़ीरोथ-ऑर्डर एल्गोरिदम (Stochastic Zeroth-Order Algorithm)।

इस नए पर्वतारोही के बारे में सोचें जो एक ऐसे हाइकर की तरह है जिसे पूरे पहाड़ का दृश्य नहीं दिखता और न ही उसके पास दिशा-सूचक यंत्र (कम्पास) है। वह सीधे ढलान (ग्रेडिएंट) की गणना नहीं कर सकता क्योंकि उसके पास "दर्पण" वाला उपकरण नहीं है। इसके बजाय, उसे महसूस करते हुए ऊपर चढ़ना होगा। वह एक यादृच्छिक (random) दिशा में कदम उठाता है, देखता है कि वह कितनी ऊंचाई पर है, और फिर दूसरी दिशा में कदम उठाता है। इन ऊंचाइयों की तुलना करके, वह बिना सटीक ढलान सूत्र जाने यह अनुमान लगा सकता है कि ऊपर जाने का रास्ता कौन सा है।

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

उन्होंने गणितीय रूप से सिद्ध किया कि यदि आप इसे करते रहते हैं—एक यादृच्छिक रेखा चुनना, उस रेखा पर सबसे अच्छा स्थान खोजना और वहां जाना—तो आप अंततः पहाड़ के बिल्कुल शीर्ष पर पहुँच जाएंगे। वास्तव में, उन्होंने दिखाया कि पर्वतारोही की "चढ़ने की गति" (कैसे त्रुटि कम होती है) एक अनुमानित तरीके से धीमी हो जाती है, लेकिन वे वहाँ पहुँचेंगे ही।

वे क्या नहीं करते (और यह क्यों महत्वपूर्ण है)
यह शोध पत्र बहुत स्पष्ट है कि यह विधि किन चीजों से बचती है। यह स्पष्ट रूप से मैट्रिक्स $B$ के इनवर्स या मैट्रिक्स $A$ के ट्रांसपोज़ का उपयोग नहीं करती है।

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

वे कितने आश्वस्त हैं?
लेखकों ने केवल अनुमान नहीं लगाया; उन्होंने कठिन परिश्रम किया।

सिद्धांत: उन्होंने एक कठोर गणितीय प्रमाण प्रदान किया जिससे यह सिद्ध होता है कि उनका एल्गोरिदम एक निश्चित संभावना के साथ वैश्विक अधिकतम (वास्तविक उच्चतम शिखर) की ओर अभिसरित (converge) होता है। उन्होंने सिद्ध किया कि "ग्रेडिएंट" (यह माप कि आप शिखर के कितने करीब हैं) एक सबलीनियर दर (sublinear rate) पर समाप्त हो जाता है।
सिमुलेशन: उन्होंने विभिन्न आकारों के मैट्रिसेस के साथ कंप्यूटर पर अपने विचार का परीक्षण किया: $d = 10, 50, 100,$ $d = 10, 50, 100,$ और $500$।
- उन्होंने पाया कि अधिक यादृच्छिक नमूनों (मान लीजिए $m=100$ के बजाय $m=1$ ) का उपयोग करने से चढ़ाई बहुत तेज़ और अधिक सटीक हो जाती है।
- उन्होंने अपनी विधि की तुलना अन्य "ज़ीरोथ-ऑर्डर" विधियों (अन्य हाइकर जो महसूस करके ऊपर चढ़ते हैं) से की और पाया कि उनकी विधि काफी बेहतर है।
- उन्होंने एक वास्तविक दुनिया जैसी समस्या पर भी परीक्षण किया जिसे कारकुनें-लवेव समस्या (Karhunen-Loève problem) कहा जाता है (सिग्नल विश्लेषण के लिए उपयोग किया जाता है)। उनके तरीके ने मानक "जेन-ओजा" (Gen-Oja) विधियों की तुलना में बहुत अधिक स्पष्ट समाधान खोजा, जो कई प्रयासों के बाद भी सही आकार खोजने में संघर्ष कर रही थीं।

निष्कर्ष
यह शोध पत्र सुझाव देता है कि यह "महसूस करने वाला" दृष्टिकोण इन जटिल गणितीय परिदृश्यों में उच्चतम बिंदु खोजने का एक शक्तिशाली, कुशल और मजबूत तरीका है। यह केवल सिद्धांत में काम नहीं करता है; कंप्यूटर सिमुलेशन दिखाते हैं कि यह मौजूदा अत्याधुनिक एल्गोरिदम से बेहतर प्रदर्शन करता है, विशेष रूप से तब जब डेटा अव्यवस्थित हो या "दर्पण" गायब हो।

संक्षेप में, यदि आपको सर्वोत्तम समाधान खोजने की आवश्यकता है लेकिन आपके पास ढलान की गणना करने के लिए पूर्ण उपकरण नहीं हैं, तो यह नई विधि आपको एक बार में एक स्मार्ट, यादृच्छिक कदम के साथ शिखर तक पहुँचने में मदद करती है।

तकनीकी सारांश: सामान्यीकृत रेले कोटिएंट (Generalized Rayleigh Quotients) की गणना के लिए स्टोकेस्टिक ज़ीरोथ-ऑर्डर विधि

समस्या विवरण
यह शोध पत्र सामान्यीकृत रेले कोटिएंट के अधिकतमकरण (maximization) को संबोधित करता है, जिसे इस प्रकार परिभाषित किया गया है:
$R(A, B) = \max_{v \in \mathbb{R}^d \setminus \{0\}} \frac{\langle v, Av \rangle}{\langle v, Bv \rangle}$
जहाँ $A \in \mathbb{R}^{d \times d}$ और $B \in \text{Sym}^d_{\succ 0}$ (सिमेट्रिक पॉजिटिव डेफिनिट) है। यह समस्या संख्यात्मक रैखिक बीजगणित (numerical linear algebra) में मौलिक है, जो स्पेक्ट्रल इक्विवेलेंस, सामान्यीकृत सिंगुलर वैल्यू डिकम्पोजिशन, और आंशिक अंतर समीकरणों (PDEs) के स्थिरता विश्लेषण (न्यूमेरिकल अब्सिसा के माध्यम से) में दिखाई देती है।

इस समस्या को हल करने के लिए पारंपरिक विधियाँ आमतौर पर मैट्रिक्स-एडजॉइंट उत्पादों ( $A^T$ ) और $B^{-1}$ की स्पष्ट गणना पर निर्भर करती हैं। लेखक इन दृष्टिकोणों के साथ दो प्राथमिक सीमाओं की पहचान करते हैं:

गणना लागत और स्थिरता: $B^{-1}$ की गणना करना या इसके साथ मैट्रिक्स-वेक्टर उत्पाद करना महंगा है और संख्यात्मक अशुद्धियों के प्रति संवेदनशील है।
एडजॉइंट मिसमैच (Adjoint Mismatch): कंप्यूटेड टोमोग्राफी जैसे अनुप्रयोगों में, ट्रांसपोज़ $A^T$ को अक्सर एक अनुमानित, गणनात्मक रूप से सुलभ ऑपरेटर द्वारा प्रतिस्थापित किया जाता है। यह "एडजॉइंट मिसमैच" महत्वपूर्ण पुनर्निर्माण त्रुटियों (reconstruction errors) की ओर ले जाता है, जिससे सटीक एडजॉइंट की आवश्यकता वाली विधियाँ अनुपयुक्त हो जाती हैं।

कार्यप्रणाली (Methodology)
लेखक एक स्टोकेस्टिक ज़ीरोथ-ऑर्डर रिमानियन एल्गोरिदम का प्रस्ताव करते हैं जो सीधे मैनिफोल्ड $S^{d-1}_B = \{v \in \mathbb{R}^d : \langle v, Bv \rangle = 1\}$ पर कार्य करता है। यह विधि $A^T$ या $B^{-1}$ की गणना किए बिना, केवल $A$ और $B$ के साथ मैट्रिक्स-वेक्टर उत्पादों पर निर्भर रहते हुए, पूरी तरह से इनसे बचती है।

मुख्य एल्गोरिदम (सिंगल-सैंपल के लिए एल्गोरिदम 1, मल्टी-सैंपल के लिए एल्गोरिदम 2) इस प्रकार आगे बढ़ता है:

आरंभीकरण (Initialization): मैनिफोल्ड पर एक यादृच्छिक वेक्टर $v_0$ से प्रारंभ करें।
सैंपलिंग (Sampling): प्रत्येक पुनरावृत्ति (iteration) $k$ पर, स्पर्श रेखा स्थान (tangent space) $T_{v_k} S^{d-1}_B$ से एक यादृच्छिक दिशा $x_k$ का नमूना लें। यह एक मानक गौसियन वेक्टर को स्पर्श रेखा स्थान पर प्रोजेक्ट करके और उसे नॉर्मलाइज़ करके किया जाता है।
इष्टतम स्टेप साइज (Optimal Step Size): एक निश्चित या बैकट्रैकिंग स्टेप साइज का उपयोग करने के बजाय, एल्गोरिदम नमूना ली गई दिशा के साथ एक-आयामी अधिकतमकरण समस्या को विश्लेषणात्मक रूप से हल करता है:
$\tau_k = \arg\max_{\tau \in \mathbb{R}} r(A, B, v_k + \tau x_k)$
थ्योरम 3.1 $v_k$ और $x_k$ के $A$ और $B$ के साथ केवल आंतरिक उत्पादों (inner products) को शामिल करते हुए $\tau_k$ के लिए एक क्लोज्ड-फॉर्म समाधान प्रदान करता है।
अपडेट (Update): इटरेट को रिट्रैक्शन मैप (retraction map) के माध्यम से अपडेट किया जाता है: $v_{k+1} = R_{v_k}(\tau_k x_k)$ ।

मल्टी-सैंपल वेरिएंट (एल्गोरिदम 2), स्टेप साइज की गणना करने से पहले ग्रेडिएंट अनुमान के विचरण (variance) को कम करने के लिए कई नमूना ली गई दिशाओं का औसत निकालता है।

सैद्धांतिक योगदान
लेखक इस शर्त के तहत कठोर अभिसरण गारंटी (convergence guarantees) स्थापित करते हैं कि अधिकतम आइजनवैल्यू के आइजनस्पेस का आयाम, $\dim(G_{\max})$ , $d-1$ से कम है।

समयपूर्व समाप्ति का न होना (Non-Termination): लेखक सिद्ध करते हैं कि यदि $\dim(G_{\max}) < d-1$ , तो एल्गोरिदम संभाव्यता एक (probability one) के साथ समयपूर्व समाप्त नहीं होता है (अर्थात, ग्रेडिएंट प्रॉक्सी $b_k$ शून्य नहीं होता है)।
ग्लोबल मैक्सिमाइज़र तक अभिसरण: अनुक्रम के ऑब्जेक्टिव मान $r(A, B, v_k)$ लगभग निश्चित रूप से (almost surely) ग्लोबल मैक्सिमम $R(A, B)$ की ओर अभिसरित होते हैं। इसके अलावा, इटरेट्स का अनुक्रम ग्लोबल मैक्सिमाइज़र्स के सेट $G_{\max}$ की ओर अभिसरित होता है।
अभिसरण दरें (Convergence Rates):
- रिमानियन ग्रेडिएंट का नॉर्म उप-रैखिक दर (sublinear rate) $O(1/n)$ के साथ शून्य की ओर जाता है।
- विशेष रूप से, $\min_{k=0,\dots,n} \| \text{grad } f(v_k) \|^2 \leq \frac{C}{n+1}$ , जहाँ $C$ , $B$ के कंडीशन नंबर और $A$ के नॉर्म पर निर्भर करता है।
ज़ीरोथ-ऑर्डर व्याख्या: इस विधि को स्टोकेस्टिक ज़ीरोथ-ऑर्डर रिमानियन ग्रेडिएंट एसेंट के रूप में पुनर्व्याख्यायित किया गया है। लेखक दिखाते हैं कि अपडेट दिशा $b_k x_k$ , रिमानियन ग्रेडिएंट के एक अनबायस्ड एस्टीमेटर (unbiased estimator) के रूप में कार्य करती है (जो $1/(d-1)$ द्वारा स्केल किया गया है), जो प्रस्तावित विधि को मौजूदा स्टोकेस्टिक ऑप्टिमाइज़ेशन फ्रेमवर्क से जोड़ती है।

संख्यात्मक परिणाम
व्यापक संख्यात्मक प्रयोग प्रस्तावित विधि के सैद्धांतिक निष्कर्षों को मान्य करते हैं और इसे अत्याधुनिक विकल्पों के विरुद्ध तुलना करते हैं:

ZO-RGA के साथ तुलना: प्रस्तावित विधि [32] से स्टोकेस्टिक ज़िरोथ-ऑर्डर रिमानियन ग्रेडिएंट एसेंट (ZO-RGA) से काफी बेहतर प्रदर्शन करती है, विशेष रूप से उच्च आयामों ( $d=100, 500$ ) में। स्टेप साइज $\tau_k$ का विश्लेषणात्मक चयन ZO-RGA में उपयोग किए जाने वाले स्थिर स्टेप साइज या आर्मिजो बैकट्रैकिंग की तुलना में श्रेष्ठ सिद्ध होता है।
Gen-Oja के साथ तुलना: एक कारनन-लोएव (Karhunen-Loève) समस्या में, प्रस्तावित विधि दोनों नियत (deterministic) और स्टोकेस्टिक Gen-Oja विधियों की तुलना में तेजी से अभिसरित होती है और अधिक सटीक आइजनफंक्शन सन्निकटन प्रदान करती है।
मजबूती (Robustness): एल्गोरिदम इल-कंडीशन्ड मैट्रिसेस $B$ के विरुद्ध मजबूती प्रदर्शित करता है, हालांकि अभिसरण का समय $\kappa(B)$ के साथ बढ़ता है।
सैंपल साइज ( $m$ ): नमूनों की संख्या $m$ (1 से 100 तक) बढ़ाने से अभिसरण की गति में काफी सुधार होता है और विचरण (variance) कम होता है, जिसमें वेक्टरों के समानांतर प्रसंस्करण (vectorization) के कारण न्यूनतम अतिरिक्त रनटाइम लागत आती है।
रेले-रिट्ज़ सबप्रॉब्लम (Rayleigh-Ritz Subproblem): लेखक वर्तमान इटरेट और $m$ नमूनों द्वारा स्पैन किए गए सबस्पेस पर अपनी विधि की तुलना रेले-रिट्ज़ दृष्टिकोण से करते हैं। जबकि रेले-रिट्ज़ विधि विशिष्ट बड़े $m$ और $d$ संयोजनों के लिए तेज़ हो सकती है, प्रस्तावित विधि कम्प्यूटेशनल जटिलता ($O(dm) $बनाम$ O(d^2m)$) और अभिसरण गति के बीच एक बेहतर संतुलन प्रदान करती है।

महत्व और दावे
शोध पत्र का दावा है कि यह एक "सरल और कुशल" एल्गोरिदम पेश करता है जो एडजॉइंट या इनवर्स गणना की आवश्यकता के बिना सामान्यीकृत रेले कोटिएंट मैक्सिमाइज़ेशन को हल करता है। इसका प्राथमिक महत्व निम्नलिखित में निहित है:

एडजॉइंट-मुक्त संचालन: यह उन समस्याओं के लिए एक प्रमाणित अभिसरण समाधान प्रदान करता है जहाँ $A^T$ उपलब्ध नहीं है या मिसमैच है, जो इमेजिंग और इनवर्स समस्याओं में एक सामान्य परिदृश्य है।
सैद्धांतिक कठोरता: यह सामान्यीकृत रेले कोटिएंट के लिए विशेष रूप से लागू होने वाले पहले स्टोकेस्टिक ज़ीरोथ-ऑर्डर रिमानियन मेथड के लिए अभिसरण विश्लेषण प्रदान करता है, जो ग्लोबल मैक्सिमाइज़र्स तक लगभग निश्चित अभिसरण और उप-रैखिक दरों को स्थापित करता है।
प्रदर्शन: अनुभवजन्य परिणाम मौजूदा स्टोकेस्टिक और नियत बेसलाइन की तुलना में, विशेष रूप से उच्च-आयामी सेटिंग्स और इल-कंडीशन्ड मैट्रिसेस के मामले में, बेहतर प्रदर्शन को प्रदर्शित करते हैं।

यह कार्य पिछले प्रीप्रिंट [41] का विस्तार करता है, जो ढांचे को रिमानियन ज्यामिति और सामान्यीकृत रेले कोटिएंट तक विस्तृत करता है, और अतिरिक्त स्पष्टीकरण एवं अभिसरण विश्लेषण में पर्याप्त सुधार शामिल करता है।

इसी तरह के और पेपर