Least-Squares Method

5 min readApr 22, 2018

Outline

Least-squares method is a simple (but yet powerful) tool for solving problems in engineering and economics.
Two examples of least-squares method and how to formulate them.
The method can be solved efficiently solved by using CVX solvers available in several programming languages such as Python, MATLAB and R.

Introduction

Least-squares problem is one of the significant numerical problems in science, engineering and economics. Data-fitting (or linear regression) problems in econometrics and SVM classification problems in machine learning can be formulated on the form of the least-squares problems. The goal based on this basic problem is to fit a model to a given set of observations.

Even though the concept is simple, let me take a Data-fitting problem as an example to illustrate how to formulate it on the form of the least-squares problem. Also, I show you how to use CVX as a numerical tool available in MATLAB (and also python) to solve the least-squares problem.

Example 1 (Data-fitting problem)

Suppose that we have collected a set of n observed data points

The objective is to model the relationship between x and y, i.e. we find y = f(x) that is close fit to the given data. One of the simplest models is the linear relationship between x and y; that is, y_hat = ax + b. The figure below shows the plot of the observed data ( x_i , y_i ) and the predicted output y_hat.

Thus, the task is to find the coefficients a, b which can minimizes the error between the predicted output y_hat and the observed output y as explained below:

Now, we can simplify the least-squares problem on the form where we estimate the parameter vector x collecting the coefficients a , b such that it minimizes || Ax - b ||² given the data A ,b by the following steps: The first step is shown below.

A simpler form of the least-squares problem for data-fitting problem

Finally, the problem can be manipulated into the even much simpler form:

The simplest form of the least-squares problem for data-fitting problem

At this point, the least-squares problem is to find the approximate vector x which actually minimizes ||Ax - b||² where A , b are given, as summarized in the following:

Implementations of the solver for least-squares problem using CVX in MATLAB.

Now, let me demonstrate how to solve find the coefficient vector x, given the data on the matrix and vector forms A , b in CVX in MATLAB. The toy example is to find the linear relationship of x , y on the form of y_hat = a x + b which is best fit to the given data. The code consists of three steps:

I generated five observed data ( x , y )
I wrote the data matrix and vector A , b as explained above
I wrote a CVX script to solve the minimization problem of || Ax -b ||²

Here are the detailed code lines solved in MATLAB along with the figure showing the relationship I obtained (line) against the observed data (dot).

% Generate the observed data. 
% Here, x_1 = 1 and y_1 = 1, and  x_3 = 3 and y_3 = 11.x_data = [ 1 , 2 , 3 , 4 , 5 ]; 
y_data = [ 1 , 3 , 11 , 15 , 30 ];   % define A , b according to our derivation A = [ x_data' , ones(5,1) ] ;  % each row of A is [ x_i   1 ]
b = y_data' ;                  % each row of b is y_i % Solve the equation using CVX in MATLABcvx_beginvariable x(2) minimize ( norm( A * x - b , 2)^2 )   % solve  min || Ax - b ||^2.cvx_end

Plot of the relationship I obtained from solving the least-squares problem (line) against the observed data (dot)

Example 2 (Least-squares SVM classification problem)

Next, I show how to formulate the celebrated binary classification problem in machine learning on the form of the least-squares problem. The goal of this machine learning problem is to classify two classes (red and blue) based on a given data.

To formalize the problem, assume that we are given a set of training data samples (a_1 , b_1), (a_2 , b_2), …, (a_m , b_m) where

a_i is the feature vector of data sample i
b_i is the class label which can be 1 if the data belongs to red, and -1 if the data belongs to blue.

Hence, the aim is to train the weight vector x such that the predicted output

gives us the correct class label. To simplify the problem, let us assume that the predicted output has the linear relationship with the feature of data sample i, meaning that

Hence, the problem is to find the weight vector x which minimizes the error between the predicted class label y_hat and the class label y. This problem can be described on the least-squares form using the following steps shown below:

Again, we can simplify the least-squares problem on the form where we estimate the parameter vector x (which is our weight vector) such that it minimizes || Ax — b ||² given the data A ,b.

Conclusion

The least-squares problem is one of the problems which cover ubiquitous applications in engineering, economics and statistics. In addition, the least-squares problem can be solved using pre-installed libraries such as CVX in several programming languages such as MATLAB, python, and R.