Solving Over- and Under-Determined Systems

In linear algebra, many real-world problems involve systems of equations where the number of equations does not match the number of unknowns. These systems are either over-determined (more equations than unknowns) or under-determined (more unknowns than equations). This article explores the methods for solving such systems, discussing techniques like Least Squares solutions, regularization, and providing practical examples in data science and engineering.

1. Introduction to Over- and Under-Determined Systems

1.1 What is an Over-Determined System?

An over-determined system is a system of linear equations in which there are more equations than unknowns. Mathematically, for a system $\mathbf{A}\mathbf{x} = \mathbf{b}$, if the matrix $\mathbf{A}$ is $m \times n$ with $m > n$, the system is over-determined.

Example: Consider the system of equations:

$$\begin{aligned} 2x + y &= 5 \\ 3x - y &= 3 \\ x + 2y &= 4 \\ \end{aligned}$$

This system has 3 equations and 2 unknowns, making it over-determined. In general, over-determined systems may not have a solution that satisfies all equations exactly.

1.2 What is an Under-Determined System?

An under-determined system is a system where there are fewer equations than unknowns. For a system $\mathbf{A}\mathbf{x} = \mathbf{b}$, if the matrix $\mathbf{A}$ is $m \times n$ with $m < n$, the system is under-determined.

Example: Consider the system:

$$\begin{aligned} x + 2y + z &= 1 \\ 2x + y + 3z &= 4 \\ \end{aligned}$$

This system has 2 equations and 3 unknowns, making it under-determined. Such systems typically have infinitely many solutions or special solutions depending on the constraints.

2. Solving Over-Determined Systems

2.1 Least Squares Solution

The Least Squares method is the most common approach to solving over-determined systems. It finds an approximate solution that minimizes the sum of the squared residuals, where the residual is the difference between the observed value and the value predicted by the model.

Mathematically: Given $\mathbf{A}\mathbf{x} = \mathbf{b}$, where $\mathbf{A}$ is $m \times n$ with $m > n$, the Least Squares solution $\mathbf{\hat{x}}$ minimizes:

$$\|\mathbf{A}\mathbf{x} - \mathbf{b}\|_2^2$$

This leads to the Normal Equations:

$$\mathbf{A}^\top \mathbf{A} \mathbf{\hat{x}} = \mathbf{A}^\top \mathbf{b}$$

Example: Consider the following over-determined system:

$$\mathbf{A} = \begin{pmatrix} 2 & 1 \\ 3 & -1 \\ 1 & 2 \end{pmatrix}, \quad \mathbf{b} = \begin{pmatrix} 5 \\ 3 \\ 4 \end{pmatrix}$$

To solve using Least Squares:

1. Compute $\mathbf{A}^\top \mathbf{A}$ and $\mathbf{A}^\top \mathbf{b}$:

$$\mathbf{A}^\top \mathbf{A} = \begin{pmatrix} 14 & 4 \\ 4 & 6 \end{pmatrix}, \quad \mathbf{A}^\top \mathbf{b} = \begin{pmatrix} 23 \\ 12 \end{pmatrix}$$

2. Solve the normal equations $\mathbf{A}^\top \mathbf{A} \mathbf{\hat{x}} = \mathbf{A}^\top \mathbf{b}$:

$$\begin{pmatrix} 14 & 4 \\ 4 & 6 \end{pmatrix} \begin{pmatrix} \hat{x}_1 \\ \hat{x}_2 \end{pmatrix} = \begin{pmatrix} 23 \\ 12 \end{pmatrix}$$

3. The solution is:

$$\mathbf{\hat{x}} = \begin{pmatrix} 1.5 \\ 1.5 \end{pmatrix}$$

2.2 Solving Over-Determined Systems with QR Decomposition

QR Decomposition can also be used to solve over-determined systems. If $\mathbf{A}$ can be decomposed as $\mathbf{A} = \mathbf{Q}\mathbf{R}$, where $\mathbf{Q}$ is an orthogonal matrix and $\mathbf{R}$ is upper triangular, the problem reduces to solving:

$$\mathbf{R}\mathbf{x} = \mathbf{Q}^\top \mathbf{b}$$

Example: Using the same $\mathbf{A}$ from above, decompose it into $\mathbf{Q}\mathbf{R}$ and solve the reduced system for $\mathbf{x}$.

2.3 Using Singular Value Decomposition (SVD)

Singular Value Decomposition (SVD) provides a robust method for solving over-determined systems, particularly when $\mathbf{A}$ is ill-conditioned. The system can be solved by expressing $\mathbf{A}$ as:

$$\mathbf{A} = \mathbf{U} \mathbf{\Sigma} \mathbf{V}^\top$$

The solution $\mathbf{\hat{x}}$ is then:

$$\mathbf{\hat{x}} = \mathbf{V} \mathbf{\Sigma}^{-1} \mathbf{U}^\top \mathbf{b}$$

This approach is particularly useful when the matrix $\mathbf{A}$ is close to being singular or has large condition numbers.

3. Solving Under-Determined Systems

3.1 General Solution Approach

For under-determined systems, there are typically infinitely many solutions. The general solution can be expressed as:

$$\mathbf{x} = \mathbf{x}_p + \mathbf{x}_h$$

Where:

• $\mathbf{x}_p$ is a particular solution.
• $\mathbf{x}_h$ is the general solution to the homogeneous system $\mathbf{A}\mathbf{x} = \mathbf{0}$, which lies in the null space of $\mathbf{A}$.

3.2 Minimum Norm Solution

In many cases, especially in optimization, we are interested in the minimum norm solution, which is the solution with the smallest L2 norm. This solution can be found using SVD:

$$\mathbf{x}_{\text{min-norm}} = \mathbf{V} \mathbf{\Sigma}^{\dagger} \mathbf{U}^\top \mathbf{b}$$

Where $\mathbf{\Sigma}^{\dagger}$ is the pseudo-inverse of $\mathbf{\Sigma}$.

Example: Consider the under-determined system:

$$\mathbf{A} = \begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{pmatrix}, \quad \mathbf{b} = \begin{pmatrix} 1 \\ 4 \end{pmatrix}$$

To find the minimum norm solution using SVD:

1. Decompose $\mathbf{A}$ into $\mathbf{U}\mathbf{\Sigma}\mathbf{V}^\top$.
2. Compute the pseudo-inverse of $\mathbf{\Sigma}$.
3. Calculate $\mathbf{x}_{\text{min-norm}}$.

3.3 Regularization Techniques

In practice, under-determined systems are often solved using regularization techniques to impose additional constraints that lead to a unique and stable solution.

• L2 Regularization (Tikhonov Regularization): Adds a penalty term proportional to the L2 norm of the solution:

$$\mathbf{x}_{\text{reg}} = \text{argmin} \|\mathbf{A}\mathbf{x} - \mathbf{b}\|_2^2 + \lambda \|\mathbf{x}\|_2^2$$

Where $\lambda$ is a regularization parameter that controls the trade-off between fitting the data and minimizing the solution norm.

• L1 Regularization (Lasso): Adds a penalty proportional to the L1 norm of the solution, encouraging sparsity:

$$\mathbf{x}_{\text{reg}} = \text{argmin} \|\mathbf{A}\mathbf{x} - \mathbf{b}\|_2^2 + \lambda \|\mathbf{x}\|_1$$

These techniques are widely used in machine learning and signal processing to obtain stable solutions in the presence of noise or incomplete data.

4. Applications and Practical Examples

4.1 Data Fitting in Regression Analysis

In regression analysis, over-determined systems are common when fitting a model to data. The Least Squares method is used to minimize the difference between the observed data and the model predictions. Regularization is often applied to prevent overfitting, especially when the model is complex.

Example: In a linear regression problem with many data points (more than the number of parameters), the system is over-determined, and the Least Squares solution provides the best-fit line.

4.2 Inverse Problems in Physics and Engineering

Inverse problems, such as recovering a signal or an image from indirect measurements, often lead to under-determined systems. Regularization techniques are crucial in obtaining meaningful solutions.

Example: In medical imaging (e.g., MRI), the measured data is incomplete, and solving the inverse problem to reconstruct the image involves solving an under-determined system with regularization.

4.3 Optimization Problems

Optimization problems frequently involve under-determined systems, particularly in cases where the number of constraints is less than the number of variables. The minimum norm solution or regularization methods help in finding the most "reasonable" solution.

Example: In portfolio optimization, where the number of assets (variables) exceeds the number of constraints (such as target return), the system is under-determined, and regularization can be used to find an optimal portfolio with minimum risk.

5. Conclusion

Solving over- and under-determined systems is a fundamental task in linear algebra with wide-ranging applications in data science, engineering, and beyond. The methods discussed—Least Squares, QR Decomposition, SVD, and regularization techniques—provide robust tools for tackling these systems, even in the presence of noise, ill-conditioning, or incomplete data. By mastering these techniques, practitioners can develop more accurate and stable solutions to complex real-world problems.