لکیری اقل مربعات

سانچہ:اصطلاح برابر تجربات سے اکثر ایسا ڈیٹا اکٹھا ہوتا ہے جسے کسی کثیر رقمی سے تقرب کرنا مفید رہتا ہے۔ فرض کرو کہ کسی تجربے کے نتیجے میں ہمیں n پیمائش جوڑے ملتی ہیں:

$(x_1,y_1),(x_2,y_2),\cdots ,(x_n,y_n)$

ان کے گراف کو دیکھتے ہوئے ہم یہ فیصلہ کرتے ہیں کہ یہ دالہ $y=f(x)$، ذیل میں سے کسی کثیر رقمی

1. $y=ax+b$     (گراف لکیری خط)
2. $y=a{x}^2+bx+c$     (درجہ دوم کثیر رقمی)
3. $y=a{x}^3+b{x}^2+cx+d$     (سہ کثیر رقمی)
4. $\cdots \cdots \cdots \cdots \cdots$
5. $y=c_m{x}^m+c_{m-1}{x}^{m-1}+c_{1}x+c_0$     (m کثیر رقمی)

سے تقرب کی جا سکتی ہے۔

فائل:Ls poly 2 fit.png

تصویر میں گیارہ نکتوں (x,y) کا درجہ دوم کثیر رقمی سے تقرب کیا گیا ہے۔

تجربہ سے حاصل ہونے والے n جوڑے اگر درجہ m کے کثیر رقمی میں ایک ایک کر کے ڈالے جائیں تو ہمارے پاس n مساوات حاصل ہوں گی، جنہیں درج ذیل میٹرکس مساوات کی صورت لکھا جا سکتا ہے (عام طور پر $n>m$ ):

$Y\approx MC$

$Y=\left[\begin{array}{c}{y}_1\\ y2\\ ⋮\\ y_n\end{array}\right],M=\left[\begin{array}{ccccc}1& x_1& x_1^2& \cdots & x_1^m\\ 1& x_2& x_2^2& \cdots & x_2^m\\ ⋮& ⋮& & ⋮\\ 1& x_n& x_n^2& \cdots & x_n^m\end{array}\right],C=\left[\begin{array}{c}{c}_0\\ c_1\\ ⋮\\ c_m\end{array}\right]$

عام طور پر یکلخت لکیری مساوات کا نظام

$MC=Y$

ناموافق ہو گا، اس لیے اس کا کوئی حل نہیں ہو گا، یعنی ایسا کوئی C نہیں جو ان مساوات کی تسکین کرے۔ اس لیے کوشش یہ ہو گی کہ ایسا $C^{*}$ نکلا جائے جس کا غلطی سمتیہ $e=Y-M{C}^{*}$ کم سے کم ہو۔ یعنی غلطی سمتیہ کا امثولہ $\Vert e\Vert$ کم سے کم ہو۔

چونکہ سمتیہ Y فضا ${ℝ}^n$ میں ہے، اس لیے ہمیں اقلیدسی فضا میں امثولہ کی عام تعریف استعمال کرتے ہوئے

$\Vert e{\Vert }^2=e_1^2+e_2^2+\cdots +e_n^2$

کی تصغیر کرنا ہے۔

اب لکیری فضا ${ℝ}^{m+1}$ کے کسی سمتیہ C کے لیے، سمتیہ $MC$، میٹرکس M کی ستون فضا میں ہے، جو ${ℝ}^n$ کی لکیری ذیلی فضا ہے۔ اب مسقط کی تعریف سے ہم جانتے ہیں کہ سمتیہ Y کا میٹرکس M کی ستون فضا میں مسقط، غلطی امثولہ $\Vert e\Vert$ کی تصغیر کرتا ہے۔ ذیلی فضا $MC$ میں سمتیہ Y کے مسقط کو ہم $M{C}^{*}$ لکھتے ہیں۔ بہترین تقرب مسلئہ اثباتی کی رو سے غلطی سمتیہ قائم الزاویہ ہو گا ذیلی فضا کے۔ دوسرے لفظوں میں غلطی سمتیہ اور میٹرکس M کی ستون فضا کے کسی بھی سمتیہ MC کا اندرونی حاصل ضرب صفر ہو گا:

$(MC{)}^t(Y-M{C}^{*})=0$

(اقلیدسی فضا میں اندرونی حاصل ضرب کی عام تعریف استعمال کرتے ہوئے)،
یا

$C^t{M}^t(Y-M{C}^{*})=0$

$C^t(M^{t}Y-M^{t}M{C}^{*})=0$

$⟨M^{t}Y-M^{t}M{C}^{*},C⟩=0$

جس سے یہ نتیجہ اخذ کیا جا سکتا ہے کہ

$M^{t}Y-M^{t}M{C}^{*}=0$

یا

$M^{t}M{C}^{*}=M^{t}Y$

اگر میٹرکس $M^{t}M$ مقلوب ہو تو حل یہ ہو گا

$C^{*}=(M^{t}M{)}^{-1}{M}^{t}Y$

مصفاہ صورت

رقمی عملیت اشارہ میں اقل مربعات تخمینہ کو مصفاہ صورت میں پیش کیا جاتا ہے۔

فائل:Linear wiener filter setup.png

تصویر 1۔ مصفاہ $H(z)=\sum _{k=0}^K{h}_k{z}^{-k}$

تصویر 1 میں اشارہ متوالیہ $x_n$ کسی صورت میں اشارہ متوالیہ $d_n$ سے متعلق ہے۔ ہم اشارہ متوالیہ $x_n$ کو مصفاہ H سے گزار کر اشارہ $y_n$ حاصل کرتے ہیں۔ ہمار مقصد یہ ہے کہ متوالیہ $y_n$ تخمینہ ہو متوالیہ $d_n$ کا۔ یعنی مصفاہ H اس طرح چنا جائے کہ متوالیہ $d_n$ اور متوالیہ $y_n$ کے درمیان غلطی متوالیہ $e_n=d_n-y_n$ کا اقل مربع کم سے کم ہو:

$\underset{H}{\min }\sum _n{e}_n^2$

اگر متوالیہ تصادفی بھی ہوں تو پھر بھی ہم صرف مشاہداتی متوالیہ استعمال کر کے حل نکالنا چاہتے ہی (اور متوالیہ کی احصائی نوعیت سے مستفید نہیں ہونا چاہتے)۔ مصفاہ H ایک متناہی متوالیہ $h_0,h_1,\cdots ,h_{K-1}$ سے بنا ہے۔ مصفاہ کے اخراج $y_n$ اور ادخال $x_n$ کے درمیان تلفیف کا رشتہ ہے۔ اس مسئلہ میں اس رشتہ کو مصفوفہ ضرب کے ذریعہ لکھنا مفید ہے۔ اخراج $y_n$کے ایک لمبائی N کے ٹکرے کو $N\times 1$ سمتیہ ${\underset{\_}{y}}_n$ کے طور پر لکھتے ہوئے، ملفیف کو بطور قالب ضرب یوں لکھا جا سکتا ہے:

$\left[\begin{array}{c}{y}_n\\ y_{n-1}\\ ⋮\\ y_{n-(N-1)}\end{array}\right]=\left[\begin{array}{cccc}{x}_n& x_{n-1}& \cdots & x_{n-(K-1)}\\ x_{n-1}& x_{n-2}& \cdots & x_{n-1-(K-1)}\\ ⋮\\ x_{n-(N-1)}& x_{n-(N-1)-1}& \cdots & x_{n-(N-1)-(K-1)}\end{array}\right]\left[\begin{array}{c}{h}_0\\ h_1\\ ⋮\\ h_{(K-1)}\end{array}\right]$

یا

${\underset{\_}{y}}_n=X\underset{\_}{h}$

جہاں میٹرکس X کی جسامت $N\times K$ ہے۔ یہ ایک معلوم بات ہے کہ اقل مربع غلطی $\sum _{i=n-(N-1)}^n{e}_i^2$ کی تصغیر اسی وقت ہوتی ہے جب غلطی $e_n$ ڈیٹا $x_n$ کے قائم الزاویہ ہو، یعنی

$X^t{\underset{\_}{e}}_n=0$

اس معلومہ کو استعمال کرتے ہوئے

$X^t{\underset{\_}{e}}_n=X^t({\underset{\_}{d}}_n-{\underset{\_}{y}}_n)=X^t({\underset{\_}{d}}_n-X\underset{\_}{h})=X^t{\underset{\_}{d}}_n-X^{t}X\underset{\_}{h}=0$

اگر میٹرکس $X^{t}X$ جس کی جسامت $K\times K$ ہے، مقلوب ہو، تو اس سے ہمیں مصفاہ حاصل ہوتا ہے

$\underset{\_}{h}=(X^{t}X{)}^{-1}{X}^t{\underset{\_}{d}}_n$

مزید دیکھیے

• لکیری وینر مصفاہ