🔢 mathematics

Quantitative Bounds for Sorting-Based Permutation-Invariant Embeddings

यह शोध पत्र इनजेक्टिविटी (injectivity) के लिए आवश्यक प्रोजेक्शन आयाम (projection dimension) पर बेहतर सीमाएं स्थापित करके और ऐसे प्रोजेक्शन मैट्रिसेस का निर्माण करके सॉर्टिंग-आधारित परम्यूटेशन-इनवेरिएंट एम्बेडिंग्स (sorting-based permutation-invariant embeddings) के सिद्धांत को आगे बढ़ाता है जो इनपुट आयाम से स्वतंत्र रहते हुए बिंदुओं की संख्या पर द्विघात रूप से (quadratically) निर्भर बाय-लिप्सचिट्ज़ डिस्टॉर्शन (bi-Lipschitz distortion) प्राप्त करते हैं।

मूल लेखक: Nadav Dym, Matthias Wellershoff, Efstratios Tsoukanis, Daniel Levy, Radu Balan

प्रकाशित 2026-04-10

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

CC BY 4.0

मूल लेखक: Nadav Dym, Matthias Wellershoff, Efstratios Tsoukanis, Daniel Levy, Radu Balan

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

कल्पना कीजिए कि आपके पास मोतियों का एक थैला है। उस थैले के अंदर $n$ मोती हैं, और प्रत्येक मोती पर $d$ अलग-अलग रंग पेंट किए गए हैं।

कंप्यूटर विज्ञान और मशीन लर्निंग की दुनिया में, हमें अक्सर कंप्यूटर को इन मोतियों के थैलों को पहचानना सिखाने की आवश्यकता होती है। लेकिन इसमें एक पेच है: क्रम मायने नहीं रखता। चाहे आप पहले लाल मोती निकालें या नीला, थैला वही रहता है। कंप्यूटर को यह समझना चाहिए कि $\{Red, Blue, Green\}$ वही है जो $\{Green, Red, Blue\}$ है।

इसे परम्यूटेशन इनवेरिएंस (Permutation Invariance) कहा जाता है। यह एक चेहरे को पहचानने जैसा है, चाहे वह व्यक्ति खड़ा हो, बैठा हो, या चलते हुए आ रहा हो। विशेषताएं वही रहती हैं; केवल उनका विन्यास बदलता है।

समस्या: अराजकता को व्यवस्थित करना

यह शोध पत्र इस समस्या को हल करने के एक विशिष्ट, चतुर तरीके पर ध्यान केंद्रित करता है। मोतियों के हर संभावित क्रम को याद करने के बजाय, लेखक एक सरल रणनीति का सुझाव देते हैं: उन्हें क्रमबद्ध (Sort) करें।

कल्पना कीजिए कि आपके पास एक टॉर्च है जो एक विशिष्ट कोण से आपके मोतियों के थैले पर रोशनी डालती है। यह 3D मोतियों को 2D दीवार पर प्रोजेक्ट करती है। यदि आप दीवार पर पड़ने वाली छायाओं को देखते हैं, तो आप उन्हें बाएं से दाएं क्रमबद्ध कर सकते हैं। यदि आप कई अलग-अलग टॉर्चों (कोणों) के साथ ऐसा करते हैं, तो आपको अपने मोतियों के थैले का एक अनूठा "फिंगरप्रिंट" प्राप्त होता है।

यह शोध पत्र $\beta_A$ नामक एक गणितीय फलन (function) का अध्ययन करता है। यह आपके मोतियों के थैले को लेता है, $D$ अलग-अलग टॉर्चों (प्रोजेक्शन) से उन पर रोशनी डालता है, परिणामी छायाओं को क्रमबद्ध करता है, और संख्याओं की एक लंबी सूची बनाता है। यह सूची आपका "एम्बेडिंग" (embedding) या डिजिटल आईडी कार्ड है।

दो बड़े प्रश्न

लेखक इस सॉर्टिंग विधि के बारे में दो महत्वपूर्ण प्रश्नों का उत्तर देना चाहते थे:

हमें कितने टॉर्च ( $D$ ) की आवश्यकता है?
यदि हम बहुत कम टॉर्च का उपयोग करते हैं, तो दो अलग-अलग थैले सॉर्ट होने के बाद एक जैसे दिख सकते हैं (एक गलत सूचना/false alarm)। यदि हम बहुत अधिक उपयोग करते हैं, तो डेटा बहुत बड़ा हो जाता है और उसे प्रोसेस करने में समय लगता है। हमें टॉर्चों की उस न्यूनतम संख्या की आवश्यकता है जो यह गारंटी दे सके कि प्रत्येक थैले की एक अनूठी आईडी है।
आईडी कार्ड कितना "विकृत" (distorted) है?
यदि दो थैले लगभग एक जैसे हैं (जैसे कि दो थैलों में लाल रंग के थोड़े अलग शेड्स हैं), तो उनके आईडी कार्ड भी एक-दूसरे के बहुत करीब होने चाहिए। यदि आईडी कार्ड दूर हैं, तो सिस्टम "विकृत" और अविश्वसनीय है। हम चाहते हैं कि विकृति (distortion) यथासंभव कम हो।

निष्कर्ष: उन्होंने क्या खोजा

1. "टॉर्च" की संख्या (Injectivity)

पिछले शोधों ने सुझाव दिया था कि यह सुनिश्चित करने के लिए कि थैले अद्वितीय हैं, आपको बहुत बड़ी संख्या में टॉर्च (जो $n!$ की तरह सुपर-एक्सपोनेंशियल रूप से बढ़ती है) की आवश्यकता होगी। यह अव्यवहारिक है।

नई खोज: लेखकों ने सिद्ध किया कि आपको इतनी अधिक टॉर्च की आवश्यकता नहीं है। आपको केवल टॉर्चों की एक ऐसी संख्या चाहिए जो मोतियों की संख्या ( $n$ $n$ ) और रंगों की संख्या ( $d$ $d$ ) के साथ रैखिक (linearly) रूप से बढ़ती है।
- उपमा: कल्पना कीजिए कि आपके पास 100 मोती हैं। पुराने गणित ने कहा कि यह सुनिश्चित करने के लिए आपको शायद एक अरब टॉर्च की आवश्यकता होगी। नया गणित कहता है, "वास्तव में, आपको शायद कुछ सौ ही चाहिए।"
- उन्होंने एक "फ्लोर" (lower bound) भी पाया। आप टॉर्चों की एक निश्चित संख्या से नीचे नहीं जा सकते, अन्यथा सिस्टम निश्चित रूप से विफल हो जाएगा। यह कम से कम जानकारी के साथ किसी व्यक्ति की पहचान करने जैसा है; आपको कम से कम एक न्यूनतम मात्रा की आवश्यकता होती है।

2. "विकृति" (Lipschitz Bounds)

यह इस बारे में है कि आईडी कार्ड थैलों के बीच की "दूरी" को कितनी अच्छी तरह सुरक्षित रखता है।

अच्छी खबर: उन्होंने टॉर्चों को इस तरह से सेट करने का तरीका खोजा जिससे विकृति केवल मोतियों की संख्या के वर्ग ( $n^2$ ) के साथ बढ़ती है। महत्वपूर्ण बात यह है कि यह विकृति इस बात पर निर्भर नहीं करती कि मोतियों के कितने रंग ( $d$ ) हैं।
- उपमा: चाहे आपके पास 2 रंगों वाले 10 मोती हों या 1,000 रंगों वाले, आईडी कार्ड की "धुंधलापन" (fuzziness) प्रबंधनीय रहती है। यह एक कैमरे की तरह है जो छोटे ऑब्जेक्ट या जटिल ऑब्जेक्ट दोनों की तस्वीर लेते समय भी स्पष्ट रहता है।
बुरी खबर (सीमा): उन्होंने यह भी सिद्ध किया कि आप बहुत अच्छा नहीं कर सकते। आप कितने भी चतुर क्यों न हों, विकृति हमेशा मोतियों की संख्या के वर्गमूल ( $\sqrt{n}$ ) के समानुपाती होगी।
- उपमा: आप शहर का एकदम सटीक नक्शा बिना किसी विकृति के नहीं बना सकते। जैसे-जैसे आप अधिक ब्लॉक (मोती) जोड़ते हैं, नक्शा खिंचता जाता है, लेकिन यह अनंत तक नहीं खिंचता।

3. "कंप्रेशन" (Compression) ट्रिक

कच्चा आईडी कार्ड (क्रमबद्ध छायाओं की सूची) बहुत बड़ा होता है। लेखकों ने दिखाया कि आप इस आईडी कार्ड को एक छोटे आकार में संकुचित (compress) कर सकते हैं (जिसे "स्केचिंग" तकनीक कहा जाता है) बिना थैलों के बीच अंतर करने की क्षमता खोए या उनकी दूरियों को बहुत अधिक प्रभावित किए।

उपमा: यह आपके मोतियों के थैले की उच्च-रिज़ॉल्यूशन वाली फोटो लेने और उसे JPEG में कंप्रेस करने जैसा है। फ़ाइल का आकार बहुत छोटा हो जाता है, लेकिन आप अभी भी थैले को पहचान सकते हैं और यह बता सकते हैं कि दो थैले समान हैं या नहीं।

यह क्यों मायने रखता है?

यह केवल अमूर्त गणित नहीं है। यह ग्राफ न्यूरल नेटवर्क (Graph Neural Networks) के पीछे का इंजन है, जिनका उपयोग किया जाता है:

ड्रग डिस्कवरी में अणुओं का विश्लेषण करने के लिए (परमाणु मोती हैं, बॉन्ड रंग हैं)।
सोशल नेटवर्क को समझने के लिए (लोग मोती हैं, मित्रता रंग हैं)।
सेल्फ-ड्राइविंग कारों में 3D पॉइंट क्लाउड को प्रोसेस करने के लिए।

इन सभी मामलों में, डेटा बिंदुओं का "क्रम" मनमाना होता है। यदि कंप्यूटर इसे नहीं संभाल सकता, तो वह विफल हो जाता है। यह पेपर इंजीनियरों को ऐसे सिस्टम बनाने के लिए एक "रेसिपी बुक" देता है:

अति-इंजीनियरिंग न करें: आपको लाखों फीचर्स की आवश्यकता नहीं है; कुछ सौ अच्छी तरह से चुने गए फीचर्स पर्याप्त हैं।
कुछ धुंधलेपन की अपेक्षा करें: आप एक पूर्ण, विकृति-मुक्त नक्शा नहीं पा सकते, लेकिन आप धुंधलेपन को नियंत्रण में रख सकते हैं।
सुरक्षित रूप से कंप्रेस करें: आप सिस्टम को तोड़े बिना डेटा के आकार को कम कर सकते हैं।

संक्षेप में

लेखकों ने एक शक्तिशाली लेकिन अव्यवस्थित गणितीय उपकरण (सॉर्टिंग प्रोजेक्शन) को लिया और उसे व्यवस्थित किया। उन्होंने यह पता लगाया कि इसे काम करने के लिए कितने "ईंधन" (डेटा आयामों) की आवश्यकता है और कितनी "घर्षण" (विकृति) की उम्मीद करनी चाहिए। उन्होंने एक सैद्धांतिक जिज्ञासा को अव्यवจัด डेटा को समझने के लिए एक व्यावहारिक, कुशल उपकरण में बदल दिया।

यहाँ शोध पत्र "Quantitative Bounds for Sorting-Based Permutation-Invariant Embeddings" का विस्तृत तकनीकी सारांश दिया गया है।

1. समस्या विवरण (Problem Statement)

यह शोध पत्र $n$ बिंदुओं के $d$ -आयामी स्थान ( $X \in \mathbb{R}^{n \times d}$ ) के लिए परम्यूटेशन-इनवेरिएंट एम्बेडिंग (permutation-invariant embeddings) के निर्माण की चुनौती को संबोधित करता है। कई मशीन लर्निंग अनुप्रयोगों (जैसे, ग्राफ न्यूरल नेटवर्क, पॉइंट क्लाउड प्रोसेसिंग) में, इनपुट एक मल्टीसेट होता है जहाँ तत्वों का क्रम अप्रासंगिक होता है। लक्ष्य इन सेटों को एक वेक्टर स्पेस में मैप करना है ताकि:

परम्यूटेशन इनवेरियेंस (Permutation Invariance): यदि इनपुट पंक्तियों (rows) को क्रमबद्ध (permute) किया जाता है, तो आउटपुट अपरिवर्तित रहता है।
ऑर्बिट सेपरेशन (Orbit Separation/Injectivity): भिन्न ऑर्बिट्स (ऐसे सेट जो एक-दूसरे के परम्यूटेशन नहीं हैं) भिन्न वेक्टर्स पर मैप होते हैं।
बी-लिप्सचिट्ज निरंतरता (Bi-Lipschitz Continuity): मैपिंग इनपुट स्पेस की ज्यामिति को संरक्षित करती है। विशेष रूप से, एम्बेडेड वेक्टर्स के बीच की दूरी, किसी भी परम्यूटेशन के तहत इनपुट सेटों के बीच की न्यूनतम दूरी (फ्रोबेनिअस ऑर्बिट दूरी) द्वारा ऊपर और नीचे दोनों ओर से सीमित होनी चाहिए।

विशिष्ट ध्यान सॉर्टिंग-आधारित एम्बेडिंग $\beta_A$ पर है, जिसे $D$ रैंडम दिशाओं $A \in \mathbb{R}^{d \times D}$ पर इनपुट $X$ को प्रोजेक्ट करके, परिणामी 1D प्रोजेक्शन को सॉर्ट करके और उन्हें संयोजित (concatenate) करके परिभाषित किया गया है:
$\beta_A(X) = \begin{pmatrix} \downarrow(Xa_1) \\ \vdots \\ \downarrow(Xa_D) \end{pmatrix}$
जहाँ $\downarrow(\cdot)$ गैर-घटते क्रम (non-decreasing order) में सॉर्टिंग को दर्शाता है।

मौजूदा अंतराल (Existing Gaps): पिछले कार्यों ने स्थापित किया कि पर्याप्त बड़े $D$ और जेनेरिक $A$ के लिए $\beta_A$ इनजेक्टिव और बी-लिप्सचिट्ज है। हालाँकि, दो महत्वपूर्ण मात्रात्मक अंतराल शेष थे:

इष्टतम आयाम (Optimal Dimension): इनजेक्टिविटी के लिए आवश्यक प्रोजेक्शन की सटीक न्यूनतम संख्या $D$ अज्ञात थी (पिछले बाउंड्स $n$ के सुपर-एक्सपोनेंशियल या क्वाड्रेटिक थे)।
डिस्टॉर्शन बाउंड्स (Distortion Bounds): बी-लिप्सचिट्ज डिस्टॉर्शन (ऊपरी और निचली लिप्सचिट्ज स्थिरांकों का अनुपात) के लिए कोई सटीक अनुमान मौजूद नहीं था, विशेष रूप से $n$ और $d$ पर इसकी निर्भरता के संबंध में।

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

लेखक कठोर बाउंड्स प्राप्त करने के लिए बीजगणितीय ज्यामिति (algebraic geometry), रैखिक बीजगणित (linear algebra), प्रायिकता सिद्धांत (probability theory), और संयोजन संबंधी तर्क (combinatorial arguments) के संयोजन का उपयोग करते हैं।

इनजेक्टिविटी विश्लेषण (Injectivity Analysis):
- वे फुल स्पार्क मैट्रिसेस (full spark matrices) की अवधारणा का उपयोग करते हैं (ऐसे मैट्रिक्स जहाँ $d$ कॉलम का प्रत्येक उपसमुच्चय रैखिक रूप से स्वतंत्र है)।
- वे उन स्थितियों का विश्लेषण करते हैं जिनमें $\beta_A(X) = \beta_A(Y)$ होने पर $X$ और $Y$ एक-दूसरे के परम्यूटेशन होते हैं। इसमें उन "खराब" प्रोजेक्शनों की गिनती शामिल है जहाँ सॉर्टिंग क्रम पंक्तियों के बीच अंतर करने में विफल रहता है।
- वे रैखिक प्रोजेक्शन ( $\delta_{A,B}$ और $\bar{\beta}_{A,L}$ ) के लिए इनजेक्टिविटी सिद्ध करने हेतु डोमेन की डाइमेंशनलिटी को कम करने के लिए वास्तविक बीजगणितीय ज्यामिति से फाइनाइट विटनेस थ्योरम (Finite Witness Theorem) लागू करते हैं।
डिस्टॉर्शन विश्लेषण (Distortion Analysis):
- ऊपरी बाउंड (Upper Bound): वे प्रोजेक्टिव यूनिफॉर्मिटी (projective uniformity) की अवधारणा पेश करते हैं। एक मैट्रिक्स $A$ , $(m, \delta)$ -प्रोजेक्टिवली यूनिफॉर्म है यदि, स्फीयर (sphere) पर किसी भी दिशा के लिए, कम से कम $D-m+1$ कॉलमों का प्रोजेक्शन मैग्नीट्यूड $\delta$ से अधिक है। यह गुण सुनिश्चित करता है कि निचला लिप्सचिट्ज स्थिरांक शून्य से दूर रहे।
- निर्माण (Constructions): वे विशिष्ट मैट्रिसेस $A$ ( $d=2$ के लिए नियतात्मक और सामान्य $d$ के लिए प्रायिकता-आधारित) का निर्माण करते हैं जो प्रोजेक्टिव यूनिफॉर्मिटी को संतुष्ट करते हैं।
- निचला बाउंड (Lower Bound): वे इनपुट सेट्स $X$ और $Y$ के विशिष्ट एडवर्सरियल उदाहरणों का निर्माण करते हैं ताकि यह सिद्ध किया जा सके कि डिस्टॉर्शन मनमाने ढंग से छोटा नहीं हो सकता है, जिससे एक मौलिक सीमा स्थापित होती है।
डाइमेंशन रिडक्शन (Dimension Reduction): वे ओब्लिवियस सबस्पेस एम्बेडिंग्स (OSE) (स्केचिंग) का उपयोग यह दिखाने के लिए करते हैं कि उच्च-आयामी एम्बेडिंग $\beta_A$ को बी-लिप्सचिट्ज गुणों को संरक्षित करते हुए रैखिक रूप से संकुचित किया जा सकता है।

3. मुख्य योगदान और परिणाम (Key Contributions and Results)

A. एम्बेडिंग डाइमेंशन बाउंड्स (इनजेक्टिविटी)

यह शोध पत्र इनजेक्टिविटी के लिए आवश्यक प्रोजेक्शन $D$ के बाउंड्स को महत्वपूर्ण रूप से कड़ा करता है।

$\beta_A$ के लिए ऊपरी बाउंड (Upper Bound):
- परिणाम: यदि $A$ फुल स्पार्क है और $D \ge n(d-1) + 1$ , तो $\beta_A$ इनजेक्टिव है।
- महत्व: यह $n$ के क्वाड्रेटिक बाउंड्स (जैसे, $D \sim n^2$ ) या सुपर-एक्सपोनेंशियल बाउंड्स में सुधार करता है। एम्बेडिंग डाइमेंशन $M = nD $का स्केल$ O(n^2 d)$ है।
$\beta_A$ के लिए निचला बाउंड (Lower Bound):
- परिणाम: यदि $D < (d-1)\log_2(n) + 1$ , तो किसी भी $A$ के चयन के लिए $\beta_A$ इनजेक्टिव नहीं है।
- महत्व: यह स्थापित करता है कि एम्बेडिंग डाइमेंशन कम से कम $\Omega(d \cdot n \log n)$ होना चाहिए। $\text{Lower bound } (\sim n \log n)$ और $\text{upper bound } (\sim n^2)$ के बीच एक अंतर बना हुआ है।
रैखिक प्रोजेक्शन ( $\delta_{A,B}$ और $\bar{\beta}_{A,L}$ ) के लिए बेहतर बाउंड्स:
- लेखक दिखाते हैं कि रैखिक रूप से प्रोजेक्ट किए गए संस्करणों के लिए, जेनेरिक मैट्रिसेस के लिए इनजेक्टिविटी तब गारंटीकृत होती है जब $D \ge (2n-1)d$ हो।
- यह पिछले $D \ge 2nd + 1$ की आवश्यकता में सुधार करता है और एम्बेडिंग डाइमेंशन को सैद्धांतिक निचले स्तर $nd$ के करीब लाता है।

B. बी-लिप्सचिट्ज डिस्टॉर्शन बाउंड्स (Bi-Lipschitz Distortion Bounds)

डिस्टॉर्शन पर ऊपरी बाउंड (सकारात्मक परिणाम):
- परिणाम: प्रोजेक्टिव यूनिफॉर्मिटी वाले मैट्रिसेस (जैसे, गॉसियन मैट्रिसेस या स्फीयर पर यूनिफॉर्म सैंपलिंग) का निर्माण करके, लेखक सिद्ध करते हैं कि $\beta_A$ का डिस्टॉर्शन $O(n^2)$ (या लॉगरिदमिक फैक्टर्स के साथ $\tilde{O}(n^2)$ ) के रूप में स्केल होता है।
- मुख्य अंतर्दृष्टि: महत्वपूर्ण रूप से, यह डिस्टॉर्शन बाउंड इनपुट डाइमेंशन $d$ से स्वतंत्र है।
- निहितार्थ: स्लाइसड वासरस्टीन दूरी (Sliced Wasserstein distance) की व्याख्या के लिए, इसका अर्थ है कि $D \sim n^2 d$ दिशाओं का मोंटे-कार्लो सन्निकटन (Monte-Carlo approximation) वास्तविक वासरस्टीन दूरी का एक बी-लिप्सचिट्ज सन्निकटन प्रदान करता है।
डिस्टॉर्शन पर निचला बाउंड (नकारात्मक परिणाम):
- परिणाम: लेखक सिद्ध करते हैं कि प्रोजेक्शन वेक्टर्स $A$ के किसी भी चुनाव के लिए, $\beta_A$ का डिस्टॉर्शन कम से कम $\Omega(\sqrt{n})$ है।
- महत्व: यह एक मौलिक सीमा स्थापित करता है: इस विशिष्ट सॉर्टिंग-आधारित आर्किटेक्चर के साथ स्थिर डिस्टॉर्शन ( $n$ से स्वतंत्र) प्राप्त नहीं किया जा सकता है। उपलब्ध $O(n^2)$ और निचली सीमा $\Omega(\sqrt{n})$ के बीच एक अंतर है।
स्केचिंग के माध्यम से डाइमेंशन रिडक्शन:
- परिणाम: रैंडम लीनियर प्रोजेक्शन (स्केचिंग) का उपयोग करके, लेखक दिखाते हैं कि मूल उच्च-आयामी मैप के $O(n^2)$ डिस्टॉर्शन को संरक्षित करते हुए एम्बेडिंग डाइमेंशन को $M \sim nd$ (लॉग फैक्टर्स तक) तक कम किया जा सकता है।

4. महत्व और प्रभाव (Significance and Impact)

ग्राफ लर्निंग के लिए सैद्धांतिक आधार: ये परिणाम ग्राफ न्यूरल नेटवर्क (GNNs) और सेट-आधारित लर्निंग में सॉर्टिंग-आधारित एम्बेडिंग्स के उपयोग के लिए कठोर औचित्य प्रदान करते हैं, जो यह गारंटी देते हैं कि भिन्न ग्राफ संरचनाओं को नियंत्रित ज्यामितीय डिस्टॉर्शन के साथ भिन्न निरूपणों (representations) में मैप किया गया है।
वासरस्टीन दूरी का सन्निकटन: यह कार्य सॉर्टिंग-आधारित एम्बेडिंग्स और स्लाइसड वासरस्टीन दूरी के बीच के अंतर को पाटता है। यह मात्रात्मक रूप से निर्धारित करता है कि वासरस्टीन दूरी का सन्निकटन करने के लिए कितने प्रोजेक्शन की आवश्यकता है, जो क्लस्टरिंग और निकटतम पड़ोसी खोज जैसे मेट्रिक लर्निंग कार्यों के लिए महत्वपूर्ण है।
इष्टतमता अंतराल (Optimality Gaps): पेपर वर्तमान ज्ञान के सटीक अंतराल की पहचान करता है:
- इनजेक्टिविटी के लिए आवश्यक $D \sim n \log n$ और पर्याप्त $D \sim n^2$ के बीच का अंतर।
- उपलब्ध $O(n^2)$ डिस्टॉर्शन और $\Omega(\sqrt{n})$ निचले बाउंड के बीच का अंतर।
व्यावहारिक मार्गदर्शन: परिणाम बताते हैं कि हालांकि सॉर्टिंग-आधारित विधियाँ सैद्धांतिक रूप से सुदृढ़ हैं, उन्हें अच्छे डिस्टॉर्शन गुणों को सुनिश्चित करने के लिए सेट के आकार $n$ के साथ द्विघातीय (quadratic) रूप से स्केल करने वाले प्रोजेक्शन की आवश्यकता होती है, जो कम्प्यूटेशनल लागत और ज्यामितीय शुद्धता के बीच एक ट्रेड-ऑफ (trade-off) प्रदान करता है।

5. निष्कर्ष (Conclusion)

यह शोध पत्र क्रमपरिवर्तन-अपरिवर्तनीय (permutation-invariant) एम्बेडिंग्स के मात्रात्मक विश्लेषण में पर्याप्त प्रगति करता है। यह इनजेक्टिविटी के लिए आवश्यक और पर्याप्त शर्तों को परिष्कृत करता है, जो सुपर-एक्सपोनेंशियल से बहुपद (polynomial) बाउंड्स की ओर ले जाता है, और पहला ठोस डिस्टॉर्शन अनुमान प्रदान करता है। हालांकि यह सिद्ध करता है कि डिस्टॉर्शन को $n$ के साथ बढ़ना ही होगा, यह यह भी प्रदर्शित करता है कि इस वृद्धि को डेटा डाइमेंशन $d$ से स्वतंत्र रूप से $O(n^2)$ तक नियंत्रित किया जा सकता है, जिससे ये एम्बेडिंग्स उच्च-आयामी सेट लर्निंग कार्यों के लिए व्यवहार्य बन जाते हैं।