तकनीकी सारांश: विविक्त द्विघाती अनुकूलन (Discrete Quadratic Optimization) में निम्न-रैंक उद्देश्य संरचना का दोहन

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

यह शोध पत्र $K$-वें मूलों (roots of unity) पर एक जटिल-मान वाले द्विघाती रूप (complex-valued quadratic form) को अधिकतम करने की समस्या को संबोधित करता है। एक हर्मिटियन पॉजिटिव सेमी-डेफिनिट (PSD) आव्यूह $Q^\star \in \mathbb{C}^{n \times n}$ और एक पूर्णांक $K \ge 2$ दिया गया है, जहाँ उद्देश्य को हल करना है:
$$\text{OPT}_{Q^\star} := \max_{z \in A_K^n} z^\dagger Q^\star z$$
जहाँ $A_K = \{e^{2\pi i k / K} : k = 0, \dots, K-1\}$ है। यह ढांचा Max-Cut ($K=2$) और Max-3-Cut ($K=3$) जैसी NP-hard समस्याओं के साथ-साथ सिग्नल प्रोसेसिंग (जैसे, MIMO डिटेक्शन, कोणीय सिंक्रोनाइज़ेशन) के अनुप्रयोगों को समाहित करता है। मानक दृष्टिकोण सेडिफिनिट प्रोग्रामिंग (SDP) रिलैक्सेशन पर निर्भर करते हैं, जो मजबूत सन्निकटन गारंटी (approximation guarantees) तो प्रदान करते हैं लेकिन उनकी $O(n^{3.5})$ कम्प्यूटेशनल जटिलता के कारण स्केलेबिलिटी सीमित हो जाती है। ह्यूरिस्टिक विधियाँ बेहतर स्केल करती हैं लेकिन उनमें कठोर गारंटी का अभाव होता है या वे इनिशियलाइजेशन के प्रति संवेदनशील होती हैं।

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

लेखक एक ज्यामितीय दृष्टिकोण प्रस्तावित करते हैं जो उद्देश्य आव्यूह (objective matrix) में निम्न-रrank संरचना का दोहन करता है। समस्या को रिलैक्स करने के बजाय, वे निम्न-रैंक उदाहरणों के लिए सटीक एल्गोरिदम और लगभग निम्न-रैंक उदाहरणों के लिए सन्निकटन योजनाएं (approximation schemes) निर्मित करते हैं।

1. ज्यामितीय पुनर्गठन (Geometric Reformulation)

एक रैंक-$r$ आव्यूह $Q^\star = VV^\dagger$ (जहाँ $V \in \mathbb{C}^{n \times r}$) के लिए, द्विघाती मैक्सिमाइजेशन को सहायक कोणीय चरों (auxiliary angular variables) और विविक्त असाइनमेंट (discrete assignments) पर दोहरे मैक्सिमाइजेशन के रूप में पुनर्गठित किया जाता है:
$$\max_{z \in A_K^n} \|V^\dagger z\|_2^2 = \max_{\phi \in H_r} \sum_{i=1}^n \max_{z_i \in A_K} \text{Re}(\bar{z}_i \cdot V_{i,:} c(\phi))$$
यहाँ, $c(\phi)$ हाइपरपोलर निर्देशांकों का उपयोग करके जटिल इकाई गोले (complex unit sphere) को पैरामीटराइज़ करता है, और $H_r$, $2r-1$ आयामों वाला एक हाइपरक्यूब है।

2. हाइपरप्लेन व्यवस्था और उम्मीदवार गणना (Hyperplane Arrangement and Candidate Enumeration)

इष्टतम असाइनमेंट $z_i$ केवल तभी बदलता है जब स्पेक्ट्रल प्रोजेक्शन $V_{i,:} c(\phi)$ का चरण विशिष्ट निर्णय सीमाओं (decision boundaries)—जो $K$-वें मूलों को द्विभाजित करने वाली किरणें हैं—को पार करता है। ये सीमाएं सहायक स्थान $\mathbb{R}^{2r}$ में एक हाइपरप्लेन व्यवस्था को परिभाषित करती हैं।

• संरचना: $n K$ निर्णय सीमाएं (समरूपता के कारण $n B_K$ विशिष्ट हाइपरप्लेन में कम की गई) खोज स्थान को सेल (cells) में विभाजित करती हैं। प्रत्येक सेल के भीतर, इष्टतम असाइनमेंट वेक्टर $z$ स्थिर रहता है।
• उम्मीदवार सेट (Candidate Set): वैश्विक मैक्सिमाइज़र इस व्यवस्था के एक शीर्ष (vertex) के अनुरूप होता है। लेखक सिद्ध करते हैं कि शीर्षों (उम्मीदवार समाधानों) का सेट आकार $O(r n^{2r-1})$ है।
• एल्गोरिदम: एक नियतात्मक (deterministic) एल्गोरिदम इन शीर्षों को $2r-1$ हाइपरप्लेन के उपसमुच्चयों द्वारा परिभाषित रैखिक प्रणालियों को हल करके गणना करता है। एल्गोरिदम उन अस्पष्टताओं को संभालता है जहाँ एक ही कोआर्डिनेट समूह के कई हाइपरप्लेन प्रतिच्छेद करते हैं और सीमा मामलों (boundary cases) के लिए पुनरावर्ती रूप से निम्न-रैंक उप-समस्याओं को हल करता है।

3. विक्षेपित और उच्च-आयामी मामलों के लिए सन्निकटन

• विक्षेपित निम्न-रैंक (Perturbed Low-Rank): आव्यूतों $Q = Q^\star + H$ के लिए (जहाँ $Q^\star$ रैंक-$r$ है और $H$ शोर/noise है), लेखक $Q$ के स्पेक्ट्रल ट्रंकेशन पर सटीक सॉल्वर लागू करते हैं। वे एक मल्टीप्लिकेटिव एप्रोक्सिमेशन गारंटी $(1 - O(\|H\|_2 / \delta^\star))$ सिद्ध करते हैं, जहाँ $\delta^\star$, $Q^\star$ का आइगेनगैप (eigengap) है।
• यादृच्छिक नमूनाकरण (Randomized Sampling): बड़े $n$ के लिए $O(n^{2r-1})$ गणना लागत से बचने के लिए, एक यादृच्छिक संस्करण जटिल इकाई गोले से $S$ दिशाओं को समान रूप से नमूना (sample) लेता है। सैद्धांतिक विश्लेषण दिखाता है कि $S = O(1/\varepsilon^{r-1})$ नमूने उच्च संभावना के साथ $(1-\varepsilon)\cos^2(\pi/K)$-सन्निकटन प्राप्त करने के लिए पर्याप्त हैं। महत्वपूर्ण रूप से, इस नमूना आकार की निर्भरता $n$ से स्वतंत्र है।

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

1. सटीक बहुपद-समय एल्गोरिदम (Exact Polynomial-Time Algorithms): यह शोध पत्र किसी भी रैंक-$r$ आव्यूह के लिए विविक्त द्विघाती मैक्सिमाइजेशन को $O(r n^{2r+1})$ समय में सटीक रूप से हल करने वाले नियतात्मक एल्गोरिदम प्रदान करता है। यह उन घातीय जटिलताओं (exponential complexities) से एक महत्वपूर्ण विचलन है जो आमतौर पर सटीक विविक्त अनुकूलन से जुड़ी होती हैं। ये एल्गोरिदम "एम्बारसिंगली पैरेलल" (embarrassingly parallel) हैं, जिससे प्रोसेसरों की संख्या के साथ रैखिक गति (linear speedup) संभव है।
2. अनुमानित निम्न-रैंक के लिए सैद्धांतिक गारंटी: यह ढांचा उन वास्तविक दुनिया के परिदृश्यों तक विस्तारित है जहाँ आव्यूह केवल अनुमानित रूप से निम्न-रैंक होते हैं। लेखक शोर के स्तर और स्पेक्ट्रल गैप के सापेक्ष सन्निकटन अनुपात पर कठोर सीमाएं स्थापित करते हैं।
3. आयाम-स्वतंत्र नमूनाकरण (Dimension-Independent Sampling): एक यादृच्छिक नमूनाकरण रणनीति पेश की गई है जो रनटाइम को $O(S \cdot n^2)$ तक कम कर देती है, जहाँ $S$ केवल रैंक $r$ और वांछित सटीकता $\varepsilon$ पर निर्भर करता है, न कि आयाम $n$ पर। यह $n \ge 10^6$ वाली समस्याओं तक स्केलिंग को सक्षम बनाता है।
4. अनुभवजन्य सत्यापन (Empirical Validation): Max-3-Cut बेंचमार्क (GSet सूट और सिंथेटिक ग्राफ सहित) पर व्यापक प्रयोगों से पता चलता है कि प्रस्तावित एल्गोरिदम संरचित उदाहरणों पर अत्याधुनिक SDP रिलैक्सेशन और ह्यूरिस्टिक्स की समाधान गुणवत्ता के बराबर या उससे बेहतर प्रदर्शन करते हैं, जबकि व्यापक स्केलेबिलिटी भी प्रदान करते हैं।

परिणाम

• लघु-पैमाने का प्रदर्शन: $n \le 50$ वाले ग्राफों पर, रैंक-3 एल्गोरिदम लगभग इष्टतम अनुपात (जैसे, 5-रेगुलर ग्राफों पर 0.997) प्राप्त करता है, जो SDP राउंडिंग और ग्रीडी ह्यूरिस्टिक्स से बेहतर है।
• स्केलेबिलिटी: GSet बेंचमार्क पर, रैंक-1 एल्गोरिदम संरचित टोरोइडल ग्राफों (जहाँ स्पेक्ट्रम केंद्रित होता है) को सेकंडों में इष्टतम रूप से हल करता है, जो ग्रीडी विधियों (मिनटों में) और SDP की तुलना में काफी तेज़ है। अनस्ट्रक्चर्ड ग्राफों के लिए, यह गति के लिए समाधान की गुणवत्ता का कुछ त्याग करता है, और बहुत कम समय में ग्रीडी स्कोर का ~90% प्राप्त करता है।
• बड़े पैमाने पर स्केलिंग: यादृच्छिक नमूनाकरण दृष्टिकोण $n = 1,000,000$ नोड्स तक के ग्राफों को सफलतापूर्वक संभालता है। इष्टतम के करीब समाधान तक पहुँचने के लिए आवश्यक सैंपल बजट $n$ के साथ नहीं बढ़ता है, जो आयाम से नमूना जटिलता की सैद्धांतिक स्वतंत्रता की पुष्टि करता है।
• समानांतर दक्षता (Parallel Efficiency): विषमांगी (heterogeneous) GPU क्लस्टर्स (15 GPU) पर प्रयोग दिखाते हैं कि समानांतर कार्यान्वयन कुशलतापूर्वक स्केल करता है, जो 1,500 नोड्स पर रैंक-2 उदाहरणों को मिनटों में हल करता है, जो SDP के तुलनीय है लेकिन इसमें व्यापक समानांतर क्षमता है।

महत्व

यह शोध पत्र दावा करता है कि उद्देश्य आव्यूह में निम्न-रैंक संरचना एक पूर्व में कम उपयोग किया गया संसाधन है जो विविक्त द्विघाती अनुकूलन (एक वर्ग जिसे आम तौर पर NP-hard माना जाता है) के लिए सटीक बहुपद-समय समाधानों को सक्षम बनाता है। निम्न-रैंक कारक द्वारा परिभाषित समाधान स्थान के ज्यामितीय गणना (geometric enumeration) पर ध्यान केंद्रित करके, लेखक प्रदान करते हैं:

1. सटीकता (Exactness): उन संरचित उदाहरणों के लिए सटीक समाधानों का मार्ग जहाँ SDP केवल एक सन्निकटन है।
2. स्केलेबिलिटी: लाखों चरों वाली समस्याओं को हल करने की विधि, जो मानक SDP सॉल्वर के लिए अगम्य (intractable) हैं।
3. मजबूती (Robustness): स्पेक्ट्रल ट्रंकेशन के माध्यम से शोर वाले, वास्तविक दुनिया के डेटा के लिए विस्तार करने वाली सैद्धांतिक गारंटी।

यह कार्य सैद्धांतिक कॉम्बिनेटरियल ऑप्टिमाइज़ेशन और व्यावहारिक बड़े पैमाने के अनुप्रयोगों (विशेष रूप से सिग्नल प्रोसेसिंग और ग्राफ पार्टिशनिंग में) के बीच के अंतर को पाटता है, जो समस्या को एक जेनेरिक ब्लैक बॉक्स के रूप में मानने के बजाय उद्देश्य के स्पेक्ट्रल गुणों का लाभ उठाता है।