यूक्लिडियन दूरी मैट्रिक्स: Difference between revisions

From Vigyanwiki
(Created page with "गणित में, यूक्लिडियन डिस्टेंस मैट्रिक्स एक है {{math|''n''×''n''}} मैट्रिक्स (...")
 
No edit summary
Line 3: Line 3:
वह है
वह है


:<math>\begin{align}
:कथन <math>\begin{align}
A & = (a_{ij}); \\
A & = (a_{ij}); \\
a_{ij} & = d_{ij}^2 \;=\; \lVert x_i - x_j\rVert^2
a_{ij} & = d_{ij}^2 \;=\; \lVert x_i - x_j\rVert^2
Line 17: Line 17:
d_{n1}^2 & d_{n2}^2 & d_{n3}^2 & \dots & 0 \\
d_{n1}^2 & d_{n2}^2 & d_{n3}^2 & \dots & 0 \\
\end{bmatrix} </math>
\end{bmatrix} </math>
(आवश्यक रूप से यूक्लिडियन नहीं) [[दूरी मैट्रिक्स]] के संदर्भ में, प्रविष्टियों को आमतौर पर सीधे दूरी के रूप में परिभाषित किया जाता है, उनके वर्ग नहीं।
(आवश्यक रूप से यूक्लिडियन नहीं) [[दूरी मैट्रिक्स]] के संदर्भ में, प्रविष्टियों को सामान्यतः सीधे दूरीअर्थात के रूप में परिभाषित किया जाता है, उनके वर्ग नहीं।
हालांकि, यूक्लिडियन मामले में, दूरियों के वर्गों का उपयोग वर्गमूलों की गणना से बचने और प्रासंगिक प्रमेयों और एल्गोरिदम को सरल बनाने के लिए किया जाता है।
चूंकि, यूक्लिडियन स्थितियोंमें, दूरियों के वर्गों का उपयोग वर्गमूलों की गणना से बचने और प्रासंगिक प्रमेयों और एल्गोरिदम को सरल बनाने के लिए किया जाता है।


यूक्लिडियन दूरी मैट्रिसेस [[ग्राम मैट्रिक्स]] ([[डॉट उत्पाद]]ों के मैट्रिसेस, उनके बीच वैक्टर और कोणों के मानदंडों का वर्णन करते हुए) से निकटता से संबंधित हैं।
यूक्लिडियन दूरी मैट्रिसेस [[ग्राम मैट्रिक्स]] ([[डॉट उत्पाद]]ों के मैट्रिसेस, उनके बीच वैक्टर और कोणों के मानदंडों का वर्णन करते हुए) से निकटता से संबंधित हैं।
रैखिक बीजगणित के तरीकों का उपयोग करके उत्तरार्द्ध का आसानी से विश्लेषण किया जाता है।
रैखिक बीजगणित के तरीकों का उपयोग करके उत्तरार्द्ध का आसानी से विश्लेषण किया जाता है।
यह यूक्लिडियन दूरी मैट्रिसेस को चिह्नित करने और अंक पुनर्प्राप्त करने की अनुमति देता है <math>x_1,x_2,\ldots,x_n</math> कि इसका एहसास हो।
यह यूक्लिडियन दूरी मैट्रिसेस को चिह्नित करने और अंक पुनर्प्राप्त करने की अनुमति देता है <math>x_1,x_2,\ldots,x_n</math> कि इसका एहसास हो।
एक बोध, यदि यह मौजूद है, [[कठोर परिवर्तन]]ों तक अद्वितीय है, अर्थात [[आइसोमेट्री]] | यूक्लिडियन अंतरिक्ष ([[रोटेशन (गणित)]], परावर्तन (गणित), [[अनुवाद (ज्यामिति)]]) के दूरी-संरक्षण परिवर्तन।
एक बोध, यदि यह उपस्तिथ है, [[कठोर परिवर्तन]]ों तक अद्वितीय है, अर्थात [[आइसोमेट्री]] | यूक्लिडियन अंतरिक्ष ([[रोटेशन (गणित)]], परावर्तन (गणित), [[अनुवाद (ज्यामिति)]]) के दूरी-संरक्षण परिवर्तन।


व्यावहारिक अनुप्रयोगों में, दूरियां शोर माप हैं या मनमाने ढंग से समानता माप अनुमानों से आती हैं (जरूरी नहीं कि [[मीट्रिक (गणित)]])।
व्यावहारिक अनुप्रयोगों में, दूरियां शोर माप हैं या मनमाने ढंग से समानता माप अनुमानों से आती हैं (आवश्यक  नहीं कि [[मीट्रिक (गणित)]])।
लक्ष्य यूक्लिडियन अंतरिक्ष में बिंदुओं द्वारा ऐसे डेटा की कल्पना करना हो सकता है, जिसकी दूरी मैट्रिक्स किसी दिए गए असमानता मैट्रिक्स के साथ-साथ संभव हो - इसे [[बहुआयामी स्केलिंग]] के रूप में जाना जाता है।
लक्ष्य यूक्लिडियन अंतरिक्ष में बिंदुओं द्वारा ऐसे डेटा की कल्पना करना हो सकता है, जिसकी दूरी मैट्रिक्स किसी दिए गए असमानता मैट्रिक्स के साथ-साथ संभव हो - इसे [[बहुआयामी स्केलिंग]] के रूप में जाना जाता है।
वैकल्पिक रूप से, डेटा के दो सेट पहले से ही यूक्लिडियन अंतरिक्ष में बिंदुओं द्वारा दर्शाए गए हैं, कोई पूछ सकता है कि वे आकार में कितने समान हैं, अर्थात, वे एक कठोर परिवर्तन से कितनी निकटता से संबंधित हो सकते हैं। दूरी-संरक्षण परिवर्तन - यह प्रोक्रस्ट्स विश्लेषण है।
वैकल्पिक रूप से, डेटा के दो सेट पहले से ही यूक्लिडियन अंतरिक्ष में बिंदुओं द्वारा दर्शाए गए हैं, कोई पूछ सकता है कि वे आकार में कितने समान हैं, अर्थात, वे एक कठोर परिवर्तन से कितनी निकटता से संबंधित हो सकते हैं। दूरी-संरक्षण परिवर्तन - यह प्रोक्रस्ट्स विश्लेषण है।
कुछ दूरियाँ गायब भी हो सकती हैं या बिना लेबल के आ सकती हैं (मैट्रिक्स के बजाय एक अनियंत्रित सेट या मल्टीसेट के रूप में), जिससे अधिक जटिल एल्गोरिथम कार्य हो सकते हैं, जैसे कि ग्राफ़ प्राप्ति समस्या या टर्नपाइक समस्या (एक रेखा पर बिंदुओं के लिए)।<ref name="DPRZ">{{harvtxt|Dokmanic|Parhizkar|Ranieri|Vetterli|2015}}</ref><ref>{{harvtxt|So|2007}}</ref>
कुछ दूरियाँ गायब भी हो सकती हैं या बिना लेबल के आ सकती हैं (मैट्रिक्स के अतिरिक्त एक अनियंत्रित सेट या मल्टीसेट के रूप में), जिससे अधिक जटिल एल्गोरिथम कार्य हो सकते हैं, जैसे कि ग्राफ़ प्राप्ति समस्या या टर्नपाइक समस्या (एक रेखा पर बिंदुओं के लिए)।<ref name="DPRZ">{{harvtxt|Dokmanic|Parhizkar|Ranieri|Vetterli|2015}}</ref><ref>{{harvtxt|So|2007}}</ref>
 
 
== गुण ==
== गुण ==


Line 36: Line 34:


* मैट्रिक्स के विकर्ण पर सभी तत्व {{mvar|''A''}} शून्य हैं (अर्थात यह एक [[खोखला मैट्रिक्स]] है); इसलिए [[एक मैट्रिक्स का निशान]] {{mvar|''A''}} शून्य है।
* मैट्रिक्स के विकर्ण पर सभी तत्व {{mvar|''A''}} शून्य हैं (अर्थात यह एक [[खोखला मैट्रिक्स]] है); इसलिए [[एक मैट्रिक्स का निशान]] {{mvar|''A''}} शून्य है।
* {{mvar|''A''}} [[सममित मैट्रिक्स]] है (यानी <math>a_{ij} = a_{ji}</math>).
* {{mvar|''A''}} [[सममित मैट्रिक्स]] है (अर्थात <math>a_{ij} = a_{ji}</math>).
* <math> \sqrt{a_{ij}} \le \sqrt{a_{ik}} + \sqrt{a_{kj}} </math> (त्रिकोण असमानता द्वारा)
* <math> \sqrt{a_{ij}} \le \sqrt{a_{ik}} + \sqrt{a_{kj}} </math> (त्रिकोण असमानता द्वारा)
* <math> a_{ij}\ge 0</math>
* <math> a_{ij}\ge 0</math>
आयाम में {{mvar|''k''}}, यूक्लिडियन दूरी मैट्रिक्स में [[रैंक (रैखिक बीजगणित)]] से कम या उसके बराबर है {{math|''k''+2}}. यदि अंक <math>x_1,x_2,\ldots,x_n</math> [[सामान्य स्थिति]] में हैं, रैंक बिल्कुल है {{math|min(''n'', ''k'' + 2).}}
आयाम में {{mvar|''k''}}, यूक्लिडियन दूरी मैट्रिक्स में [[रैंक (रैखिक बीजगणित)]] से कम या उसके बराबर है {{math|''k''+2}}. यदि अंक <math>x_1,x_2,\ldots,x_n</math> [[सामान्य स्थिति]] में हैं, रैंक बिल्कुल है {{math|min(''n'', ''k'' + 2).}}


एक और यूक्लिडियन दूरी मैट्रिक्स प्राप्त करने के लिए दूरियों को किसी भी शक्ति से कम किया जा सकता है। यानी अगर <math>A=(a_{ij})</math> एक यूक्लिडियन दूरी मैट्रिक्स है, तो <math>({a_{ij}}^s)</math> प्रत्येक के लिए एक यूक्लिडियन दूरी मैट्रिक्स है {{math|0<''s''<1}}.<ref>{{Cite journal |last=Maehara |first=Hiroshi |date=2013 |title=परिमित मीट्रिक रिक्त स्थान के यूक्लिडियन एम्बेडिंग|journal=Discrete Mathematics |language=en |volume=313 |issue=23 |pages=2848–2856 |doi=10.1016/j.disc.2013.08.029 |issn=0012-365X|doi-access=free }} Theorem 2.6</ref>
एक और यूक्लिडियन दूरी मैट्रिक्स प्राप्त करने के लिए दूरियों को किसी भी शक्ति से कम किया जा सकता है। अर्थात यदि <math>A=(a_{ij})</math> एक यूक्लिडियन दूरी मैट्रिक्स है, तो <math>({a_{ij}}^s)</math> प्रत्येक के लिए एक यूक्लिडियन दूरी मैट्रिक्स है {{math|0<''s''<1}}.<ref>{{Cite journal |last=Maehara |first=Hiroshi |date=2013 |title=परिमित मीट्रिक रिक्त स्थान के यूक्लिडियन एम्बेडिंग|journal=Discrete Mathematics |language=en |volume=313 |issue=23 |pages=2848–2856 |doi=10.1016/j.disc.2013.08.029 |issn=0012-365X|doi-access=free }} Theorem 2.6</ref>
 
 
== ग्राम मैट्रिक्स से संबंध ==
== ग्राम मैट्रिक्स से संबंध ==
अंकों के अनुक्रम का ग्राम मैट्रिक्स <math>x_1,x_2,\ldots,x_n</math> में {{mvar|''k''}}-विमीय स्थान {{math|ℝ<sup>''k''</sup>}}
अंकों के अनुक्रम का ग्राम मैट्रिक्स <math>x_1,x_2,\ldots,x_n</math> में {{mvar|''k''}}-विमीय स्थान {{math|ℝ<sup>''k''</sup>}}
Line 60: Line 56:
यूक्लिडियन दूरी मैट्रिक्स को ग्राम मैट्रिक्स से संबंधित करने के लिए, इसे देखें
यूक्लिडियन दूरी मैट्रिक्स को ग्राम मैट्रिक्स से संबंधित करने के लिए, इसे देखें
: <math>d_{ij}^2 = \|x_i - x_j\|^2 = (x_i - x_j)^\textsf{T} (x_i - x_j) = x_i^\textsf{T} x_i - 2x_i^\textsf{T} x_j + x_j^\textsf{T} x_j = g_{ii} -2g_{ij} + g_{jj}</math>
: <math>d_{ij}^2 = \|x_i - x_j\|^2 = (x_i - x_j)^\textsf{T} (x_i - x_j) = x_i^\textsf{T} x_i - 2x_i^\textsf{T} x_j + x_j^\textsf{T} x_j = g_{ii} -2g_{ij} + g_{jj}</math>
यानी मानदंड और कोण दूरी तय करते हैं।
अर्थात मानदंड और कोण दूरी तय करते हैं।
ध्यान दें कि ग्राम मैट्रिक्स में अतिरिक्त जानकारी होती है: 0 से दूरी।
ध्यान दें कि ग्राम मैट्रिक्स में अतिरिक्त जानकारी होती है: 0 से दूरी।


Line 69: Line 65:
== लक्षण वर्णन ==
== लक्षण वर्णन ==
एक के लिए {{math|''n''×''n''}} आव्यूह {{mvar|''A''}}, अंकों का एक क्रम <math>x_1,x_2,\ldots,x_n</math> में {{mvar|''k''}}-आयामी यूक्लिडियन स्थान {{math|ℝ<sup>''k''</sup>}}
एक के लिए {{math|''n''×''n''}} आव्यूह {{mvar|''A''}}, अंकों का एक क्रम <math>x_1,x_2,\ldots,x_n</math> में {{mvar|''k''}}-आयामी यूक्लिडियन स्थान {{math|ℝ<sup>''k''</sup>}}
का बोध कहा जाता है {{mvar|''A''}} में {{math|ℝ<sup>''k''</sup>}} अगर {{mvar|''A''}} उनकी यूक्लिडियन दूरी मैट्रिक्स है।
का बोध कहा जाता है {{mvar|''A''}} में {{math|ℝ<sup>''k''</sup>}} यदि {{mvar|''A''}} उनकी यूक्लिडियन दूरी मैट्रिक्स है।
कोई सामान्यता के नुकसान के बिना मान सकता है कि <math>x_1 = \mathbf{0}</math> (क्योंकि अनुवाद (ज्यामिति) द्वारा <math>-x_1</math> दूरी बनाए रखता है)।
कोई सामान्यता के नुकसान के बिना मान सकता है कि <math>x_1 = \mathbf{0}</math> (क्योंकि अनुवाद (ज्यामिति) द्वारा <math>-x_1</math> दूरी बनाए रखता है)।


Line 80: Line 76:
is [[positive semidefinite matrix|positive semidefinite]] and has [[matrix rank|rank]] at most {{mvar|''k''}}.
is [[positive semidefinite matrix|positive semidefinite]] and has [[matrix rank|rank]] at most {{mvar|''k''}}.
}}
}}
यह पिछली चर्चा से इस प्रकार है क्योंकि {{mvar|''G''}} अधिक से अधिक रैंक का धनात्मक अर्धनिश्चित है {{mvar|''k''}} अगर और केवल अगर इसे विघटित किया जा सकता है <math>G = X^\textsf{T} X</math> कहाँ {{mvar|''X''}} एक {{math|''k''×''n''}} आव्यूह।<ref>{{harvtxt|So|2007}}, Theorem 2.2.1, p. 10</ref>
यह पिछली चर्चा से इस प्रकार है क्योंकि {{mvar|''G''}} अधिक से अधिक रैंक का धनात्मक अर्धनिश्चित है {{mvar|''k''}} यदि और केवल यदि इसे विघटित किया जा सकता है <math>G = X^\textsf{T} X</math> कहाँ {{mvar|''X''}} एक {{math|''k''×''n''}} आव्यूह।<ref>{{harvtxt|So|2007}}, Theorem 2.2.1, p. 10</ref>
इसके अलावा, के कॉलम {{mvar|''X''}} में एक अहसास दें {{math|ℝ<sup>''k''</sup>}}.
इसके अतिरिक्त, के कॉलम {{mvar|''X''}} में एक अहसास दें {{math|ℝ<sup>''k''</sup>}}.
इसलिए, किसी भी विधि को विघटित करने के लिए {{mvar|''G''}} एक अहसास खोजने की अनुमति देता है।
इसलिए, किसी भी विधि को विघटित करने के लिए {{mvar|''G''}} एक अहसास खोजने की अनुमति देता है।
दो मुख्य दृष्टिकोण चॉल्स्की अपघटन के प्रकार हैं या मैट्रिक्स के वर्ग रूट को खोजने के लिए [[eigendecomposition]] का उपयोग करना {{mvar|''G''}}, निश्चित मैट्रिक्स#अपघटन देखें।
दो मुख्य दृष्टिकोण चॉल्स्की अपघटन के प्रकार हैं या मैट्रिक्स के वर्ग रूट को खोजने के लिए [[eigendecomposition]] का उपयोग करना {{mvar|''G''}}, निश्चित मैट्रिक्स#अपघटन देखें।
Line 91: Line 87:
: <math>v^\textsf{T} A v \leq 0</math> for all <math>v \in \mathbf{R}^n</math> such that <math>\textstyle\sum_{i=1}^n v_i = 0</math>.
: <math>v^\textsf{T} A v \leq 0</math> for all <math>v \in \mathbf{R}^n</math> such that <math>\textstyle\sum_{i=1}^n v_i = 0</math>.
}}
}}
अन्य लक्षण वर्णन में केली-मेंजर निर्धारक शामिल है।
अन्य लक्षण वर्णन में केली-मेंजर निर्धारक सम्मिलित है।
विशेष रूप से, ये एक सममित खोखला मैट्रिक्स दिखाने की अनुमति देते हैं {{math|''n''×''n''}} मैट्रिक्स में वसूली योग्य है {{math|ℝ<sup>''k''</sup>}} अगर और केवल अगर हर {{math|(''k''+3)×(''k''+3)}} [[प्रिंसिपल सबमैट्रिक्स]] है।
विशेष रूप से, ये एक सममित खोखला मैट्रिक्स दिखाने की अनुमति देते हैं {{math|''n''×''n''}} मैट्रिक्स में वसूली योग्य है {{math|ℝ<sup>''k''</sup>}} यदि और केवल यदि हर {{math|(''k''+3)×(''k''+3)}} [[प्रिंसिपल सबमैट्रिक्स]] है।
दूसरे शब्दों में, एक मीट्रिक (गणित)#अर्धमिति बहुत से बिंदुओं पर आइसोमेट्री है {{math|ℝ<sup>''k''</sup>}} अगर और केवल अगर हर  {{math|''k''+3}} अंक हैं।<ref>
दूसरे शब्दों में, एक मीट्रिक (गणित)#अर्धमिति बहुत से बिंदुओं पर आइसोमेट्री है {{math|ℝ<sup>''k''</sup>}} यदि और केवल यदि हर  {{math|''k''+3}} अंक हैं।<ref>
{{Cite journal |last=Menger |first=Karl |date=1931 |title=New Foundation of Euclidean Geometry |journal=American Journal of Mathematics |volume=53 |issue=4 |pages=721–745 |doi=10.2307/2371222|jstor=2371222 }}
{{Cite journal |last=Menger |first=Karl |date=1931 |title=New Foundation of Euclidean Geometry |journal=American Journal of Mathematics |volume=53 |issue=4 |pages=721–745 |doi=10.2307/2371222|jstor=2371222 }}
</ref>
</ref>
Line 101: Line 97:
इन विधियों के विभिन्न प्रकार अपूर्ण दूरी डेटा से भी निपट सकते हैं।
इन विधियों के विभिन्न प्रकार अपूर्ण दूरी डेटा से भी निपट सकते हैं।


बिना लेबल वाला डेटा, यानी, दूरियों का एक सेट या मल्टीसेट जो विशेष जोड़े को नहीं सौंपा गया है, इससे निपटना बहुत मुश्किल है।
बिना लेबल वाला डेटा, अर्थात, दूरियों का एक सेट या मल्टीसेट जो विशेष जोड़े को नहीं सौंपा गया है, इससे निपटना बहुत कठिनाई है।
इस तरह के डेटा उत्पन्न होते हैं, उदाहरण के लिए, डीएनए अनुक्रमण में (विशेष रूप से, [[प्रतिबंध डाइजेस्ट]] से जीनोम रिकवरी) या चरण समस्या।
इस तरह के डेटा उत्पन्न होते हैं, उदाहरण के लिए, डीएनए अनुक्रमण में (विशेष रूप से, [[प्रतिबंध डाइजेस्ट]] से जीनोम रिकवरी) या चरण समस्या।
बिंदुओं के दो सेटों को [[ समरूप संरचनाएं ]] कहा जाता है यदि उनके पास दूरियों का एक ही मल्टीसेट हो (लेकिन जरूरी नहीं कि वे एक कठोर परिवर्तन से संबंधित हों)।
बिंदुओं के दो सेटों को [[ समरूप संरचनाएं ]] कहा जाता है यदि उनके पास दूरियों का एक ही मल्टीसेट हो (किन्तु आवश्यक  नहीं कि वे एक कठोर परिवर्तन से संबंधित हों)।
यह तय करना कि क्या दिया गया मल्टीसेट है {{math|''n''(''n''-1)/2}} दिए गए आयाम में दूरी महसूस की जा सकती है {{mvar|''k''}} जोरदार [[ एनपी कठिन ]] है।
यह तय करना कि क्या दिया गया मल्टीसेट है {{math|''n''(''n''-1)/2}} दिए गए आयाम में दूरी महसूस की जा सकती है {{mvar|''k''}} जोरदार [[ एनपी कठिन ]] है।
एक आयाम में इसे टर्नपाइक समस्या के रूप में जाना जाता है; यह एक खुला प्रश्न है कि क्या इसे बहुपद समय में हल किया जा सकता है।
एक आयाम में इसे टर्नपाइक समस्या के रूप में जाना जाता है; यह एक खुला प्रश्न है कि क्या इसे बहुपद समय में हल किया जा सकता है।
जब त्रुटि सलाखों के साथ दूरियों का मल्टीसेट दिया जाता है, तब भी एक आयामी मामला एनपी-हार्ड होता है।
जब त्रुटि सलाखों के साथ दूरियों का मल्टीसेट दिया जाता है, तब भी एक आयामी मामला एनपी-हार्ड होता है।
फिर भी, कई मामलों के लिए व्यावहारिक एल्गोरिदम मौजूद हैं, उदा। यादृच्छिक बिंदु।<ref>{{Cite book |title=असतत और कम्प्यूटेशनल ज्यामिति|last1=Lemke |first1=Paul |chapter=Reconstructing Sets From Interpoint Distances |last2=Skiena |first2=Steven S. |last3=Smith |first3=Warren D. |date=2003 |publisher=Springer Berlin Heidelberg |isbn=978-3-642-62442-1 |editor-last=Aronov |editor-first=Boris |volume=25 |location=Berlin, Heidelberg |pages=597–631 |doi=10.1007/978-3-642-55566-4_27 |editor-last2=Basu |editor-first2=Saugata |editor-last3=Pach |editor-first3=János |editor-last4=Sharir |editor-first4=Micha}}</ref><ref>{{Cite journal |arxiv=1804.02465 |title=दूरस्थ वितरण से पुन: निर्माण बिंदु समूह|first1=Shuai |last1=Huang |first2=Ivan |last2=Dokmanić |journal=IEEE Transactions on Signal Processing |year=2021|volume=69 |pages=1811–1827 |doi=10.1109/TSP.2021.3063458 |s2cid=4746784 }}</ref><ref>{{Cite arXiv |eprint=1212.2386 |title=जोड़ीवार दूरियों से पूर्णांकों का पुनर्निर्माण|first1=Kishore |last1=Jaganathan |first2=Babak |last2=Hassibi|year=2012 |class=cs.DM }}</ref>
फिर भी, कई स्थितियों के लिए व्यावहारिक एल्गोरिदम उपस्तिथ हैं, उदा। यादृच्छिक बिंदु।<ref>{{Cite book |title=असतत और कम्प्यूटेशनल ज्यामिति|last1=Lemke |first1=Paul |chapter=Reconstructing Sets From Interpoint Distances |last2=Skiena |first2=Steven S. |last3=Smith |first3=Warren D. |date=2003 |publisher=Springer Berlin Heidelberg |isbn=978-3-642-62442-1 |editor-last=Aronov |editor-first=Boris |volume=25 |location=Berlin, Heidelberg |pages=597–631 |doi=10.1007/978-3-642-55566-4_27 |editor-last2=Basu |editor-first2=Saugata |editor-last3=Pach |editor-first3=János |editor-last4=Sharir |editor-first4=Micha}}</ref><ref>{{Cite journal |arxiv=1804.02465 |title=दूरस्थ वितरण से पुन: निर्माण बिंदु समूह|first1=Shuai |last1=Huang |first2=Ivan |last2=Dokmanić |journal=IEEE Transactions on Signal Processing |year=2021|volume=69 |pages=1811–1827 |doi=10.1109/TSP.2021.3063458 |s2cid=4746784 }}</ref><ref>{{Cite arXiv |eprint=1212.2386 |title=जोड़ीवार दूरियों से पूर्णांकों का पुनर्निर्माण|first1=Kishore |last1=Jaganathan |first2=Babak |last2=Hassibi|year=2012 |class=cs.DM }}</ref>
 
 
== अभ्यावेदन की विशिष्टता ==
== अभ्यावेदन की विशिष्टता ==
एक यूक्लिडियन दूरी मैट्रिक्स को देखते हुए, बिंदुओं का क्रम जो यह महसूस करता है कि यह कठोर परिवर्तनों तक अद्वितीय है - ये यूक्लिडियन अंतरिक्ष की आइसोमेट्री हैं: रोटेशन (गणित), परावर्तन (गणित), अनुवाद (ज्यामिति), और उनकी रचनाएँ।<ref name="DPRZ"/>
एक यूक्लिडियन दूरी मैट्रिक्स को देखते हुए, बिंदुओं का क्रम जो यह महसूस करता है कि यह कठोर परिवर्तनों तक अद्वितीय है - ये यूक्लिडियन अंतरिक्ष की आइसोमेट्री हैं: रोटेशन (गणित), परावर्तन (गणित), अनुवाद (ज्यामिति), और उनकी रचनाएँ।<ref name="DPRZ"/>
Line 129: Line 123:




अनुप्रयोगों में, जब दूरियां सटीक रूप से मेल नहीं खाती हैं, तो प्रोक्रेस्ट्स विश्लेषण का लक्ष्य दो बिंदु सेटों को कठोर परिवर्तनों के माध्यम से जितना संभव हो उतना करीब से जोड़ना है, आमतौर पर एकवचन मूल्य अपघटन का उपयोग करना।
अनुप्रयोगों में, जब दूरियां त्रुटिहीन रूप से मेल नहीं खाती हैं, तो प्रोक्रेस्ट्स विश्लेषण का लक्ष्य दो बिंदु सेटों को कठोर परिवर्तनों के माध्यम से जितना संभव हो उतना करीब से जोड़ना है, सामान्यतः एकवचन मूल्य अपघटन का उपयोग करना।
साधारण यूक्लिडियन मामले को [[ऑर्थोगोनल प्रोक्रस्ट्स समस्या]] या वाहबा की समस्या के रूप में जाना जाता है (जब टिप्पणियों को अलग-अलग अनिश्चितताओं के लिए भारित किया जाता है)।
साधारण यूक्लिडियन स्थितियोंको [[ऑर्थोगोनल प्रोक्रस्ट्स समस्या]] या वाहबा की समस्या के रूप में जाना जाता है (जब टिप्पणियों को अलग-अलग अनिश्चितताओं के लिए भारित किया जाता है)।
अनुप्रयोगों के उदाहरणों में उपग्रहों के झुकाव का निर्धारण करना, अणु संरचना (रसायन सूचना विज्ञान में), प्रोटीन संरचना (जैव सूचना विज्ञान में [[संरचनात्मक संरेखण]]), या हड्डी संरचना (जीव विज्ञान में [[सांख्यिकीय आकार विश्लेषण]]) की तुलना करना शामिल है।
अनुप्रयोगों के उदाहरणों में उपग्रहों के झुकाव का निर्धारण करना, अणु संरचना (रसायन सूचना विज्ञान में), प्रोटीन संरचना (जैव सूचना विज्ञान में [[संरचनात्मक संरेखण]]), या हड्डी संरचना (जीव विज्ञान में [[सांख्यिकीय आकार विश्लेषण]]) की तुलना करना सम्मिलित है।


== यह भी देखें ==
== यह भी देखें ==
Line 140: Line 134:
* दूरी मैट्रिक्स
* दूरी मैट्रिक्स
* [[यूक्लिडियन यादृच्छिक मैट्रिक्स]]
* [[यूक्लिडियन यादृच्छिक मैट्रिक्स]]
* शास्त्रीय बहुआयामी स्केलिंग, एक विज़ुअलाइज़ेशन तकनीक जो एक यूक्लिडियन दूरी मैट्रिक्स द्वारा एक मनमाना असमानता मैट्रिक्स का अनुमान लगाती है
* मौलिक  बहुआयामी स्केलिंग, एक विज़ुअलाइज़ेशन तकनीक जो एक यूक्लिडियन दूरी मैट्रिक्स द्वारा एक मनमाना असमानता मैट्रिक्स का अनुमान लगाती है
* केली-मेंजर निर्धारक
* केली-मेंजर निर्धारक
* [[अर्ध निश्चित एम्बेडिंग]]
* [[अर्ध निश्चित एम्बेडिंग]]

Revision as of 19:21, 27 April 2023

गणित में, यूक्लिडियन डिस्टेंस मैट्रिक्स एक है n×n मैट्रिक्स (गणित) के एक सेट के अंतर का प्रतिनिधित्व करता है {{mvar|n}यूक्लिडियन अंतरिक्ष में } बिंदु (ज्यामिति)। अंक के लिए में k-विमीय स्थान k, उनके यूक्लिडियन दूरी मैट्रिक्स के तत्व A उनके बीच की दूरियों के वर्ग द्वारा दिए गए हैं। वह है

कथन

कहाँ यूक्लिडियन मानदंड को दर्शाता है k.

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

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

व्यावहारिक अनुप्रयोगों में, दूरियां शोर माप हैं या मनमाने ढंग से समानता माप अनुमानों से आती हैं (आवश्यक नहीं कि मीट्रिक (गणित))। लक्ष्य यूक्लिडियन अंतरिक्ष में बिंदुओं द्वारा ऐसे डेटा की कल्पना करना हो सकता है, जिसकी दूरी मैट्रिक्स किसी दिए गए असमानता मैट्रिक्स के साथ-साथ संभव हो - इसे बहुआयामी स्केलिंग के रूप में जाना जाता है। वैकल्पिक रूप से, डेटा के दो सेट पहले से ही यूक्लिडियन अंतरिक्ष में बिंदुओं द्वारा दर्शाए गए हैं, कोई पूछ सकता है कि वे आकार में कितने समान हैं, अर्थात, वे एक कठोर परिवर्तन से कितनी निकटता से संबंधित हो सकते हैं। दूरी-संरक्षण परिवर्तन - यह प्रोक्रस्ट्स विश्लेषण है। कुछ दूरियाँ गायब भी हो सकती हैं या बिना लेबल के आ सकती हैं (मैट्रिक्स के अतिरिक्त एक अनियंत्रित सेट या मल्टीसेट के रूप में), जिससे अधिक जटिल एल्गोरिथम कार्य हो सकते हैं, जैसे कि ग्राफ़ प्राप्ति समस्या या टर्नपाइक समस्या (एक रेखा पर बिंदुओं के लिए)।[1][2]

गुण

इस तथ्य से कि यूक्लिडियन दूरी एक मीट्रिक (गणित) है, मैट्रिक्स है A में निम्नलिखित गुण होते हैं।

आयाम में k, यूक्लिडियन दूरी मैट्रिक्स में रैंक (रैखिक बीजगणित) से कम या उसके बराबर है k+2. यदि अंक सामान्य स्थिति में हैं, रैंक बिल्कुल है min(n, k + 2).

एक और यूक्लिडियन दूरी मैट्रिक्स प्राप्त करने के लिए दूरियों को किसी भी शक्ति से कम किया जा सकता है। अर्थात यदि एक यूक्लिडियन दूरी मैट्रिक्स है, तो प्रत्येक के लिए एक यूक्लिडियन दूरी मैट्रिक्स है 0<s<1.[3]

ग्राम मैट्रिक्स से संबंध

अंकों के अनुक्रम का ग्राम मैट्रिक्स में k-विमीय स्थान k है n×n आव्यूह उनके डॉट उत्पाद (यहां एक बिंदु 0 से उस बिंदु तक वेक्टर के रूप में माना जाता है):

, कहाँ वेक्टर के बीच का कोण है और .

विशेष रूप से

की दूरी का वर्ग है 0 से।

इस प्रकार ग्राम मैट्रिक्स वैक्टर के मानदंडों और कोणों का वर्णन करता है (0 से) .

होने देना हो k×n मैट्रिक्स युक्त स्तंभों के रूप में। तब

, क्योंकि (देख के कॉलम वेक्टर के रूप में)।

मैट्रिसेस जिन्हें विघटित किया जा सकता है , अर्थात्, सदिशों के कुछ अनुक्रमों के ग्राम आव्यूह (के स्तंभ ), अच्छी तरह से समझ गए हैं - ये ठीक सकारात्मक अर्ध निश्चित मैट्रिक्स हैं।


यूक्लिडियन दूरी मैट्रिक्स को ग्राम मैट्रिक्स से संबंधित करने के लिए, इसे देखें

अर्थात मानदंड और कोण दूरी तय करते हैं। ध्यान दें कि ग्राम मैट्रिक्स में अतिरिक्त जानकारी होती है: 0 से दूरी।

इसके विपरीत दूरियां के जोड़े के बीच n+1 अंक के बीच डॉट उत्पाद निर्धारित करें n वैक्टर (1≤in):

(इसे ध्रुवीकरण पहचान के रूप में जाना जाता है)।

लक्षण वर्णन

एक के लिए n×n आव्यूह A, अंकों का एक क्रम में k-आयामी यूक्लिडियन स्थान k का बोध कहा जाता है A में k यदि A उनकी यूक्लिडियन दूरी मैट्रिक्स है। कोई सामान्यता के नुकसान के बिना मान सकता है कि (क्योंकि अनुवाद (ज्यामिति) द्वारा दूरी बनाए रखता है)।

Theorem[4] (Schoenberg criterion,[5] independently shown by Young & Householder[6]) —  A symmetric hollow n×n matrix A with real entries admits a realization in k if and only if the (n-1)×(n-1) matrix defined by

is positive semidefinite and has rank at most k.

यह पिछली चर्चा से इस प्रकार है क्योंकि G अधिक से अधिक रैंक का धनात्मक अर्धनिश्चित है k यदि और केवल यदि इसे विघटित किया जा सकता है कहाँ X एक k×n आव्यूह।[7] इसके अतिरिक्त, के कॉलम X में एक अहसास दें k. इसलिए, किसी भी विधि को विघटित करने के लिए G एक अहसास खोजने की अनुमति देता है। दो मुख्य दृष्टिकोण चॉल्स्की अपघटन के प्रकार हैं या मैट्रिक्स के वर्ग रूट को खोजने के लिए eigendecomposition का उपयोग करना G, निश्चित मैट्रिक्स#अपघटन देखें।

प्रमेय का कथन पहले बिंदु को अलग करता है . उसी प्रमेय का एक अधिक सममित संस्करण निम्नलिखित है:

Corollary[8] —  A symmetric hollow n×n matrix A with real entries admits a realization if and only if A is negative semidefinite on the hyperplane , that is

for all such that .

अन्य लक्षण वर्णन में केली-मेंजर निर्धारक सम्मिलित है। विशेष रूप से, ये एक सममित खोखला मैट्रिक्स दिखाने की अनुमति देते हैं n×n मैट्रिक्स में वसूली योग्य है k यदि और केवल यदि हर (k+3)×(k+3) प्रिंसिपल सबमैट्रिक्स है। दूसरे शब्दों में, एक मीट्रिक (गणित)#अर्धमिति बहुत से बिंदुओं पर आइसोमेट्री है k यदि और केवल यदि हर k+3 अंक हैं।[9] व्यवहार में, संख्यात्मक त्रुटियों, माप में शोर, या वास्तविक यूक्लिडियन दूरी से डेटा नहीं आने के कारण निश्चितता या रैंक की स्थिति विफल हो सकती है। ऐसे बिंदु जो इष्टतम समान दूरी का एहसास करते हैं, फिर एकवचन मूल्य अपघटन या अर्ध-निश्चित प्रोग्रामिंग जैसे रैखिक बीजगणितीय उपकरण का उपयोग करके सेमीडिफिनिट सन्निकटन (और निम्न रैंक सन्निकटन, यदि वांछित हो) द्वारा पाया जा सकता है। इसे बहुआयामी स्केलिंग के रूप में जाना जाता है। इन विधियों के विभिन्न प्रकार अपूर्ण दूरी डेटा से भी निपट सकते हैं।

बिना लेबल वाला डेटा, अर्थात, दूरियों का एक सेट या मल्टीसेट जो विशेष जोड़े को नहीं सौंपा गया है, इससे निपटना बहुत कठिनाई है। इस तरह के डेटा उत्पन्न होते हैं, उदाहरण के लिए, डीएनए अनुक्रमण में (विशेष रूप से, प्रतिबंध डाइजेस्ट से जीनोम रिकवरी) या चरण समस्या। बिंदुओं के दो सेटों को समरूप संरचनाएं कहा जाता है यदि उनके पास दूरियों का एक ही मल्टीसेट हो (किन्तु आवश्यक नहीं कि वे एक कठोर परिवर्तन से संबंधित हों)। यह तय करना कि क्या दिया गया मल्टीसेट है n(n-1)/2 दिए गए आयाम में दूरी महसूस की जा सकती है k जोरदार एनपी कठिन है। एक आयाम में इसे टर्नपाइक समस्या के रूप में जाना जाता है; यह एक खुला प्रश्न है कि क्या इसे बहुपद समय में हल किया जा सकता है। जब त्रुटि सलाखों के साथ दूरियों का मल्टीसेट दिया जाता है, तब भी एक आयामी मामला एनपी-हार्ड होता है। फिर भी, कई स्थितियों के लिए व्यावहारिक एल्गोरिदम उपस्तिथ हैं, उदा। यादृच्छिक बिंदु।[10][11][12]

अभ्यावेदन की विशिष्टता

एक यूक्लिडियन दूरी मैट्रिक्स को देखते हुए, बिंदुओं का क्रम जो यह महसूस करता है कि यह कठोर परिवर्तनों तक अद्वितीय है - ये यूक्लिडियन अंतरिक्ष की आइसोमेट्री हैं: रोटेशन (गणित), परावर्तन (गणित), अनुवाद (ज्यामिति), और उनकी रचनाएँ।[1]

Theorem —  Let and be two sequences of points in k-dimensional Euclidean space k. The distances and are equal (for all 1≤i,jn) if and only if there is a rigid transformation of k mapping to (for all 1≤in).

style="background: #F0F2F5; font-size:87%; padding:0.2em 0.3em; text-align:center; " |
Proof

कठोर परिवर्तन दूरियों को बनाए रखते हैं इसलिए एक दिशा स्पष्ट होती है। मान लीजिए दूरियां और बराबर हैं। व्यापकता के नुकसान के बिना हम मान सकते हैं द्वारा बिंदुओं का अनुवाद करके और , क्रमश। फिर (n-1)×(n-1) शेष सदिशों का ग्राम आव्यूह सदिशों के ग्राम आव्यूह के समान है (2≤in). वह है, , कहाँ X और Y हैं k×(n-1) कॉलम के रूप में संबंधित वैक्टर युक्त मैट्रिसेस। इसका तात्पर्य है कि एक ऑर्थोगोनल मैट्रिक्स मौजूद है k×k आव्यूह Q ऐसा है कि QX=Y, निश्चित सममित मैट्रिक्स देखें#एकात्मक परिवर्तनों तक अद्वितीयता। Q के एक ओर्थोगोनल परिवर्तन का वर्णन करता है k (अनुवाद के बिना घुमावों और प्रतिबिंबों की रचना) जो मैप करता है को (और 0 से 0)। अंतिम कठोर परिवर्तन द्वारा वर्णित है .


अनुप्रयोगों में, जब दूरियां त्रुटिहीन रूप से मेल नहीं खाती हैं, तो प्रोक्रेस्ट्स विश्लेषण का लक्ष्य दो बिंदु सेटों को कठोर परिवर्तनों के माध्यम से जितना संभव हो उतना करीब से जोड़ना है, सामान्यतः एकवचन मूल्य अपघटन का उपयोग करना। साधारण यूक्लिडियन स्थितियोंको ऑर्थोगोनल प्रोक्रस्ट्स समस्या या वाहबा की समस्या के रूप में जाना जाता है (जब टिप्पणियों को अलग-अलग अनिश्चितताओं के लिए भारित किया जाता है)। अनुप्रयोगों के उदाहरणों में उपग्रहों के झुकाव का निर्धारण करना, अणु संरचना (रसायन सूचना विज्ञान में), प्रोटीन संरचना (जैव सूचना विज्ञान में संरचनात्मक संरेखण), या हड्डी संरचना (जीव विज्ञान में सांख्यिकीय आकार विश्लेषण) की तुलना करना सम्मिलित है।

यह भी देखें

टिप्पणियाँ

  1. 1.0 1.1 Dokmanic et al. (2015)
  2. So (2007)
  3. Maehara, Hiroshi (2013). "परिमित मीट्रिक रिक्त स्थान के यूक्लिडियन एम्बेडिंग". Discrete Mathematics (in English). 313 (23): 2848–2856. doi:10.1016/j.disc.2013.08.029. ISSN 0012-365X. Theorem 2.6
  4. So (2007), Theorem 3.3.1, p. 40
  5. Schoenberg, I. J. (1935). "Remarks to Maurice Fréchet's Article "Sur La Definition Axiomatique D'Une Classe D'Espace Distances Vectoriellement Applicable Sur L'Espace De Hilbert"". Annals of Mathematics. 36 (3): 724–732. doi:10.2307/1968654. ISSN 0003-486X. JSTOR 1968654.
  6. Young, Gale; Householder, A. S. (1938-03-01). "Discussion of a set of points in terms of their mutual distances". Psychometrika (in English). 3 (1): 19–22. doi:10.1007/BF02287916. ISSN 1860-0980. S2CID 122400126.
  7. So (2007), Theorem 2.2.1, p. 10
  8. So (2007), Corollary 3.3.3, p. 42
  9. Menger, Karl (1931). "New Foundation of Euclidean Geometry". American Journal of Mathematics. 53 (4): 721–745. doi:10.2307/2371222. JSTOR 2371222.
  10. Lemke, Paul; Skiena, Steven S.; Smith, Warren D. (2003). "Reconstructing Sets From Interpoint Distances". In Aronov, Boris; Basu, Saugata; Pach, János; Sharir, Micha (eds.). असतत और कम्प्यूटेशनल ज्यामिति. Vol. 25. Berlin, Heidelberg: Springer Berlin Heidelberg. pp. 597–631. doi:10.1007/978-3-642-55566-4_27. ISBN 978-3-642-62442-1.
  11. Huang, Shuai; Dokmanić, Ivan (2021). "दूरस्थ वितरण से पुन: निर्माण बिंदु समूह". IEEE Transactions on Signal Processing. 69: 1811–1827. arXiv:1804.02465. doi:10.1109/TSP.2021.3063458. S2CID 4746784.
  12. Jaganathan, Kishore; Hassibi, Babak (2012). "जोड़ीवार दूरियों से पूर्णांकों का पुनर्निर्माण". arXiv:1212.2386 [cs.DM].


संदर्भ