Linear regression via least squares
Linear regression is based on the idea of fitting a linear function through data points.
In its basic form, the problem is as follows. We are given data 
where 
is the ‘‘input’’ and 
is the ‘‘output’’ for the 
-th measurement. We seek to find a linear function 
such that 
are collectively close to the corresponding values 
.
In least-squares regression, the way we evaluate how well a candidate function 
fits the data is via the (squared) Euclidean norm:
![\[\sum_{i=1}^m\left(y_i-f\left(x_i\right)\right)^2 .\]](https://pressbooks.pub/app/uploads/quicklatex/quicklatex.com-1ef1878d0bcb676ab5bcbca5d9047a40_l3.png "Rendered by QuickLaTeX.com")
Since a linear function has the form 
for some 
, the problem of minimizing the above criterion takes the form
![\[\min _\theta \sum_{i=1}^m\left(y_i-x_i^T \theta\right)^2 .\]](https://pressbooks.pub/app/uploads/quicklatex/quicklatex.com-45492c9fd8813f91c47fffd6bc5621da_l3.png "Rendered by QuickLaTeX.com")
We can formulate this as a least-squares problem:
![\[\min _\theta\|A \theta-y\|_2,\]](https://pressbooks.pub/app/uploads/quicklatex/quicklatex.com-c52c45724a2e23c72f335afd4bb7a8c0_l3.png "Rendered by QuickLaTeX.com")
where
![\[A=\left(\begin{array}{c} x_1^T \\ \vdots \\ x_m^T \end{array}\right)\]](https://pressbooks.pub/app/uploads/quicklatex/quicklatex.com-ff92dd4466175e15383e56e7507c6d15_l3.png "Rendered by QuickLaTeX.com")
The linear regression approach can be extended to multiple dimensions, that is, to problems where the output in the above problem contains more than one dimension (see here). It can also be extended to the problem of fitting non-linear curves.
 |
In this example, we seek to analyze how customers react to an increase in the price of a given item. We are given two-dimensional data points  . The  ‘s contain the prices of the item, and the ‘s the average number of customers who buy the item at that price. |
The generic equation of a non-vertical line is  , where  contains the decision variables. The quality of the fit of a generic line is measured via the sum of the squares of the error in the component  (blue dotted lines). Thus, the best least-squares fit is obtained via the least-squares problem |
|
|
|
|
Once the line is found, it can be used to predict the value of the average number of customers buying the item () for a new price ( ). The prediction is shown in red. |
![\[\min _\theta \sum_{i=1}^m\left(\theta_1 x_i+\theta_2-y_i\right)^2 .\]](https://pressbooks.pub/app/uploads/quicklatex/quicklatex.com-d8c704ea848f16f5bccd1cc9606c500f_l3.png "Rendered by QuickLaTeX.com")
See also:
