حداقل مربعات خطی
تحلیل جبری مسئله

اگر فرض کنیم متغیر ما  m بُعد دارد، یعنی  {\vec {x}}=[x_{1},x_{2},\dots ,x_{m}]، مسئله رگرسیون به یک مسئله بهینه‌سازی برای پیدا کردن  m+1 پارامتر تبدیل می‌شود. به این معنی که ما یک پارامتر چند متغیره به اسم  {\vec {\beta }}=[\beta _{0},\beta _{1},\cdots ,\beta _{m}] داریم و سعی می‌کنیم که متغیر وابسته که همان  y است را با ترکیبی خطی از بردارد ورودیِ  {\vec {x}}، تخمین بزنیم یعنی  y\approx \beta _{0}+\sum _{i=1}^{m}\beta _{i}\times x_{i}. حال اگر یک بعد دیگر به متغیر  {\vec {x}} اضافه کنیم و مقدارش را همیشه عدد ثابت  1 در نظر بگیریم ( x_{0}=1) و  {\vec {x}} را به صورتِ  {\vec {x}}=[1,x_{1},x_{2},\dots ,x_{m}] تغییر دهیم، تخمینی که از  y داریم در واقع ضرب نقطه ای بردار ورودی و بردار پارامترهای ماست یعنی  y\approx \sum _{i=0}^{m}\beta _{i}\times x_{i}={\vec {\beta }}\,\,.\,{\vec {x}}. حال فرض کنیم که تعداد مثالهایی که قرار است برای تخمین پارامترها استفاده کنیم  n است و این مثالها را به این شکل نمایش دهیم  D=({\vec {x_{1}}},y_{1}),\cdots ({\vec {x_{n}}},y_{n}). پارامتر بهینه پارامتری است که یک تابع هزینه را به حداقل برساند و تخمینهایی ما را به متغیر وابسته بسیار نزدیک کند. تابع هزینه را با جمع مربع تفاضل تخمینها با متغیر وابسته تعریف می‌کنیم، به این شکل که  L(D,{\vec {\beta }})=\sum _{i=1}^{n}({\vec {\beta }}\,.\,{\vec {x_{i}}}-y_{i})^{2}، با این حساب پارامتر بهینه می‌شود:
{\vec {\hat {\beta }}}=argmin_{\vec {\beta }}L(D,{\vec {\beta }})=argmin_{\vec {\beta }}\sum _{i=1}^{n}({\vec {\beta }}\,.\,{\vec {x_{i}}}-y_{i})^{2}
برای بدست آوردن  {\vec {\hat {\beta }}} یا همان پارامتر بهینه، از تابع هزینه که هم  L(D,{\vec {\beta }})نسبت به  {\vec {\beta }} گرادیان می‌گیریم و گرادیان را برابر صفر قرار می‌دهیم و پارامتر بهینه را بدست می‌آوریم. از آنجا که تابع  L(D,{\vec {\beta }}) نسبت به  {\vec {\beta }} تابعی کاملاً محدب است، در نقطه مینیمم گرادیان ما صفر خواهد بود و این روش پارامتر بهینه را بدست می‌دهد. برای تسهیل کار شکل تابع را با بکارگیری چند ماتریس ساده می‌کنیم. دو ماتریس برای این کار نیاز داردیم ماتریس  X و ماتریس  Y. ماتریس  X ماتریس ورودهای چندمتغیره ماست. هر سطر معادل یک نمونه از داده ماست، سطر  iام برابر است با  iامین نمونه ورودی ما یعنی بردار  {\vec {x_{i}}}، از اینرو  X یک ماتریس  n\times (m+1) خواهد بود. ماتریس  Y از طرف دیگر برابر است با مجموعه متغیرهای وابسته داده ما. سطر  iام این ماتریس برابر است با متغیر وابسته برای  iامین نمونه داده ما یا همان  y_{i}. ماتریس  Y یک ماتریس  n\times 1 است. با کمک این دو ماتریس می‌توان تابع هزینه را به شکل ذیل تعریف کرد:
L(D,{\vec {\beta }})=||X{\vec {\beta }}-Y||^{2}=(X{\vec {\beta }}-Y)^{T}(X{\vec {\beta }}-Y)=Y^{T}Y-Y^{T}X{\vec {\beta }}-{\vec {\beta }}^{T}X^{T}Y+{\vec {\beta }}^{T}X^{T}X{\vec {\beta }}
حال گرادیان این تابع را نسبت به  {\vec {\beta }} پیدا می‌کنیم که می‌شود:
{\frac {\partial L(D,{\vec {\beta }})}{\partial {\vec {\beta }}}}={\frac {\partial \left(Y^{T}Y-Y^{T}X{\vec {\beta }}-{\vec {\beta }}^{T}X^{T}Y+{\vec {\beta }}^{T}X^{T}X{\vec {\beta }}\right)}{\partial {\vec {\beta }}}}=-2X^{T}Y+2X^{T}X{\vec {\beta }}
با برابر قرار دادن گرادیان با صفر پارامتر بهینه بدست می‌آید:
-2X^{T}Y+2X^{T}X{\vec {\beta }}=0\Rightarrow X^{T}Y=X^{T}X{\vec {\beta }}\Rightarrow {\vec {\hat {\beta }}}=(X^{T}X)^{-1}X^{T}Y
پس پارامتر بهینه ما برابر است با:
{\bf {{\vec {\hat {\beta }}}=(X^{T}X)^{-1}X^{T}Y}}