dev.nm.algebra.linear.matrix.doubles.linearsystem

Class OLSSolver

java.lang.Object

dev.nm.algebra.linear.matrix.doubles.linearsystem.OLSSolverByQR

dev.nm.algebra.linear.matrix.doubles.linearsystem.OLSSolver

public class OLSSolver
extends OLSSolverByQR

This class solves an over-determined system of linear equations in the ordinary least square sense. An over-determined system, represented by \[ Ax = y \] has more rows than columns. That is, there are more equations than unknowns. One important application is linear regression, where A is the independent factors, y the dependent observations. The solution \(\hat{x}\) minimizes: \[ \left\|Ax-y\right\|_2 \] That is, \(\hat{x}\) is the best approximation that minimizes the sum of squared differences between the data values and their corresponding modeled values. The approach is called "linear" least squares since the solution depends linearly on the data. \[ \hat{x} = (A^{\mathsf T}A)^{-1}A^{\mathsf T}y, \] This implementation does not use the above formula to solve for \(\hat{x}\) because of the numerical stability problem in computing \(A^{\mathsf T}A\). Instead, we use an orthogonal decomposition method.

Solve without forming an inverse

Supply a full-column-rank design matrix with at least as many rows as columns and a right-hand side with one entry per row. The returned vector has one coefficient per column. The solver does not insert an intercept; include a column of ones yourself, or use the regression API.

Example

 import dev.nm.algebra.linear.matrix.doubles.matrixtype.dense.DenseMatrix;
 import dev.nm.algebra.linear.matrix.doubles.linearsystem.LSProblem;
 import dev.nm.algebra.linear.matrix.doubles.linearsystem.OLSSolver;
 import dev.nm.algebra.linear.vector.doubles.Vector;
 import dev.nm.algebra.linear.vector.doubles.dense.DenseVector;

 DenseMatrix a = new DenseMatrix(new double[][]{{1, 0}, {1, 1}, {1, 2}});
 DenseVector b = new DenseVector(1.0, 3.0, 5.0);
 Vector coefficients = new OLSSolver(1e-12).solve(new LSProblem(a, b));
 assert Math.abs(coefficients.get(1) - 1.0) < 1e-10;
 assert Math.abs(coefficients.get(2) - 2.0) < 1e-10;
 assert a.multiply(coefficients).minus(b).norm() < 1e-10;
 

See Also:

• Wikipedia: Linear least squares
• Wikipedia: Least squares
• Wikipedia: Orthogonal decomposition methods

Constructor Summary

Constructors

Constructor and Description
OLSSolver(double epsilon) Construct an OLS solver for an over-determined system of linear equations.

Method Summary

Methods inherited from class dev.nm.algebra.linear.matrix.doubles.linearsystem.OLSSolverByQR

solve

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

OLSSolver

public OLSSolver(double epsilon)

Construct an OLS solver for an over-determined system of linear equations.

Parameters:

epsilon - a precision parameter: when a number |x| ≤ ε, it is considered 0