Linear System
Overview
A linear system is a collection of simultaneous linear equations that can be expressed in matrix form as ( Ax = b ). Here, ( A ) is a matrix, ( x ) is a vector of unknowns, and ( b ) is a vector of constants. This representation allows for the application of various mathematical techniques to find solutions. Solutions to linear systems can be obtained using matrix inverses or pseudo-inverses. However, solving a linear system using matrix inversion can be numerically unstable, especially if the determinant of the matrix ( A ) is near zero. In such cases, Singular Value Decomposition (SVD) provides a stable method to solve linear systems, even when the matrix is not square, by using the Moore-Penrose inverse to yield the best-effort solution.
Example
A typical example of a linear system is one that can be rewritten in the form ( Ax = b ), where ( A ) is a square matrix. This form is common in many applications, including those in engineering and physics, where systems of equations need to be solved simultaneously.
Zero or Near-Zero Determinants
A linear system with a zero determinant is termed singular and cannot be solved exactly. If the determinant is near-zero, the system is considered ill-conditioned and is numerically unstable. Ill-conditioned systems are sensitive to small changes in input, which can lead to large changes in the output. This instability poses challenges in numerical computations and requires careful handling to ensure accurate solutions.
Over- and Under-Determined Systems
Linear systems can be classified based on the number of equations relative to the number of unknowns. Over-determined systems have more equations than unknowns, while under-determined systems have fewer equations than unknowns. In machine learning and other fields, these systems are often solved iteratively. The pseudo-inverse is a useful tool in these scenarios, as it can be used to find a solution that minimizes the error.
Solving Without Inversion via Diagonalization
Solving linear systems without inversion can be achieved through diagonalization, particularly when dealing with symmetric matrices. This method involves diagonalizing the matrix ( A ) and utilizing the orthogonal properties of the eigenvectors to simplify the solution process. By avoiding matrix inversion, this approach enhances numerical stability and efficiency.
Solving via Diagonalization
Diagonalization is a powerful technique for solving linear systems. By transforming the matrix ( A ) into a diagonal form, the solution process is simplified. This method leverages the orthogonal properties of the eigenvectors, which helps in avoiding the computational pitfalls associated with matrix inversion.
Listing: Solving an Overdetermined Linear System
The following listing demonstrates solving an overdetermined linear system using the pseudo-inverse and SVD:
A = torch.tensor([[0.11, 0.09], [0.01, 0.02],
[0.98, 0.91], [0.12, 0.21],
[0.98, 0.99], [0.85, 0.87],
[0.03, 0.14], [0.55, 0.45],
[0.49, 0.51], [0.99, 0.01],
[0.02, 0.89], [0.31, 0.47],
[0.55, 0.29], [0.87, 0.76],
[0.63, 0.24]]) #1
A = torch.column_stack((A, torch.ones(15)))
b = torch.tensor([-0.8, -0.97, 0.89, -0.67,
0.97, 0.72, -0.83, 0.00,
0.00, 0.00, -0.09, -0.22,
-0.16, 0.63, 0.37])
x_0 = torch.matmul(torch.linalg.pinv(A), b) #2
U, S, V_t = torch.linalg.svd(A, full_matrices=False) #3
y1 = torch.matmul(U.T, b)
S_inv = torch.diag(1 / S)
y2 = torch.matmul(S_inv, y1)
x_1 = torch.matmul(V_t.T, y2)
assert torch.allclose(x_0, x_1) #4
#1 Cat-brain dataset: nonsquare matrix
#2 Solution via pseudo-inverse
#3 Solution via SVD
#4 The two solutions are the same.
This code snippet illustrates the use of the pseudo-inverse and SVD to solve an overdetermined system, ensuring that the solutions obtained through both methods are equivalent.