🔢 mathematics

High-dimensional sparse trigonometric approximation in the uniform norm and consequences for sampling recovery

यह शोध पत्र $L_q$ और $L_\infty$ नॉर्म्स में विनर क्लासेज (Wiener classes) के लिए सटीक आयाम-निर्भर स्थिरांकों के साथ नए उच्च-आयामी विरल त्रिकोणमितीय सन्निकटन परिणाम स्थापित करता है, जो यह प्रदर्शित करता है कि पदों की संख्या व्युत्क्रम सटीकता के साथ द्विघात रूप से स्केल करती है और सीमित मिश्रित सुगमता वाले फलनों के लिए $\ell_1$ -न्यूनतमीकरण (minimization) के माध्यम से सुलभ नमूना रिकवरी को सक्षम बनाती है।

मूल लेखक: Moritz Moeller, Serhii Stasyuk, Tino Ullrich

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

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

CC BY 4.0

मूल लेखक: Moritz Moeller, Serhii Stasyuk, Tino Ullrich

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

कल्पना कीजिए कि आप अपने एक मित्र को एक विशाल, अराजक शहर का वर्णन करने की कोशिश कर रहे हैं जिसने इसे पहले कभी नहीं देखा है। आपके पास सीमित समय है और केवल कुछ वाक्यों का ही विकल्प है। यदि आप हर एक इमारत, सड़क और व्यक्ति का वर्णन करने की कोशिश करते हैं, तो आप पहले ब्लॉक तक पहुँचने से पहले ही समय समाप्त कर देंगे। यह "आयामों का अभिशाप" (curse of dimensionality) है। गणित और विज्ञान की दुनिया में, जब हम कई अलग-अलग चरों (जैसे तापमान, आर्द्रता, हवा की गति और समय एक साथ) वाली चीजों को समझने की कोशिश करते हैं, तो एक सटीक चित्र प्राप्त करने के लिए आवश्यक जानकारी की मात्रा आमतौर पर विस्फोट की तरह बढ़ जाती है, जो इतनी तेजी से बढ़ती है कि उसे संभालना असंभव हो जाता है।

हालाँकि, कई वास्तविक दुनिया के संकेत वास्तव में अराजक मलबे नहीं होते; वे "विरल" (sparse) होते हैं। उस शहर के बारे में सोचें जो ज्यादातर खाली मैदानों से भरा है जिसमें बस कुछ प्रमुख स्थल (landmarks) हैं। यदि आप जानते हैं कि शहर विरल है, तो आपको हर खाली मैदान का वर्णन करने की आवश्यकता नहीं है; आपको बस उन प्रमुख स्थलों को खोजने की आवश्यकता है। यह शोध पत्र अनुमान सिद्धांत (approximation theory) के क्षेत्र में है, जो मूल रूप से सर्वोत्तम संभव शॉर्टकट का विज्ञान है। यह पूछता है: यदि हमारे पास एक जटिल, बहु-आयामी फलन (एक आकार या संकेत का गणितीय विवरण) है, तो हम इसे इसके केवल कुछ सबसे महत्वपूर्ण हिस्सों का उपयोग करके कैसे पुनर्गठित कर सकते हैं? विशेष रूप से, लेखक त्रिकोणमितीय सन्निकटन (trigonometric approximation) पर विचार कर रहे हैं, जो एक जटिल ध्वनि तरंग या छवि को पूरे स्पेक्ट्रम के बजाय केवल कुछ विशिष्ट संगीत स्वरों या रंगों का उपयोग करके पुनर्गठित करने जैसा है। लक्ष्य यह देखना है कि क्या हम इन शॉर्टकट को कुशल बनाए रख सकते हैं, भले ही चरों (dimensions) की संख्या बहुत अधिक हो जाए, ताकि गणित विफल न हो।

इस शोध पत्र के लेखक, मोरिट्ज़ मोलर, सेरही स्टैस्युक और टीनो उलरिच, एक कठिन समस्या का समाधान करते हैं: वे जानना चाहते हैं कि हम इन जटिल, उच्च-आयामी आकारों का कम से से कम "स्वरों" (पदों/terms) का उपयोग करके कितनी अच्छी तरह सन्निकटन कर सकते हैं, जबकि यह गारंटी दी जा सकती है कि परिणाम हर एक विवरण में एक विशिष्ट त्रुटि सीमा के भीतर है, न कि केवल औसत रूप से। गणितीय शब्दों में, वे यूनिफॉर्म नॉर्म (uniform norm) की ओर देख रहे हैं, जिसका अर्थ है कि त्रुटि हर जगह कम होनी चाहिए, न कि केवल औसत रूप में। वे वीनर क्लासेज (Wiener classes) नामक गणितीय स्थान के एक विशिष्ट प्रकार पर ध्यान केंद्रित करते हैं, जहाँ फलन के "स्वर" इतनी तेजी से घटते हैं कि उन्हें विरल माना जा सके।

उन्होंने यह पाया: उन्होंने सिद्ध किया कि इन विशिष्ट प्रकार के फलनों के लिए, आप वास्तव में एक आश्चर्यजनक रूप से कम संख्या में पदों का उपयोग करके एक बहुत ही सटीक पुनर्निर्माण प्राप्त कर सकते हैं, भले ही आयाम $d$ बहुत बड़ा हो। आपको आवश्यक पदों की संख्या $m$ , आयाम के साथ घातीय रूप से (exponentially) नहीं बढ़नी चाहिए (जो कि एक आपदा होगी)। इसके बजाय, यह एक प्रबंधनीय तरीके से बढ़ती है। विशेष रूप से, एक निश्चित स्तर की सटीकता प्राप्त करने के लिए (मान लीजिए त्रुटि $\varepsilon$ है), $m$ पदों की संख्या सटीकता के व्युत्क्रम ( $1/\varepsilon$ ) के साथ अधिकतम द्विघाती (quadratically) रूप से स्केल करती है, हालांकि सटीक दर $\theta$ नामक एक पैरामीटर पर भी निर्भर करती है जो फलन की विरलता को परिभाषित करता है।

यह शोध पत्र सटीक सूत्र प्रदान करता है। उदाहरण के लिए, यदि आप $\theta$ ( $0 < \theta \le 1$ ) द्वारा परिभाषित फलनों के एक विशिष्ट वर्ग के साथ काम कर रहे हैं, तो $m$ पदों के साथ प्राप्त त्रुटि $m^{-(1/\theta - 1/2)}$ की दर से घटती है। यह एक बहुत अच्छी दर है। लेखकों ने इन सूत्रों में सटीक स्थिरांकों (constants) की भी गणना की है, यह दिखाते हुए कि आयाम $d$ का प्रभाव नियंत्रण में रखा गया है, जो मुख्य रूप से एक हानिरहित लघुगणकीय पद (जैसे $\log(d)$ ) के रूप में प्रकट होता है, न कि एक डरावने घातीय पद के रूप में।

इन परिणामों को प्राप्त करने के लिए, टीम ने एक चतुर दो-चरणीय रणनीति का उपयोग किया। पहले, उन्होंने इस समस्या को एक "कोमल" सेटिंग ( $L_q$ नॉर्म, जो एक औसत त्रुटि की तरह है) में देखा जहाँ गणित आसान है, और उन्होंने सिद्ध किया कि वहाँ स्थिरांक आयाम बढ़ने के साथ विस्फोट नहीं करते हैं। फिर, उन्होंने निकोलस्की असमानता (Nikol'skii's inequality) के एक परिष्कृत संस्करण का उपयोग करके उन परिणामों को "एक्सट्रपोलेट" (extrapolate) करने के लिए किया, जो "यूनिफॉर्म नॉर्म" (सबसे खराब स्थिति की त्रुटि) तक पहुँचते हैं। यह चरण महत्वपूर्ण था क्योंकि इसने उन्हें यह दिखाने की अनुमति दी कि सख्त अर्थों में भी, आयाम $d$ केवल एक छोटा, लघुगणकीय दंड (logarithmic penalty) जोड़ता है, न कि पूरे स्पेक्ट्रम (आवृत्तियों की सीमा) को बर्बाद करता है।

यह शोध पत्र सैंपलिंग रिकवरी (sampling recovery) से भी जुड़ा है, जो एक सीमित संख्या में मापों (जैसे 3D वस्तु की कुछ तस्वीरें लेना) से एक फलन को पुनर्गठित करने की व्यावहारिक समस्या है। वे दिखाते हैं कि चूंकि उनका विरल सन्निकटन इतना अच्छा काम करता है, इसलिए आप $\ell_1$ -न्यूनतमीकरण (एक तकनीक जो कंप्रेस्ड सेंसिंग में लोकप्रिय है) का उपयोग करके इन उच्च-आयामी फलनों को सीमित नमूनों से पुनः प्राप्त कर सकते हैं। परिणाम यह है कि इन विशिष्ट प्रकार के फलनों के लिए, यह समस्या "सुग्राह्य" (tractable) है, जिसका अर्थ है कि यह एक उचित समय और उचित डेटा के साथ हल करने योग्य है, भले ही चरों की संख्या बढ़ रही हो।

शोध पत्र में एक बात पर सावधानीपूर्वक ध्यान दिया गया है कि ये विशिष्ट, स्वच्छ परिणाम उन फलनों पर लागू होते हैं जिनमें एक निश्चित प्रकार की विरलता ( $\ell_1$ -summability condition) होती है। यदि फलनों में यह विशिष्ट संरचना नहीं है, या यदि आप अलग प्रकार के स्मूथनेस स्पेस (जैसे $\theta = \infty$ वाले) को देखते हैं, तो गणित अधिक जटिल हो जाता है, और आप अतिरिक्त लघुगणकीय कारक देख सकते हैं। लेकिन जिन वर्गों का उन्होंने अध्ययन किया है, उनके लिए "आयामों का अभिशाप" प्रभावी रूप से नियंत्रित हो गया है। उन्होंने केवल अनुमान नहीं लगाया; उन्होंने स्पष्ट स्थिरांकों के साथ कठोर गणितीय प्रमाण दिए, जिससे पता चलता है कि त्रुटि वास्तव में कैसे व्यवहार करती है। उदाहरण के लिए, उन्होंने दिखाया कि मिश्रित स्मूथनेस वाले बेसोव स्पेस (Besov spaces) से संबंधित एक विशिष्ट मामले के लिए, यूनिफॉर्म नॉर्म में त्रुटि $d \log(d)$ और $m^{-1/2}$ के क्षय दर वाले सूत्र द्वारा सीमित है, जो यह सिद्ध करता है कि आयाम का प्रभाव पहले की तुलना में बहुत कम गंभीर है।

संक्षेप में, यह शोध पत्र उच्च-आयामी गणित में दक्षता की एक जीत है। यह सिद्ध करता है कि यदि कोई संकेत पर्याप्त विरल है, तो हमें चरों की संख्या से डरने की आवश्यकता नहीं है। हम पूरे गीत को पुनर्गठित करने के लिए कुछ सबसे महत्वपूर्ण "स्वरों" को चुन सकते हैं, और गणित गारंटी देता है कि यदि गाने में दस लाख आयाम हैं, तो हमें दस लाख स्वरों की आवश्यकता नहीं होगी। लेखकों ने हमें सटीक मानचित्र दिया है कि हमें कितने स्वरों की आवश्यकता है और शहर का आकार (आयाम) यात्रा को कैसे प्रभावित करता है, यह सुनिश्चित करते हुए कि जैसे-जैसे शहर बढ़ता है, पथ चलने योग्य बना रहता है।

तकनीकी सारांश: उच्च-आयामी विरल त्रिकोणमितीय सन्निकटन (trigonometric approximation) यूनिफॉर्म नॉर्म में और सैंपलिंग रिकवरी के लिए इसके परिणाम

समस्या विवरण
यह शोध पत्र उच्च-आयामी बहुचर फलनों (multivariate functions) को सीमित संख्या में फलन नमूनों (function samples) से पुनर्गठित करने की चुनौती को संबोधित करता है, जो अक्सर "आयामीता के अभिशाप" (curse of dimensionality) से बाधित होता है। विशेष रूप से, लेखक वीनर वर्गों (Wiener classes) और मिश्रित चिकनाई (mixed smoothness) वाले बेसोव स्थानों (Besov spaces) से संबंधित फलनों के सर्वोत्तम $m$ -टर्म त्रिकोणमितीय सन्निकटन त्रुटि के लिए सटीक सीमाएँ स्थापित करने की जांच करते हैं। मुख्य समस्या यूनिफॉर्म नॉर्म ( $L_\infty$ ) में सर्वोत्तम $m$ -टर्म त्रिकोणमितीय सन्निकटन त्रुटि के लिए सटीक सीमाएँ निर्धारित करना और यह निर्धारित करना है कि ये सीमाएँ आयाम $d$ के साथ कैसे स्केल करती हैं। अंतिम लक्ष्य इन सन्निकटन परिणामों को गैर-रेखीय सैंपलिंग रिकवरी ( $m$ फलन मानों का उपयोग करके) के लिए गारंटी में अनुवादित करना है, जिससे $L_2$ नॉर्म में समस्या की सुग्राह्यता (tractability) का आकलन किया जा सके।

कार्यप्रणाली
लेखक उच्च आयामों में $L_q$ और $L_\infty$ सन्निकटन के बीच के अंतर को पाटने के लिए एक तीन-चरणीय रणनीति का उपयोग करते हैं:

संभाव्य $L_q$ सन्निकटन (Probabilistic $L_q$ Approximation): वीनर बीजगणित $A_\theta$ (जो फूरियर गुणांकों के $\ell_\theta$ -योग्यता द्वारा परिभाषित है) और संबंधित बेसोव स्थानों के लिए, लेखक $L_q$ ( $2 \le q < \infty$ ) में सर्वोत्तम $m$ -टर्म सन्निकटन त्रुटि के लिए ऊपरी और निचली सीमाएँ प्राप्त करते हैं। पिछले कार्यों के विपरीत, जो आयाम-निर्भर स्थिरांकों (constants) को ट्रैक किए बिना ग्रीडी एल्गोरिदम पर निर्भर थे, यह शोध पत्र गुणांकों के यादृच्छिक चयन (रैंडम सिलेक्शन) पर आधारित एक संभाव्य दृष्टिकोण (जो [19] से प्रेरित है) और बर्नस्टीन असमानता (Bernstein inequality) का उपयोग करता है। यह स्पष्ट रूप से स्थिरांकों को ट्रैक करने की अनुमति देता है, जिससे यह प्रदर्शित होता है कि त्रुटि सीमाएँ $d$ और $q$ के साथ बहुपद रूप से (polynomially) स्केल करती हैं।
परिमार्जित निकोल्स्की असमानता (Refined Nikol'skii Inequality): $L_q$ परिणामों को यूनिफॉर्म नॉर्म ( $L_\infty$ ) तक विस्तारित करने के लिए, लेखक शास्त्रीय निकोल्स्की असमानता का एक परिमार्जित संस्करण सिद्ध करते हैं (प्रमेय 3.1)। यह असमानता $[-N, N]^d$ आयताकार बॉक्स में आवृत्तियों वाले त्रिकोणमितीय बहुपदों के लिए $L_\infty$ नॉर्म को $L_q$ नॉर्म से जोड़ती है। महत्वपूर्ण रूप से, इस असमानता में स्थिरांक को इस तरह नियंत्रित किया गया है कि जब $q$ को उपयुक्त रूप से चुना जाता है (विशेष रूप से $q \sim \log(d)\log(\#Q)$ ), तो यह $d$ के साथ केवल बहुपद या लघुगणकीय (logarithmic) रूप से बढ़ता है। यह शास्त्रीय प्रमाणों में विशिष्ट $d$ में घातांकीय वृद्धि (exponential growth) से बचने में मदद करता है।
इंटरपोलेशन और एक्सट्रपलेशन (Interpolation and Extrapolation): इंटरपोलेशन तर्कों (विशेष रूप से $K$ -विधि और हॉसडॉर्फ-यंग असमानताओं) का उपयोग करके, परिणामों को $\theta$ और $q$ के विभिन्न पैरामीटर शासन (regimes) के लिए विस्तारित किया जाता है। अंत में, स्थापित $L_\infty$ सन्निकटन सीमाओं को गैर-रेखीय सैंपलिंग संख्याओं और सर्वोत्तम $m$ -टर्म सन्निकटन त्रुटियों के बीच ज्ञात संबंध ( [14] से) के साथ जोड़कर, सैंपलिंग रिकवरी दरों को प्राप्त किया जाता है।

प्रमुख योगदान और परिणाम

$L_q$ सन्निकटन के लिए सटीक स्थिरांक: शोध पत्र सर्वोत्तम $m$ -टर्म चौड़ाई (widths) $\sigma_m(A_\theta; \mathcal{T}^d)_{L_q}$ के लिए स्पष्ट स्थिरांक प्रदान करता है। $2 \le q < \infty$ और $0 < \theta \le 1$ के लिए, ऊपरी सीमा को $C \sqrt{q} m^{-(1/\theta - 1/2)}$ के रूप में दिखाया गया है, जहाँ स्थिरांक $C$ आयाम $d$ से स्वतंत्र है (प्रमेय 4.4)। सटीक स्थिरांकों के साथ निचली सीमाएँ भी स्थापित की गई हैं।
आयाम-निर्भर $L_\infty$ सीमाएँ: परिमार्जित निकोल्स्की असमानता के साथ अपने $L_q$ परिणामों को जोड़कर, लेखक यूनिफॉर्म नॉर्म के लिए सीमाएँ प्राप्त करते हैं। सपोर्ट आकार $\#Q$ वाले त्रिकोणमितीय बहुपदों के लिए, त्रुटि संतुष्ट करती है:
$\sigma_{4m}(t; \mathcal{T}^d)_{L_\infty} \lesssim \log(d)^{1/2} m^{-(1/\theta - 1/2)} (\log \#Q)^{1/2} \|t\|_{A_\theta}$
(प्रमेय 4.5)। यह परिणाम दर्शाता है कि आयाम $d$ का प्रभाव सपोर्ट आकार में एक लघुगणकीय कारक और $d$ में एक बहुपद कारक तक सीमित है, न कि एक घातांकीय कारक।
बेसोव स्थानों के लिए परिणाम: निष्कर्षों को प्रभावी मिश्रित चिकनाई (dominating mixed smoothness) वाले बेसोव स्थानों $B^r_{p,\theta}$ के लिए विस्तारित किया गया है। सीमांत मिश्रित चिकनाई मामले $r = 1/\theta - 1/2$ के लिए, शोध पत्र स्थापित करता है कि $L_\infty$ में सर्वोत्तम $m$ -टर्म सन्निकटन त्रुटि $m^{-(1/\theta - 1/2)}$ की दर से घटती है, जिसमें आयाम निर्भरता $d \log(d)^{1/2}$ के रूप में दिखाई देती है (प्रमेय 5.3)।
सैंपलिंग रिकवरी निहितार्थ: शोध पत्र इन सन्निकटन परिणामों को $L_2$ नॉर्म में गैर-रेखीय सैंपलिंग संख्याओं $\varrho_m$ के लिए सीमाओं में अनुवादित करता है। [14] के संबंध का उपयोग करते हुए, यह दिखाया गया है कि इन वर्गों के फलनों के लिए, सैंपलिंग रिकवरी त्रुटि $m$ के साथ बहुपद रूप से घटती है, और आयाम $d$ पर निर्भरता लघुगणकीय कारकों तक लघुगणकीय कारकों सहित अधिकतम बहुपद (विशेष रूप से $O(d^2)$ या समान, मापदंडों के आधार पर) है (अनुवर्ती 5.4)। यह इन विशिष्ट फलन वर्गों के लिए सैंपलिंग रिकवरी समस्या की बहुपद सुग्राह्यता (polynomial tractability) की पुष्टि करता है।

महत्व और दावे
लेखक दावा करते हैं कि उनका कार्य विशिष्ट विरल फलन वर्गों के लिए उच्च-आयामी सैंपलिंग रिकवरी के लिए एक "सुग्राह्य" (tractable) समाधान प्रदान करता है। प्राथमिक महत्व निम्नलिखित में निहित है:

आयामीता का नियंत्रण: शोध पत्र प्रदर्शित करता है कि वीनर और संबंधित बेसोव वर्गों के लिए, आयामीता के अभिशाप से बचा जा सकता है। रिकवरी त्रुटि $d$ पर घातांकीय के बजाय बहुपद रूप से निर्भर करती है।
स्पष्ट स्थिरांक: सन्निकटन चौड़ाई के कई साहसी (asymptotic) परिणामों के विपरीत, यह शोध पत्र सटीक, आयाम-स्वतंत्र (या बहुपद-निर्भर) स्थिरांक प्रदान करता है। यह व्यावहारिक अनुप्रयोगों और कठोर सुग्राह्यता परिणाम स्थापित करने के लिए आवश्यक है।
यूनिफॉर्म नॉर्म में विस्तार: यह शोध पत्र एक परिमार्जित निकोल्स्की असमानता का उपयोग करके उच्च आयामों में $L_q$ और $L_\infty$ सन्निकटन के बीच के अंतर को सफलतापूर्वक पाटता है, जो एक ऐसा चरण था जिसे पहले आयाम के संबंध में पूरी तरह से मात्रात्मक नहीं बनाया गया था।
मौजूदा साहित्य का पूरक: परिणाम क्रीग [16] के हालिया बहुपद सुग्राह्यता निष्कर्षों के पूरक हैं और [14] में स्थापित विरल त्रिकोणमितीय सन्निकटन और गैर-रेखीय सैंपलिंग संख्याओं के बीच संबंध को परिष्कृत करते हैं।

शोध पत्र निष्कर्ष निकालता है कि $\ell_\theta$ -विरलता (जहाँ $\theta \le 1$ ) वाले फलनों के लिए, आयाम का प्रभाव प्रबंधनीय है, जिससे उच्च-आयामी सेटिंग्स में $\ell_1$ -न्यूनतमीकरण (या संबंधित गैर-रेखीय विधियों) के माध्यम से ऐसे फलनों की रिकवरी संभव हो जाती है।

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