कम से कम औसत वर्ग फ़िल्टर

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

समस्या निर्माण

विनीज़ फ़िल्टर से संबंध

सिग्नल प्रोसेसिंग डोमेन को छोड़कर, कारण वीनर फ़िल्टर की प्राप्ति कम से कम वर्गों के अनुमान के समाधान की तरह दिखती है। इनपुट मैट्रिक्स के लिए कम से कम वर्ग समाधान $\mathbf {X}$ और आउटपुट वेक्टर ${\boldsymbol {y}}$ है

${\boldsymbol {\hat {\beta }}}=(\mathbf {X} ^{\mathbf {T} }\mathbf {X} )^{-1}\mathbf {X} ^{\mathbf {T} }{\boldsymbol {y}}.$

एफआईआर कम से कम औसत वर्ग फ़िल्टर वीनर फ़िल्टर से संबंधित है, लेकिन पूर्व के त्रुटि मानदंड को कम करना क्रॉस-सहसंबंधों या ऑटो-सहसंबंधों पर निर्भर नहीं करता है। इसका विलयन वीनर फिल्टर विलयन में परिवर्तित हो जाता है। उपरोक्त ब्लॉक आरेख का उपयोग करके अधिकांश रैखिक अनुकूली फ़िल्टरिंग समस्याओं को तैयार किया जा सकता है। यानी एक अज्ञात प्रणाली $\mathbf {h} (n)$ पहचान की जानी है और अनुकूली फ़िल्टर फ़िल्टर को अनुकूलित करने का प्रयास करता है ${\hat {\mathbf {h} }}(n)$ जितना संभव हो उतना करीब बनाने के लिए $\mathbf {h} (n)$, केवल देखने योग्य संकेतों का उपयोग करते हुए $x(n)$, $d(n)$ और $e(n)$; लेकिन $y(n)$, $v(n)$ और $h(n)$ प्रत्यक्ष रूप से देखने योग्य नहीं हैं। इसका समाधान वीनर फ़िल्टर से निकटता से संबंधित है।

प्रतीकों की परिभाषा

$n$ वर्तमान इनपुट नमूने की संख्या है

$p$ फिल्टर नल की संख्या है

$\{\cdot \}^{H}$ (हर्मिटियन ट्रांसपोज़ या संयुग्मी स्थानान्तरण )

$\mathbf {x} (n)=\left[x(n),x(n-1),\dots ,x(n-p-1)\right]^{T}$ :$\mathbf {h} (n)=\left[h_{0}(n),h_{1}(n),\dots ,h_{p-1}(n)\right]^{T},\quad \mathbf {h} (n)\in \mathbb {C} ^{p}$

$y(n)=\mathbf {h} ^{H}(n)\cdot \mathbf {x} (n)$

$d(n)=y(n)+\nu (n)$ :${\hat {\mathbf {h} }}(n)$ अनुमानित फ़िल्टर; बाद में फ़िल्टर गुणांक के अनुमान के रूप में व्याख्या करें n नमूने

$e(n)=d(n)-{\hat {y}}(n)=d(n)-{\hat {\mathbf {h} }}^{H}(n)\cdot \mathbf {x} (n)$

विचार

एलएमएस फिल्टर के पीछे मूल विचार इष्टतम फिल्टर वजन तक पहुंचना है $(R^{-1}P)$, फ़िल्टर वज़न को इष्टतम फ़िल्टर वज़न में परिवर्तित करने के तरीके से अपडेट करके। यह ग्रेडिएंट डिसेंट एल्गोरिथम पर आधारित है। एल्गोरिथ्म छोटे वजन (ज्यादातर मामलों में शून्य) मानकर शुरू होता है और, प्रत्येक चरण में, औसत वर्ग त्रुटि के ग्रेडिएंट का पता लगाकर, वजन को अपडेट किया जाता है। अर्थात्, यदि MSE-ग्रेडिएंट धनात्मक है, तो इसका तात्पर्य है कि त्रुटि सकारात्मक रूप से बढ़ती रहेगी यदि वही वज़न आगे पुनरावृत्तियों के लिए उपयोग किया जाता है, जिसका अर्थ है कि हमें वज़न कम करने की आवश्यकता है। उसी तरह, अगर ग्रेडिएंट नेगेटिव है, तो हमें वेट बढ़ाने की जरूरत है। वजन अद्यतन समीकरण है

$W_{n+1}=W_{n}-\mu \nabla \varepsilon [n],$

कहाँ $\varepsilon$ माध्य-वर्ग त्रुटि का प्रतिनिधित्व करता है और $\mu$ अभिसरण गुणांक है।

ऋणात्मक चिह्न दर्शाता है कि हम त्रुटि की ढलान पर नीचे जा रहे हैं, $\varepsilon$ फिल्टर वजन खोजने के लिए, $W_{i}$, जो त्रुटि को कम करता है।

फिल्टर भार के एक समारोह के रूप में माध्य-स्क्वायर त्रुटि एक द्विघात समारोह है जिसका अर्थ है कि इसका केवल एक चरम है, जो औसत-वर्ग त्रुटि को कम करता है, जो कि इष्टतम वजन है। LMS इस प्रकार, माध्य-स्क्वायर-त्रुटि बनाम फ़िल्टर भार वक्र के आरोही/अवरोही द्वारा इस इष्टतम भार की ओर पहुंचता है।

व्युत्पत्ति

एलएमएस फिल्टर के पीछे का विचार फ़िल्टर वजन खोजने के लिए सबसे तेज गिरावट का उपयोग करना है ${\hat {\mathbf {h} }}(n)$ जो हानि समारोह को कम करता है। हम लागत फलन को इस रूप में परिभाषित करते हुए प्रारंभ करते हैं

$C(n)=E\left\{|e(n)|^{2}\right\}$

कहाँ $e(n)$ वर्तमान नमूना n और में त्रुटि है $E\{\cdot \}$ अपेक्षित मूल्य दर्शाता है।

यह लागत फलन ($C(n)$) माध्य वर्ग त्रुटि है, और इसे LMS द्वारा न्यूनतम किया जाता है। यहीं पर LMS को इसका नाम मिला। स्टीपेस्ट डिसेंट को लागू करने का मतलब फ़िल्टर गुणांक (वजन) वेक्टर की व्यक्तिगत प्रविष्टियों के संबंध में आंशिक डेरिवेटिव लेना है

$\nabla _{{\hat {\mathbf {h} }}^{H}}C(n)=\nabla _{{\hat {\mathbf {h} }}^{H}}E\left\{e(n)\,e^{*}(n)\right\}=2E\left\{\nabla _{{\hat {\mathbf {h} }}^{H}}(e(n))\,e^{*}(n)\right\}$

कहाँ $\nabla$ ग्रेडियेंट ऑपरेटर है

$\nabla _{{\hat {\mathbf {h} }}^{H}}(e(n))=\nabla _{{\hat {\mathbf {h} }}^{H}}\left(d(n)-{\hat {\mathbf {h} }}^{H}\cdot \mathbf {x} (n)\right)=-\mathbf {x} (n)$

$\nabla C(n)=-2E\left\{\mathbf {x} (n)\,e^{*}(n)\right\}$

अब, $\nabla C(n)$ एक सदिश राशि है जो लागत फलन के सबसे तीव्र आरोहण की ओर इशारा करती है। न्यूनतम लागत फ़ंक्शन खोजने के लिए हमें विपरीत दिशा में एक कदम उठाने की आवश्यकता है $\nabla C(n)$. गणितीय शब्दों में व्यक्त करने के लिए

${\hat {\mathbf {h} }}(n+1)={\hat {\mathbf {h} }}(n)-{\frac {\mu }{2}}\nabla C(n)={\hat {\mathbf {h} }}(n)+\mu \,E\left\{\mathbf {x} (n)\,e^{*}(n)\right\}$

कहाँ ${\frac {\mu }{2}}$ चरण आकार (अनुकूलन स्थिर) है। इसका मतलब है कि हमें एक अनुक्रमिक अद्यतन एल्गोरिदम मिला है जो लागत समारोह को कम करता है। दुर्भाग्य से, यह एल्गोरिथम तब तक साकार नहीं होता है जब तक हम नहीं जानते $E\left\{\mathbf {x} (n)\,e^{*}(n)\right\}$.

आम तौर पर, ऊपर की अपेक्षा की गणना नहीं की जाती है। इसके बजाय, एलएमएस को ऑनलाइन (प्रत्येक नए नमूने के प्राप्त होने के बाद अद्यतन करना) वातावरण में चलाने के लिए, हम उस अपेक्षा के तात्कालिक अनुमान का उपयोग करते हैं। नीचे देखें।

सरलीकरण

अधिकांश प्रणालियों के लिए अपेक्षा कार्य ${E}\left\{\mathbf {x} (n)\,e^{*}(n)\right\}$ अनुमानित होना चाहिए। यह निम्नलिखित निष्पक्ष अनुमानक के साथ किया जा सकता है

${\hat {E}}\left\{\mathbf {x} (n)\,e^{*}(n)\right\}={\frac {1}{N}}\sum _{i=0}^{N-1}\mathbf {x} (n-i)\,e^{*}(n-i)$ कहाँ $N$ उस अनुमान के लिए हमारे द्वारा उपयोग किए जाने वाले नमूनों की संख्या को इंगित करता है। सबसे सरल मामला है $N=1$

${\hat {E}}\left\{\mathbf {x} (n)\,e^{*}(n)\right\}=\mathbf {x} (n)\,e^{*}(n)$ उस साधारण मामले के लिए अद्यतन एल्गोरिथ्म इस प्रकार है

${\hat {\mathbf {h} }}(n+1)={\hat {\mathbf {h} }}(n)+\mu \mathbf {x} (n)\,e^{*}(n)$

दरअसल, यह एलएमएस फिल्टर के लिए अद्यतन एल्गोरिथ्म का गठन करता है।

एलएमएस एल्गोरिथम सारांश

के लिए एलएमएस एल्गोरिथम $p$वें आदेश फ़िल्टर को संक्षेप में प्रस्तुत किया जा सकता है

Parameters:	$p=$ filter order
	$\mu =$ step size
Initialisation:	${\hat {\mathbf {h} }}(0)=\operatorname {zeros} (p)$
Computation:	For $n=0,1,2,...$
	$\mathbf {x} (n)=\left[x(n),x(n-1),\dots ,x(n-p+1)\right]^{T}$
	$e(n)=d(n)-{\hat {\mathbf {h} }}^{H}(n)\mathbf {x} (n)$
	${\hat {\mathbf {h} }}(n+1)={\hat {\mathbf {h} }}(n)+\mu \,e^{*}(n)\mathbf {x} (n)$

माध्य में अभिसरण और स्थिरता

जैसा कि एलएमएस एल्गोरिथ्म अपेक्षाओं के सटीक मूल्यों का उपयोग नहीं करता है, वजन कभी भी पूर्ण अर्थों में इष्टतम वजन तक नहीं पहुंचेगा, लेकिन माध्य में एक अभिसरण संभव है। यही है, भले ही वज़न कम मात्रा में बदल सकता है, यह इष्टतम वज़न के बारे में बदलता है। हालाँकि, यदि वेरियंस जिसके साथ वज़न बदलता है, बड़ा है, माध्य में अभिसरण भ्रामक होगा। यह समस्या हो सकती है, यदि चरण-आकार का मान $\mu$ ठीक से नहीं चुना गया है।

अगर $\mu$ बड़े होने के लिए चुना जाता है, जिस मात्रा के साथ वजन परिवर्तन ढाल अनुमान पर निर्भर करता है, और इसलिए वजन एक बड़े मूल्य से बदल सकता है ताकि पहले पल में नकारात्मक ढाल अब सकारात्मक हो सके। और दूसरे पल में, वजन नकारात्मक ढाल के कारण बड़ी मात्रा में विपरीत दिशा में बदल सकता है और इस प्रकार इष्टतम वजन के बारे में एक बड़े विचरण के साथ दोलन करता रहेगा। वहीं दूसरी ओर अगर $\mu$ बहुत छोटा होने के लिए चुना गया है, इष्टतम भारों में अभिसरण करने का समय बहुत बड़ा होगा।

इस प्रकार, एक ऊपरी सीमा पर $\mu$ की आवश्यकता होती है जो दिया जाता है

$0<\mu <{\frac {2}{\lambda _{\mathrm {max} }}}$

कहाँ $\lambda _{\max }$ स्वतःसंबंध मैट्रिक्स का सबसे बड़ा eigenvalue है ${\mathbf {R} }=E\{{\mathbf {x} }(n){\mathbf {x} ^{H}}(n)\}$. यदि यह स्थिति पूरी नहीं होती है, तो एल्गोरिथम अस्थिर हो जाता है और ${\hat {h}}(n)$ विचलन।

अधिकतम अभिसरण गति तब प्राप्त होती है जब

$\mu ={\frac {2}{\lambda _{\mathrm {max} }+\lambda _{\mathrm {min} }}},$

कहाँ $\lambda _{\min }$ का सबसे छोटा आइगेनवैल्यू है ${\mathbf {R} }$. मान लें कि $\mu$ इस इष्टतम से कम या उसके बराबर है, अभिसरण गति द्वारा निर्धारित किया जाता है $\lambda _{\min }$, तेजी से अभिसरण देने वाले बड़े मूल्य के साथ। इसका मतलब है कि तेजी से अभिसरण कब प्राप्त किया जा सकता है $\lambda _{\max }$ इसके करीब है $\lambda _{\min }$, अर्थात्, अधिकतम प्राप्त करने योग्य अभिसरण गति के eigenvalue प्रसार पर निर्भर करता है ${\mathbf {R} }$.

एक सफेद शोर संकेत में स्वतः सहसंबंध मैट्रिक्स होता है ${\mathbf {R} }=\sigma ^{2}{\mathbf {I} }$ कहाँ $\sigma ^{2}$ संकेत का विचरण है। इस मामले में सभी eigenvalues ​​​​बराबर हैं, और eigenvalue प्रसार सभी संभव आव्यूहों पर न्यूनतम है। इसलिए इस परिणाम की सामान्य व्याख्या यह है कि एलएमएस सफेद इनपुट संकेतों के लिए तेजी से और रंगीन इनपुट संकेतों के लिए धीरे-धीरे अभिसरित होता है, जैसे कम-पास या उच्च-पास विशेषताओं वाली प्रक्रियाएं।

यह ध्यान रखना महत्वपूर्ण है कि उपरोक्त ऊपरी सीमा पर $\mu$ केवल माध्य में स्थिरता को लागू करता है, लेकिन के गुणांक ${\hat {h}}(n)$ अभी भी असीम रूप से बड़ा हो सकता है, यानी गुणांकों का विचलन अभी भी संभव है। एक अधिक व्यावहारिक सीमा है

$0<\mu <{\frac {2}{\mathrm {tr} \left[{\mathbf {R} }\right]}},$

कहाँ $\mathrm {tr} [{\mathbf {R} }]$ के ट्रेस (रैखिक बीजगणित) को दर्शाता है ${\mathbf {R} }$. यह बाध्य गारंटी देता है कि के गुणांक ${\hat {h}}(n)$ विचलन न करें (व्यवहार में, का मूल्य $\mu$ इस ऊपरी बाउंड के करीब नहीं चुना जाना चाहिए, क्योंकि यह बाउंड की व्युत्पत्ति में किए गए अनुमानों और धारणाओं के कारण कुछ हद तक आशावादी है)।

सामान्यीकृत कम से कम वर्ग फ़िल्टर (एनएलएमएस)

शुद्ध एलएमएस एल्गोरिथ्म का मुख्य दोष यह है कि यह अपने इनपुट के स्केलिंग के प्रति संवेदनशील है $x(n)$. इससे सीखने की दर का चयन करना बहुत कठिन (यदि असंभव नहीं है) हो जाता है $\mu$ जो एल्गोरिथ्म की स्थिरता की गारंटी देता है (हायकिन 2002)। सामान्यीकृत कम से कम औसत वर्ग फ़िल्टर (एनएलएमएस) एलएमएस एल्गोरिदम का एक प्रकार है जो इनपुट की शक्ति के साथ सामान्यीकरण करके इस समस्या को हल करता है। एनएलएमएस एल्गोरिदम को संक्षेप में प्रस्तुत किया जा सकता है:

Parameters:	$p=$ filter order
	$\mu =$ step size
Initialization:	${\hat {\mathbf {h} }}(0)=\operatorname {zeros} (p)$
Computation:	For $n=0,1,2,...$
	$\mathbf {x} (n)=\left[x(n),x(n-1),\dots ,x(n-p+1)\right]^{T}$
	$e(n)=d(n)-{\hat {\mathbf {h} }}^{H}(n)\mathbf {x} (n)$
	${\hat {\mathbf {h} }}(n+1)={\hat {\mathbf {h} }}(n)+{\frac {\mu \,e^{*}(n)\mathbf {x} (n)}{\mathbf {x} ^{H}(n)\mathbf {x} (n)}}$

इष्टतम सीखने की दर

यह दिखाया जा सकता है कि अगर कोई हस्तक्षेप नहीं है ($v(n)=0$), तो एनएलएमएस एल्गोरिथम के लिए इष्टतम सीखने की दर है

$\mu _{opt}=1$ और इनपुट से स्वतंत्र है $x(n)$ और वास्तविक (अज्ञात) आवेग प्रतिक्रिया $\mathbf {h} (n)$. सामान्य मामले में हस्तक्षेप के साथ ($v(n)\neq 0$), इष्टतम सीखने की दर है

$\mu _{opt}={\frac {E\left[\left|y(n)-{\hat {y}}(n)\right|^{2}\right]}{E\left[|e(n)|^{2}\right]}}$

ऊपर दिए गए परिणाम मानते हैं कि सिग्नल $v(n)$ और $x(n)$ एक दूसरे से असंबद्ध हैं, जो आमतौर पर व्यवहार में होता है।

प्रमाण

बता दें कि फिल्टर मिसलिग्न्मेंट को इस रूप में परिभाषित किया गया है $\Lambda (n)=\left|\mathbf {h} (n)-{\hat {\mathbf {h} }}(n)\right|^{2}$, हम अगले नमूने के लिए अपेक्षित मिसलिग्न्मेंट प्राप्त कर सकते हैं:

$E\left[\Lambda (n+1)\right]=E\left[\left|{\hat {\mathbf {h} }}(n)+{\frac {\mu \,e^{*}(n)\mathbf {x} (n)}{\mathbf {x} ^{H}(n)\mathbf {x} (n)}}-\mathbf {h} (n)\right|^{2}\right]$

$E\left[\Lambda (n+1)\right]=E\left[\left|{\hat {\mathbf {h} }}(n)+{\frac {\mu \,\left(v^{*}(n)+y^{*}(n)-{\hat {y}}^{*}(n)\right)\mathbf {x} (n)}{\mathbf {x} ^{H}(n)\mathbf {x} (n)}}-\mathbf {h} (n)\right|^{2}\right]$

होने देना $\mathbf {\delta } ={\hat {\mathbf {h} }}(n)-\mathbf {h} (n)$ और $r(n)={\hat {y}}(n)-y(n)$

$E\left[\Lambda (n+1)\right]=E\left[\left|\mathbf {\delta } (n)-{\frac {\mu \,\left(v(n)+r(n)\right)\mathbf {x} (n)}{\mathbf {x} ^{H}(n)\mathbf {x} (n)}}\right|^{2}\right]$

$E\left[\Lambda (n+1)\right]=E\left[\left(\mathbf {\delta } (n)-{\frac {\mu \,\left(v(n)+r(n)\right)\mathbf {x} (n)}{\mathbf {x} ^{H}(n)\mathbf {x} (n)}}\right)^{H}\left(\mathbf {\delta } (n)-{\frac {\mu \,\left(v(n)+r(n)\right)\mathbf {x} (n)}{\mathbf {x} ^{H}(n)\mathbf {x} (n)}}\right)\right]$

स्वतंत्रता मानकर, हमारे पास:

$E\left[\Lambda (n+1)\right]=\Lambda (n)+E\left[\left({\frac {\mu \,\left(v(n)+r(n)\right)\mathbf {x} (n)}{\mathbf {x} ^{H}(n)\mathbf {x} (n)}}\right)^{H}\left({\frac {\mu \,\left(v(n)+r(n)\right)\mathbf {x} (n)}{\mathbf {x} ^{H}(n)\mathbf {x} (n)}}\right)\right]-2E\left[{\frac {\mu |r(n)|^{2}}{\mathbf {x} ^{H}(n)\mathbf {x} (n)}}\right]$

$E\left[\Lambda (n+1)\right]=\Lambda (n)+{\frac {\mu ^{2}E\left[|e(n)|^{2}\right]}{\mathbf {x} ^{H}(n)\mathbf {x} (n)}}-{\frac {2\mu E\left[|r(n)|^{2}\right]}{\mathbf {x} ^{H}(n)\mathbf {x} (n)}}$

इष्टतम सीखने की दर पाई जाती है ${\frac {dE\left[\Lambda (n+1)\right]}{d\mu }}=0$, जिससे होता है:

$2\mu E\left[|e(n)|^{2}\right]-2E\left[|r(n)|^{2}\right]=0$

$\mu ={\frac {E\left[|r(n)|^{2}\right]}{E\left[|e(n)|^{2}\right]}}$

यह भी देखें

• रिकर्सिव कम से कम वर्ग
• LMS फ़िल्टर से संबंधित सांख्यिकीय तकनीकों के लिए कम से कम वर्ग देखें।
• वीनर और एलएमएस के बीच समानताएं
• बहुविलंब ब्लॉक आवृत्ति डोमेन अनुकूली फ़िल्टर
• शून्य-बल तुल्यकारक
• कर्नेल अनुकूली फ़िल्टर
• मिलान फ़िल्टर
• वीनर फिल्टर

संदर्भ

• Monson H. Hayes: Statistical Digital Signal Processing and Modeling, Wiley, 1996, ISBN 0-471-59431-8
• Simon Haykin: Adaptive Filter Theory, Prentice Hall, 2002, ISBN 0-13-048434-2
• Simon S. Haykin, Bernard Widrow (Editor): Least-Mean-Square Adaptive Filters, Wiley, 2003, ISBN 0-471-21570-8
• Bernard Widrow, Samuel D. Stearns: Adaptive Signal Processing, Prentice Hall, 1985, ISBN 0-13-004029-0
• Weifeng Liu, Jose Principe and Simon Haykin: Kernel Adaptive Filtering: A Comprehensive Introduction, John Wiley, 2010, ISBN 0-470-44753-2
• Paulo S.R. Diniz: Adaptive Filtering: Algorithms and Practical Implementation, Kluwer Academic Publishers, 1997, ISBN 0-7923-9912-9

बाहरी संबंध

• LMS Algorithm in Adaptive Antenna Arrays www.antenna-theory.com
• LMS Noise cancellation demo www.advsolned.com