लेविंसन रिकर्सन

लेविंसन प्रत्यावर्तन या लेविंसन-डर्बिन रिकर्सन, टोएप्लिट्ज़ मैट्रिक्स से जुड़े समीकरण के समाधान की गणना करने के लिए रैखिक बीजगणित में एक प्रक्रिया है। कलन विधि चलता है Θ(n²) समय, जो गॉस-जॉर्डन उन्मूलन पर एक मजबूत सुधार है, जो Θ(n) में चलता है³).

लेविंसन-डर्बिन एल्गोरिथ्म को सबसे पहले 1947 में नॉर्मन लेविंसन द्वारा प्रस्तावित किया गया था, जिसे 1960 में जेम्स डर्बिन द्वारा सुधारा गया और बाद में इसमें सुधार किया गया। 4n² और तब 3n² क्रमशः डब्ल्यू.एफ. ट्रेंच और एस. ज़ोहर द्वारा गुणन।

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

टोप्लिट्ज़ मैट्रिक्स के लिए बेरिस एल्गोरिथ्म (सामान्य बेरिस एल्गोरिदम के साथ भ्रमित नहीं होना चाहिए) लेविंसन रिकर्सन जितना तेज़ चलता है, लेकिन यह इसका उपयोग करता है O(n²) स्पेस, जबकि लेविंसन रिकर्सन केवल O(n) स्पेस का उपयोग करता है। हालाँकि, बेरिस एल्गोरिथ्म संख्यात्मक स्थिरता है, जबकि लेविंसन रिकर्सन केवल कमजोर रूप से स्थिर है (यानी यह स्थिति संख्या | अच्छी तरह से वातानुकूलित रैखिक प्रणालियों के लिए संख्यात्मक स्थिरता प्रदर्शित करता है)। नए एल्गोरिदम, जिन्हें एसिम्प्टोटिकली फास्ट या कभी-कभी सुपरफास्ट टोप्लिट्ज़ एल्गोरिदम कहा जाता है, हल कर सकते हैं Θ(n log^pn) विभिन्न पी के लिए (जैसे पी = 2, पी = 3 ). लेविंसन रिकर्सन कई कारणों से लोकप्रिय बना हुआ है; एक के लिए, तुलना में इसे समझना अपेक्षाकृत आसान है; दूसरे के लिए, यह छोटे n (आमतौर पर n <256) के लिए सुपरफास्ट एल्गोरिदम से तेज़ हो सकता है।

व्युत्पत्ति

पृष्ठभूमि

मैट्रिक्स समीकरण प्रपत्र का अनुसरण करते हैं

$\mathbf {M} \,{\vec {x}}={\vec {y}}.$

लेविंसन-डर्बिन एल्गोरिथ्म का उपयोग ऐसे किसी भी समीकरण के लिए किया जा सकता है, जब तक कि एम एक गैर-शून्य मुख्य विकर्ण के साथ एक ज्ञात टोप्लिट्ज़ मैट्रिक्स है। यहाँ ${\vec {y}}$ एक ज्ञात सदिश समष्टि है, और ${\vec {x}}$ संख्या x का एक अज्ञात सदिश है_i अभी तक निर्धारित नहीं किया गया है।

इस लेख के लिए, ê_i एक वेक्टर है जो इसके वें स्थान को छोड़कर पूरी तरह से शून्य से बना है, जिसका मान एक है। इसकी लंबाई आस-पास के संदर्भ से स्पष्ट रूप से निर्धारित होगी। शब्द N उपरोक्त मैट्रिक्स की चौड़ाई को संदर्भित करता है - 'M' एक N×N मैट्रिक्स है। अंत में, इस आलेख में, सुपरस्क्रिप्ट एक आगमनात्मक सूचकांक को संदर्भित करते हैं, जबकि सबस्क्रिप्ट सूचकांकों को दर्शाते हैं। उदाहरण के लिए (और परिभाषा), इस आलेख में, मैट्रिक्स 'टी'ⁿ एक n×n मैट्रिक्स है जो 'M' से ऊपरी बाएँ n×n ब्लॉक को कॉपी करता है - यानी, Tⁿ_ij = एम_ij.

टीⁿ भी एक Toeplitz मैट्रिक्स है, जिसका अर्थ है कि इसे इस प्रकार लिखा जा सकता है

$\mathbf {T} ^{n}={\begin{bmatrix}t_{0}&t_{-1}&t_{-2}&\dots &t_{-n+1}\\t_{1}&t_{0}&t_{-1}&\dots &t_{-n+2}\\t_{2}&t_{1}&t_{0}&\dots &t_{-n+3}\\\vdots &\vdots &\vdots &\ddots &\vdots \\t_{n-1}&t_{n-2}&t_{n-3}&\dots &t_{0}\end{bmatrix}}.$

परिचयात्मक चरण

एल्गोरिथम दो चरणों में आगे बढ़ता है। पहले चरण में, वैक्टर के दो सेट स्थापित किए जाते हैं, जिन्हें फॉरवर्ड और बैकवर्ड वेक्टर कहा जाता है। आगे वाले वैक्टर का उपयोग पिछड़े वैक्टर के सेट को प्राप्त करने में मदद के लिए किया जाता है; तो उन्हें तुरंत त्याग दिया जा सकता है। दूसरे चरण के लिए बैकवर्ड वेक्टर आवश्यक हैं, जहां उनका उपयोग वांछित समाधान बनाने के लिए किया जाता है।

लेविंसन-डर्बिन रिकर्सन एन को परिभाषित करता है^वेंआगे वेक्टर, निरूपित ${\vec {f}}^{n}$, लंबाई n के वेक्टर के रूप में जो संतुष्ट करता है:

$\mathbf {T} ^{n}{\vec {f}}^{n}={\hat {e}}_{1}.$

तब^वेंबैकवर्ड वेक्टर ${\vec {b}}^{n}$ समान रूप से परिभाषित किया गया है; यह लंबाई n का सदिश है जो संतुष्ट करता है:

$\mathbf {T} ^{n}{\vec {b}}^{n}={\hat {e}}_{n}.$

एक महत्वपूर्ण सरलीकरण तब हो सकता है जब एम एक सममित मैट्रिक्स है; तो दोनों वेक्टर बी से संबंधित हैंⁿ_i = एफⁿ_n+1−i-अर्थात्, वे एक-दूसरे की पंक्ति-उलट हैं। यह उस विशेष मामले में कुछ अतिरिक्त गणना बचा सकता है।

पिछड़े सदिश प्राप्त करना

भले ही मैट्रिक्स सममित न हो, फिर भी n^वें आगे और पीछे के वेक्टर को लंबाई n - 1 के वैक्टर से निम्नानुसार पाया जा सकता है। सबसे पहले, आगे के वेक्टर को प्राप्त करने के लिए शून्य के साथ बढ़ाया जा सकता है:

$\mathbf {T} ^{n}{\begin{bmatrix}{\vec {f}}^{n-1}\\0\\\end{bmatrix}}={\begin{bmatrix}\ &\ &\ &t_{-n+1}\\\ &\mathbf {T} ^{n-1}&\ &t_{-n+2}\\\ &\ &\ &\vdots \\t_{n-1}&t_{n-2}&\dots &t_{0}\\\end{bmatrix}}{\begin{bmatrix}\ \\{\vec {f}}^{n-1}\\\ \\0\\\ \\\end{bmatrix}}={\begin{bmatrix}1\\0\\\vdots \\0\\\varepsilon _{f}^{n}\end{bmatrix}}.$

टी से जाने मेंⁿ⁻¹' से 'Tⁿ, मैट्रिक्स में जोड़ा गया अतिरिक्त कॉलम समाधान को परेशान नहीं करता है जब शून्य का उपयोग फॉरवर्ड वेक्टर को बढ़ाने के लिए किया जाता है। हालाँकि, मैट्रिक्स में जोड़ी गई अतिरिक्त पंक्ति ने समाधान को बाधित कर दिया है; और इसने एक अवांछित त्रुटि शब्द ε बनाया हैf जो अंतिम स्थान पर होता है. उपरोक्त समीकरण इसका मान देता है:

$\varepsilon _{f}^{n}\ =\ \sum _{i=1}^{n-1}\ M_{ni}\ f_{i}^{n-1}\ =\ \sum _{i=1}^{n-1}\ t_{n-i}\ f_{i}^{n-1}.$

यह त्रुटि शीघ्र ही वापस आ जाएगी और नए फॉरवर्ड वेक्टर से समाप्त कर दी जाएगी; लेकिन सबसे पहले, बैकवर्ड वेक्टर को समान (यद्यपि उलटा) तरीके से बढ़ाया जाना चाहिए। बैकवर्ड वेक्टर के लिए,

$\mathbf {T} ^{n}{\begin{bmatrix}0\\{\vec {b}}^{n-1}\\\end{bmatrix}}={\begin{bmatrix}t_{0}&\dots &t_{-n+2}&t_{-n+1}\\\vdots &\ &\ &\ \\t_{n-2}&\ &\mathbf {T} ^{n-1}&\ \\t_{n-1}&\ &\ &\end{bmatrix}}{\begin{bmatrix}\ \\0\\\ \\{\vec {b}}^{n-1}\\\ \\\end{bmatrix}}={\begin{bmatrix}\varepsilon _{b}^{n}\\0\\\vdots \\0\\1\end{bmatrix}}.$

पहले की तरह, मैट्रिक्स में जोड़ा गया अतिरिक्त कॉलम इस नए बैकवर्ड वेक्टर को परेशान नहीं करता है; लेकिन अतिरिक्त पंक्ति करती है. यहां हमारे पास एक और अवांछित त्रुटि है ε_b मूल्य के साथ:

$\varepsilon _{b}^{n}\ =\ \sum _{i=2}^{n}\ M_{1i}\ b_{i-1}^{n-1}\ =\ \sum _{i=1}^{n-1}\ t_{-i}\ b_{i}^{n-1}.\$

इन दो त्रुटि शब्दों का उपयोग निम्नानुसार वर्णित उच्च-क्रम वाले आगे और पीछे के वैक्टर बनाने के लिए किया जा सकता है। आव्यूहों की रैखिकता का उपयोग करते हुए, निम्नलिखित पहचान सभी के लिए मान्य है $(\alpha ,\beta )$:

$\mathbf {T} \left(\alpha {\begin{bmatrix}{\vec {f}}\\\ \\0\\\end{bmatrix}}+\beta {\begin{bmatrix}0\\\ \\{\vec {b}}\end{bmatrix}}\right)=\alpha {\begin{bmatrix}1\\0\\\vdots \\0\\\varepsilon _{f}\\\end{bmatrix}}+\beta {\begin{bmatrix}\varepsilon _{b}\\0\\\vdots \\0\\1\end{bmatrix}}.$

यदि α और β को चुना जाता है ताकि दाहिनी ओर ê प्राप्त हो₁ या_n, तो कोष्ठक में मौजूद मात्रा n की परिभाषा को पूरा करेगी^वें क्रमशः आगे या पीछे वेक्टर। उन अल्फा और बीटा को चुनने पर, कोष्ठक में वेक्टर योग सरल होता है और वांछित परिणाम देता है।

इन गुणांकों को खोजने के लिए, $\alpha _{f}^{n}$, $\beta _{f}^{n}$ ऐसे हैं कि:

${\vec {f}}^{n}=\alpha _{f}^{n}{\begin{bmatrix}{\vec {f}}^{n-1}\\0\end{bmatrix}}+\beta _{f}^{n}{\begin{bmatrix}0\\{\vec {b}}^{n-1}\end{bmatrix}}$

और क्रमशः $\alpha _{b}^{n}$, $\beta _{b}^{n}$ ऐसे हैं कि:

${\vec {b}}^{n}=\alpha _{b}^{n}{\begin{bmatrix}{\vec {f}}^{n-1}\\0\end{bmatrix}}+\beta _{b}^{n}{\begin{bmatrix}0\\{\vec {b}}^{n-1}\end{bmatrix}}.$

पिछले दोनों समीकरणों को इससे गुणा करने पर ${\mathbf {T} }^{n}$ किसी को निम्नलिखित समीकरण मिलता है:

${\begin{bmatrix}1&\varepsilon _{b}^{n}\\0&0\\\vdots &\vdots \\0&0\\\varepsilon _{f}^{n}&1\end{bmatrix}}{\begin{bmatrix}\alpha _{f}^{n}&\alpha _{b}^{n}\\\beta _{f}^{n}&\beta _{b}^{n}\end{bmatrix}}={\begin{bmatrix}1&0\\0&0\\\vdots &\vdots \\0&0\\0&1\end{bmatrix}}.$

अब, ऊपर दिए गए दो वैक्टरों के बीच के सभी शून्यों को नजरअंदाज कर दिया गया है और ध्वस्त कर दिया गया है, केवल निम्नलिखित समीकरण बचा है:

${\begin{bmatrix}1&\varepsilon _{b}^{n}\\\varepsilon _{f}^{n}&1\end{bmatrix}}{\begin{bmatrix}\alpha _{f}^{n}&\alpha _{b}^{n}\\\beta _{f}^{n}&\beta _{b}^{n}\end{bmatrix}}={\begin{bmatrix}1&0\\0&1\end{bmatrix}}.$

इन्हें हल करने के साथ (क्रैमर 2×2 मैट्रिक्स व्युत्क्रम सूत्र का उपयोग करके), नए फॉरवर्ड और बैकवर्ड वेक्टर हैं:

${\vec {f}}^{n}={1 \over {1-\varepsilon _{b}^{n}\varepsilon _{f}^{n}}}{\begin{bmatrix}{\vec {f}}^{n-1}\\0\end{bmatrix}}-{\varepsilon _{f}^{n} \over {1-\varepsilon _{b}^{n}\varepsilon _{f}^{n}}}{\begin{bmatrix}0\\{\vec {b}}^{n-1}\end{bmatrix}}$

${\vec {b}}^{n}={1 \over {1-\varepsilon _{b}^{n}\varepsilon _{f}^{n}}}{\begin{bmatrix}0\\{\vec {b}}^{n-1}\end{bmatrix}}-{\varepsilon _{b}^{n} \over {1-\varepsilon _{b}^{n}\varepsilon _{f}^{n}}}{\begin{bmatrix}{\vec {f}}^{n-1}\\0\end{bmatrix}}.$

इन सदिश योगों को निष्पादित करने पर, n प्राप्त होता है^वें पिछले वाले से आगे और पीछे के वेक्टर। जो कुछ बचा है वह इन वैक्टरों में से पहले को ढूंढना है, और फिर कुछ त्वरित योग और गुणन से शेष को प्राप्त करना है। पहले आगे और पीछे वाले वेक्टर बस हैं:

${\vec {f}}^{1}={\vec {b}}^{1}=\left[{1 \over M_{11}}\right]=\left[{1 \over t_{0}}\right].$

पिछड़े वैक्टर का उपयोग करना

उपरोक्त चरण 'एम' के लिए एन बैकवर्ड वैक्टर देते हैं। वहां से, एक अधिक मनमाना समीकरण है:

${\vec {y}}=\mathbf {M} \ {\vec {x}}.$

समाधान उसी पुनरावर्ती तरीके से बनाया जा सकता है जैसे बैकवर्ड वैक्टर बनाए गए थे। इसलिए, ${\vec {x}}$ मध्यवर्ती के अनुक्रम में सामान्यीकृत किया जाना चाहिए ${\vec {x}}^{n}$, ऐसा है कि ${\vec {x}}^{N}={\vec {x}}$.

समाधान तब पुनरावर्ती रूप से यह ध्यान देकर बनाया जाता है कि यदि

$\mathbf {T} ^{n-1}{\begin{bmatrix}x_{1}^{n-1}\\x_{2}^{n-1}\\\vdots \\x_{n-1}^{n-1}\\\end{bmatrix}}={\begin{bmatrix}y_{1}\\y_{2}\\\vdots \\y_{n-1}\end{bmatrix}}.$

फिर, शून्य के साथ फिर से विस्तार करना, और जहां आवश्यक हो, एक त्रुटि स्थिरांक को परिभाषित करना:

$\mathbf {T} ^{n}{\begin{bmatrix}x_{1}^{n-1}\\x_{2}^{n-1}\\\vdots \\x_{n-1}^{n-1}\\0\end{bmatrix}}={\begin{bmatrix}y_{1}\\y_{2}\\\vdots \\y_{n-1}\\\varepsilon _{x}^{n-1}\end{bmatrix}}.$

फिर हम n का उपयोग कर सकते हैं^{त्रुटि शब्द को खत्म करने और इसे वांछित सूत्र के साथ बदलने के लिए बैकवर्ड वेक्टर निम्नानुसार है:}

$\mathbf {T} ^{n}\left({\begin{bmatrix}x_{1}^{n-1}\\x_{2}^{n-1}\\\vdots \\x_{n-1}^{n-1}\\0\\\end{bmatrix}}+(y_{n}-\varepsilon _{x}^{n-1})\ {\vec {b}}^{n}\right)={\begin{bmatrix}y_{1}\\y_{2}\\\vdots \\y_{n-1}\\y_{n}\end{bmatrix}}.$

इस विधि को n = N तक विस्तारित करने से समाधान प्राप्त होता है ${\vec {x}}$.

व्यवहार में, ये चरण अक्सर शेष प्रक्रिया के साथ-साथ किए जाते हैं, लेकिन वे एक सुसंगत इकाई बनाते हैं और उन्हें अपने स्वयं के चरण के रूप में माना जाना चाहिए।

ब्लॉक लेविंसन एल्गोरिथ्म

यदि एम सख्ती से टोएप्लिट्ज़ नहीं है, लेकिन ब्लॉक मैट्रिक्स टोएप्लिट्ज़ है, तो लेविंसन रिकर्सन को मैट्रिक्स तत्वों के साथ टोएप्लिट्ज़ मैट्रिक्स के रूप में ब्लॉक टोएप्लिट्ज़ मैट्रिक्स के संबंध में उसी तरह से प्राप्त किया जा सकता है (म्यूजिकस 1988)। ब्लॉक टॉप्लिट्ज़ मैट्रिसेस सिग्नल प्रोसेसिंग एल्गोरिदम में स्वाभाविक रूप से उत्पन्न होते हैं जब कई सिग्नल स्ट्रीम (उदाहरण के लिए, सिस्टम विश्लेषण # सिस्टम सिस्टम की विशेषता) या साइक्लो-स्टेशनरी सिग्नल से निपटते हैं।

यह भी देखें

• स्प्लिट लेविंसन रिकर्सन
• रैखिक भविष्यवाणी
• स्वप्रतिगामी मॉडल

संदर्भ

Defining sources

• Levinson, N. (1947). "The Wiener RMS error criterion in filter design and prediction." J. Math. Phys., v. 25, pp. 261–278.
• Durbin, J. (1960). "The fitting of time series models." Rev. Inst. Int. Stat., v. 28, pp. 233–243.
• Trench, W. F. (1964). "An algorithm for the inversion of finite Toeplitz matrices." J. Soc. Indust. Appl. Math., v. 12, pp. 515–522.
• Musicus, B. R. (1988). "Levinson and Fast Choleski Algorithms for Toeplitz and Almost Toeplitz Matrices." RLE TR No. 538, MIT. [1]
• Delsarte, P. and Genin, Y. V. (1986). "The split Levinson algorithm." IEEE Transactions on Acoustics, Speech, and Signal Processing, v. ASSP-34(3), pp. 470–478.

Further work

• Bojanczyk, A.W.; Brent, R.P.; De Hoog, F.R.; Sweet, D.R. (1995). "On the stability of the Bareiss and related Toeplitz factorization algorithms". SIAM Journal on Matrix Analysis and Applications. 16: 40–57. arXiv:1004.5510. doi:10.1137/S0895479891221563. S2CID 367586.
• Brent R.P. (1999), "Stability of fast algorithms for structured linear systems", Fast Reliable Algorithms for Matrices with Structure (editors—T. Kailath, A.H. Sayed), ch.4 (SIAM).
• Bunch, J. R. (1985). "Stability of methods for solving Toeplitz systems of equations." SIAM J. Sci. Stat. Comput., v. 6, pp. 349–364. [2]
• Krishna, H.; Wang, Y. (1993). "The Split Levinson Algorithm is weakly stable". SIAM Journal on Numerical Analysis. 30 (5): 1498–1508. doi:10.1137/0730078.

Summaries

• Bäckström, T. (2004). "2.2. Levinson–Durbin Recursion." Linear Predictive Modelling of Speech – Constraints and Line Spectrum Pair Decomposition. Doctoral thesis. Report no. 71 / Helsinki University of Technology, Laboratory of Acoustics and Audio Signal Processing. Espoo, Finland. [3]
• Claerbout, Jon F. (1976). "Chapter 7 – Waveform Applications of Least-Squares." Fundamentals of Geophysical Data Processing. Palo Alto: Blackwell Scientific Publications. [4]
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), "Section 2.8.2. Toeplitz Matrices", Numerical Recipes: The Art of Scientific Computing (3rd ed.), New York: Cambridge University Press, ISBN 978-0-521-88068-8
• Golub, G.H., and Loan, C.F. Van (1996). "Section 4.7 : Toeplitz and related Systems" Matrix Computations, Johns Hopkins University Press