The world’s leading publication for data science, AI, and ML professionals.

Comprehensive Study of Least Square Estimation (Part 2)

Ordinary, Constrained, Multi-objective, and Nonlinear least square.

Photo by Jay Mantri on Unsplash
Photo by Jay Mantri on Unsplash

In the first part, I discussed the ordinary least square problem in detail. In this part (part 2) I will go over the multi-objective least-square problems. If you have not already read the first part please refer to the following article for more information:

Comprehensive Study of Least Square Estimation (Part 1)

For more information and a more detailed explanation, please refer to my YouTube channel.

MANIE TADAYON

Multi-Objective Least Square

Assuming we are looking for a solution that makes more than one objective/cost functions small. This problem is referred to as a multi-objective optimization problem. If all the objective functions are in the form of a least-square problem then the problem is called the multi-objective least square problem.

Problem Formulation

Suppose we have K least-square objective function and our goal is to find a single x that makes all of them small.

Figure 1: Multi-Objective Least Square Problem Formulation
Figure 1: Multi-Objective Least Square Problem Formulation

Where each Aᵢ is mᵢ x n matrix and each bᵢ is mᵢ x 1 vector. There are many ways to solve and formulate the multi-objective LS problem but perhaps the most common method is to minimize the weighted sum of all objective functions, where the weights determine the influence or importance of each objective function.

Figure 2: Multi-Objective LS Problem Formulation
Figure 2: Multi-Objective LS Problem Formulation

where λ’s are the weights for each objective function. Here I introduce two methods to solve the multi-objective LS problems.

Method 1: Direct DifferentiationIn this method, we take the derivative of Jₜₒₜ with respect to x and set it to zero.

Figure 3: Multi-Objective LS Solution Using Direct Differentiation
Figure 3: Multi-Objective LS Solution Using Direct Differentiation

Although this method seems easy enough but the second method is more common and provides a better intuition. Method 1: Stacked MatrixThis is a better approach to solve the multi-objective LS problems since it takes advantage of the solution of the OLS problem and directly model the problem as an OLS problem. We first construct a new matrix A and B, then formulate the problem as a simple OLS problem as follows using what we derived in figure 2.

Figure 4: Multi-Objective LS Solution Using Stacked Matrix
Figure 4: Multi-Objective LS Solution Using Stacked Matrix

This method only works if the stacked A has linearly independent columns similar to an OLS where it requires matrix A to have linearly independent columns (tall and left invertible matrix).

When Stacked Matrix has Linearly Independent Columns

As it was mentioned before, to use the stacked matrix approach we need to make sure the stacked matrix is left-invertible or has linearly independent columns, this means:

Figure 5: Condition for Linearly Independent Columns
Figure 5: Condition for Linearly Independent Columns
  • If at least one of the matrices A₁, A₂, . . ., Aₖ has linearly independent columns then the stacked matrix will have the linearly independent columns.
  • However the stacked matrix can have linearly independent columns even if all the matrices A₁, A₂, . . ., Aₖ have linearly dependent columns and this happens when the following condition is met: Assume A₁ is m₁x n, A₂ is m₂ x n and Aₖ is mₖ by n then if each m_i is less than or equal to n but their sum is greater than or equal to n then the stacked matrix is still tall and can be a left invertible matrix (Linearly independent columns). Mathematically this means the following:

Figure 6: Condition for Linearly Independent Columns
Figure 6: Condition for Linearly Independent Columns

Tikhonov Regularization

Suppose you are trying to solve a least square problem given:

  • Matrix A does not have linearly independent columns.
  • Or we would like to minimize ||Ax – b||² such that ||x|| is small (norm of x is small).

One way to formulate this problem is as follows:

Figure 7: Regularized Least-Square
Figure 7: Regularized Least-Square

In figure 7, the λ is a positive weight and determines the importance of the second objective function compared to the first one. If λ is zero then we go back to the OLS. if λ is small then we place more weights on the first objective function. This is a common way of formulating the multi-objective problem by normalizing the weight of the primary objective function to 1 and let λ denotes the relative weights.

To solve the above equation we can use either method 1 or method 2, but to demonstrate the stacked matrix approach, we will be using the second method.

Figure 8: Regularize Least-Square using the Stacked Matrix
Figure 8: Regularize Least-Square using the Stacked Matrix

Before solving the above problem in figure 8, it is important to prove that stacked matrix A has linearly independent columns. There are two ways to prove this:

  1. The identity matrix has linearly independent columns therefore the stacked matrix has linearly independent columns whether A has dependent columns or not.
  2. Follow the standard procedure to prove the linear independence for the columns:
Figure 9: Prove that Stacked Matrix Has Linearly Independent Columns
Figure 9: Prove that Stacked Matrix Has Linearly Independent Columns

Now that the stacked matrix has linearly independent columns then the solution can be determined easily as follows:

Figure 10: Solution of Regularized Least Square
Figure 10: Solution of Regularized Least Square

To learn more about multi-objective Least Squares, please refer to my YouTube channel.

What is next:

Make sure to check out part 3 article on constrained least square.

Comprehensive Study of Least Square Estimation (Part 3)


Conclusion

In this article, I discuss multi-objective least square problems, in the next part (part 3) I will discuss the constrained- least square problems. If you find any part of this article or the previous one complicated, please refer to my YouTube channel, where I have a series of videos on numerical linear algebra and Optimization, which requires no prior knowledge in matrix algebra or optimization.


Related Articles