Finding accurate eigenvalues and eigenvectors of positive semi-definite matrices given a subspace

तकनीकी सारांश: एक उपसमष्टि (Subspace) दिए जाने पर धनात्मक अर्ध-निश्चित (Positive Semi-Definite) आव्यूहों के सटीक आइगेनमान (Eigenvalues) और आइगेनवेक्टर (Eigenvectors) खोजना

समस्या विवरण
यह शोध पत्र संख्यात्मक रैखिक बीजगणित (numerical linear algebra) की एक शास्त्रीय समस्या को संबोधित करता है: एक $n \times n$ धनात्मक अर्ध-निश्चित (PSD) आव्यूह $A$ और एक $k$-आयामी उपसमष्टि $Q$ (जिसे एक ऑर्थोनॉर्मल बेस मैट्रिक्स $Q \in \mathbb{R}^{n \times k}$ द्वारा दर्शाया गया है) दिया गया है, जो $A$ के प्रमुख आइगेनस्पेस (leading eigenspace) का सन्निकटन (approximation) करता है, तो उच्च-सटीकता वाले आइगेनमान और आइगेनवेक्टर कैसे निकाले जा सकते हैं? जबकि रेले-रित्ज़ (Rayleigh-Ritz - RR) विधि इस कार्य के लिए मानक दृष्टिकोण है, लेखक यह जांचते हैं कि क्या $A$ के धनात्मक अर्ध-निश्चित होने के विशिष्ट संरचनात्मक गुण का उपयोग बिना कम्प्यूटेशनल जटिलता बढ़ाए, RR द्वारा दी जाने वाली सटीकता से बेहतर परिणाम प्राप्त करने के लिए किया जा सकता है।

कार्यप्रणाली (Methodology)
शोध पत्र तीन प्रोजेक्शन-आधारित विधियों की तुलना करता है जो $O(Nk + nk^2)$ की समान कम्प्यूटेशनल जटिलता साझा करती हैं, जहाँ $N$ आव्यूह $A$ के साथ आव्यूह-सदिश गुणन (matrix-vector multiplication) की लागत है:

1. रेले-रित्ज़ (RR): मानक विधि जो प्रक्षेपित आव्यूह $Q^\top A Q$ के आइगेनमानों की गणना करती है। अनुमानित आइगेनमान $\hat{\lambda}_i^{(RR)} = \lambda_i(Q^\top A Q)$ हैं।
2. SVD-extract: यह विधि PSD आव्यूहों के लिए आइगेनमानों और सिंगुलर मानों (singular values) के बीच समानता का लाभ उठाती है। यह एक-पक्षीय प्रोजेक्शन (one-sided projection) $AQ$के सिंगुलर मानों की गणना करती है। अनुमानित आइगेनमान$\hat{\lambda}_i^{(SVD)} = \sigma_i(AQ)$ हैं।
3. निस्ट्रोम विधि (Nyström Method): यह विधि $A$ के निम्न-रैंक सन्निकटन (low-rank approximation) का निर्माण करती है, जिसे $A_{\langle Q \rangle} = AQ(Q^\top AQ)^\dagger (AQ)^\top$ के रूप में दर्शाया गया है, और इस सन्निकटन से आइगेनमान निकालती है। अनुमानित आइगेनमान $\hat{\lambda}_i^{(Nys)} = \lambda_i(A_{\langle Q \rangle})$ हैं।

लेखक $Q$ को $A$ के प्रमुख अपरिवर्तनीय उपसमष्टि (dominant invariant subspace) $U_1$ के $\epsilon$-सन्निकटन के रूप में मॉडल करके इन विधियों का सैद्धांतिक विश्लेषण करते हैं। वे आइगेनमान सन्निकटन के लिए त्रुटि सीमा (error bounds) प्राप्त करने हेतु विक्षोभ विश्लेषण (perturbation analysis), शूर पूरक (Schur complements), और PSD आव्यूहों के गुणों का उपयोग करते हैं।

मुख्य योगदान और सैद्धांतिक परिणाम

• प्रमुख आइगेनमानों के लिए सटीकता पदानुक्रम (Accuracy Hierarchy): शोध पत्र प्रमुख आइगेनमानों (उन आइगेनमानों के लिए जो $A$ के सबसे बड़े आइगेनमानों के अनुरूप हैं) के सन्निकटन के लिए एक सख्त क्रम स्थापित करता है। लेखक अनुमानित आइगेनमानों के लिए निम्नलिखित असमानता सिद्ध करते हैं:
  $$\lambda_i(A) \geq \lambda_i(A_{\langle Q \rangle}) \geq \sigma_i(AQ) \geq \lambda_i(Q^\top A Q)$$
  परिणामस्वरूप, निरपेक्ष त्रुटि (absolute error) इस प्रकार है:
  $$|\lambda_i(A) - \hat{\lambda}_i^{(RR)}| \geq |\lambda_i(A) - \hat{\lambda}_i^{(SVD)}| \geq |\lambda_i(A) - \hat{\lambda}_i^{(Nys)}|$$
  यह दर्शाता है कि निस्ट्रोम सर्वाधिक सटीक अनुमान प्रदान करता है, उसके बाद SVD-extract, और RR सबसे कम सटीक है।

• निस्ट्रोम की उच्च-क्रम सटीकता (Higher-Order Accuracy): लेखक मात्रात्मक त्रुटि सीमाएं निकालते हैं जो दर्शाती हैं कि निस्ट्रोम, RR और SVD-extract की तुलना में उच्च-क्रम की सटीकता प्राप्त करता है। विशेष रूप से, जब $A$ का स्पेक्ट्रम तेजी से घटता है (अर्थात, $\lambda_1 \gg \lambda_{k+1}$), तो प्रमुख आइगेनमानों के लिए निस्ट्रोम विधि की त्रुटि, $\lambda_1(A)/\lambda_{k+1}(A)$ के अनुपात वाले कारक से RR और SVD-extract की तुलना में छोटी हो सकती है। यह सुधार अत्यधिक बड़ा हो सकता है।

• पिछली (Trailing) आइगेनमानों के लिए उलटाव: शोध पत्र नोट करता है कि जब लक्ष्य 'ट्रेलिंग' (सबसे छोटे) आइगेनमानों को प्राप्त करना होता है, तो स्थिति उलट जाती है। इस शासन (regime) में, निस्ट्रोम विधि खराब प्रदर्शन करती है, और RR सबसे सटीक विधि बन जाती है। लेखक इसका श्रेय इस तथ्य को देते हैं कि $\text{span}(AQ)$ (जिसका उपयोग निस्ट्रोम और SVD-$\tilde{U}$ द्वारा किया जाता है) प्रमुख अपरिवर्तनीय उपसमष्टि $U_1$ का एक बेहतर सन्निकटन है लेकिन $\text{span}(Q)$ की तुलना में ट्रैलिंग अपरिवर्तनीय उपसमष्टि $U_2$ का एक खराब सन्निकटन है।

• ट्रेलिंग आइगेनमानों के लिए उपचार (Remedy): ट्रैलिंग आइगेनमानों के लिए खराब प्रदर्शन को संबोधित करने के लिए, लेखक एक 'शिफ्ट-एंड-फ्लिप' (shift-and-flip) रणनीति का सुझाव देते हैं। शिफ्ट किए गए आव्यूह $\gamma I - A$ (जहाँ $\gamma \geq \lambda_{\max}(A)$) के प्रमुख आइगेनपेयर्स (eigenpairs) की गणना करके, मूल आव्यूह के ट्रैलिंग आइगेनमानों को प्रभावी ढंग से प्राप्त करने के लिए निस्ट्रोम विधि का उपयोग किया जा सकता है।

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

• प्रमुख आइगेनमान: जब $A$ का स्पेक्ट्रम तेजी से घटता है (घातांकीय क्षय/exponential decay), तो निस्ट्रोम विधि, RR और SVD-extract से काफी बेहतर प्रदर्शन करती है, जिसके त्रुटि ढलान (error slopes) उच्च-क्रम अभिसरण (higher-order convergence) का संकेत देते हैं। जब स्पेक्ट्रम धीमा घटता है (बीजीय या रैखिक क्षय), तो निस्ट्रोम का लाभ कम हो जाता है लेकिन फिर भी बना रहता है।
• आइगेनवेक्टर: आइगेनवेक्टर सन्निकटन के लिए भी समान रुझान देखे गए हैं। $\text{span}(AQ)$ का उपयोग करने वाली विधियाँ (निस्ट्रोम और SVD-$\tilde{U}$) $\text{span}(Q)$ तक सीमित विधियों (RR और SVD-$Q\tilde{V}$) की तुलना में अधिक सटीक प्रमुख आइगेनवेक्टर प्रदान करती हैं।
• ट्रेलिंग आइगेनमान: प्रयोग पुष्टि करते हैं कि ट्रैलिंग आइगेनमानों के लिए RR श्रेष्ठ है, जबकि निस्ट्रोम शिफ्ट-एंड-फ्लिप तकनीक का उपयोग किए बिना विफल हो जाता है।

महत्व और दावे
शोध पत्र साहित्य में एक स्पष्ट विसंगति को हल करने का दावा करता है: जबकि RR को मिनी-मैक्स लक्षण वर्णन (min-max characterization) और उपसमष्टि प्रोजेक्शन के अर्थ में इष्टतम (optimal) माना जाता है, यह इष्टतमता स्पष्ट रूप से PSD गुण का उपयोग करने पर अधिक सटीक आइगेनमान सन्निकटन के अस्तित्व को बाधित नहीं करती है।

इस कार्य का प्राथमिक महत्व इस बात का प्रदर्शन है कि PSD आव्यूहों के लिए, निस्ट्रोम विधि प्रमुख आइगेनपेयर्स निकालने के लिए मानक रेले-रित्ज़ विधि का एक बेहतर विकल्प है, जो बिना किसी अतिरिक्त कम्प्यूटेशनल लागत के काफी उच्च सटीकता प्रदान करती है। लेखक इस बात पर जोर देते हैं कि यह सुधार विशेष रूप से उन अनुप्रयोगों में महत्वपूर्ण है जिनमें तेजी से घटने वाले स्पेक्ट्रा वाले आव्यूह शामिल हैं, जैसे कि मशीन लर्निंग में कर्नेल मैट्रिसेस और प्रिंसिपल कंपोनेंट एनालिसिस (PCA) में कोवेरिएंस मैट्रिसेस। शोध पत्र विनम्रतापूर्वक नोट करता है कि हालांकि सैद्धांतिक सीमाएं वास्तविक आव्यूहों (real matrices) के लिए व्युत्पन्न की गई हैं, समान परिणाम जटिल आव्यूहों (complex matrices) के लिए भी लागू होते हैं।