Class LstsqSolver<T extends MatrixMixin<T,?,U,?>,U extends VectorMixin<U,T,?,?>>

java.lang.Object

org.flag4j.linalg.solvers.lstsq.LstsqSolver<T,U>

Type Parameters:

T - The matrix type in the linear system.

U - The vector type in the linear system.

All Implemented Interfaces:

LinearMatrixSolver<T,U>, LinearSolver<T>

Direct Known Subclasses:

ComplexLstsqSolver, RealLstsqSolver

public abstract class LstsqSolver<T extends MatrixMixin<T,?,U,?>,U extends VectorMixin<U,T,?,?>>
extends Object
implements LinearMatrixSolver<T,U>

An abstract solver for linear systems of the form Ax = b or AX = B in a least-squares sense. The system may be under-, well-, or over-determined. Specifically, this solver minimizes the sum of squared residuals:

• ||Ax - b||₂² for vector-based problems, or
• ||AX - B||_F² for matrix-based where problems

where ||·||₂ is the Euclidean vector norm and ||·||_F is the Frobenius norm. This is equivalent to solving the normal equations given by: A^HAx = A^Hb or A^HAX = A^HB

Usage:

A single system may be solved by calling either solve(MatrixMixin, VectorMixin) or solve(MatrixMixin, VectorMixin).

Instances of this solver may also be used to efficiently solve many systems of the form Ax = b or AX = B for the same coefficient matrix A but numerous constant vectors/matrices b or B. To do this, the workflow would be as follows:

1. Create a concrete instance of LstsqSolver.
2. Call decompse(A) once on the coefficient matrix A.
3. Call solve(b) or solve(B) as many times as needed to solve each system for with the various b vectors and/or B matrices.

Note: Any call made to one of the following methods after a call to decompse(A) will override the coefficient matrix set that call:

• solve(MatrixMixin, VectorMixin)
• solve(MatrixMixin, MatrixMixin)

Implementation Notes:

Minimizing the sum of squared residuals is achieved by computing a QR decomposition of the coefficient matrix A:

A = QR

where Q is a unitary/orthonormal matrix and R is an upper triangular matrix. The normal equations then reduces to:

A^HAx = A^Hb or A^HAX = A^HB
⇒ (QR)^HQRx = (QR)^Hb or (QR)^HQRX = (QR)^HB
⇒ R^HQ^HQRx = R^HQ^Hb or R^HQ^HQRX = R^HQ^HB
⇒ R^HRx = R^HQ^Hb or R^HRX = R^HQ^HB since Q is unitary/orthonormal.
⇒ Rx = Q^Hb or RX = Q^HB

which is easily solved by back-substitution on R. In the real case, Q^H simply becomes Q^T.

Field Summary

Fields

Modifier and Type	Field	Description
protected final LinearMatrixSolver<T,U>	backSolver	Solver for system with an upper triangular coefficient matrix.
protected T	Qh	The Hermitian transpose of the unitary matrix, Q, from the QR decomposition.
protected final UnitaryDecomposition<T,?>	qr	Decomposer to compute the QR decomposition for using the least-squares solver.
protected T	R	The upper triangular matrix, R, from the QR decomposition.

Constructor Summary

Constructors

Modifier	Constructor	Description
protected	LstsqSolver(UnitaryDecomposition<T,?> qr, LinearMatrixSolver<T,U> backSolver)	Constructs a least-squares solver with a specified decomposer to use in the QR decomposition.

Method Summary

Modifier and Type	Method	Description
void	decompose(T A)	Computes (or updates) the QR decomposition of the given matrix A for use in subsequent solves.
T	solve(T B)	Solves the set of linear system of equations given by AX = B for the matrix X in a least-squares sense.
T	solve(T A, T B)	Solves the linear system of equation given by AX = B for the matrix X in a least-squares sense.
U	solve(T A, U b)	Solves the linear system given by Ax = b in a least-squares sense.
U	solve(U b)	Solves the linear system given by Ax = b in a least-squares sense.

Methods inherited from class java.lang.Object

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

Field Details

backSolver

protected final LinearMatrixSolver<T extends MatrixMixin<T,?,U,?>,U extends VectorMixin<U,T,?,?>> backSolver

Solver for system with an upper triangular coefficient matrix.

qr

protected final UnitaryDecomposition<T extends MatrixMixin<T,?,U,?>,?> qr

Decomposer to compute the QR decomposition for using the least-squares solver.

Qh

protected T extends MatrixMixin<T,?,U,?> Qh

The Hermitian transpose of the unitary matrix, Q, from the QR decomposition.

R

protected T extends MatrixMixin<T,?,U,?> R

The upper triangular matrix, R, from the QR decomposition.

Constructor Details

LstsqSolver

protected LstsqSolver(UnitaryDecomposition<T,?> qr,
 LinearMatrixSolver<T,U> backSolver)

Constructs a least-squares solver with a specified decomposer to use in the QR decomposition.

Parameters:

qr - The QR decomposer to use in the solver.

backSolver - The solver to solve the upper triangular system resulting from the QR decomposition which is equivalent to solving the normal equations

Method Details

solve

public U solve(T A,
 U b)

Solves the linear system given by Ax = b in a least-squares sense.

Note: Any call of this method will override the coefficient matrix specified in any previous calls to decompose(MatrixMixin) on the same solver instance.

Specified by:

solve in interface LinearMatrixSolver<T extends MatrixMixin<T,?,U,?>,U extends VectorMixin<U,T,?,?>>

Parameters:

A - Coefficient matrix, A, in the linear system.

b - Constant vector, b, in the linear system.

Returns:

The least-squares solution to x in the linear system Ax = b.

solve

public T solve(T A,
 T B)

Solves the linear system of equation given by AX = B for the matrix X in a least-squares sense.

Note: Any call of this method will override the coefficient matrix specified in any previous calls to decompose(MatrixMixin) on the same solver instance.

Specified by:

solve in interface LinearMatrixSolver<T extends MatrixMixin<T,?,U,?>,U extends VectorMixin<U,T,?,?>>

Specified by:

solve in interface LinearSolver<T extends MatrixMixin<T,?,U,?>>

Parameters:

A - Coefficient matrix, A, in the linear system.

B - Constant matrix, B, in the linear system.

Returns:

The solution to x in the linear system AX = B.

solve

public U solve(U b)

Solves the linear system given by Ax = b in a least-squares sense.

Parameters:

b - Constant vector, b, in the linear system.

Returns:

The solution to x in the linear system Ax = b for the last A passed to decompose(MatrixMixin).

Throws:

IllegalStateException - If no coefficient matrix has been specified for this solver by first calling one of the following:

• decompose(MatrixMixin)
• solve(MatrixMixin, VectorMixin)
• solve(MatrixMixin, MatrixMixin)

solve

public T solve(T B)

Solves the set of linear system of equations given by AX = B for the matrix X in a least-squares sense.

Parameters:

B - Constant matrix, B, in the linear system.

Returns:

The solution to X in the linear system AX = B for the last A passed to decompose(MatrixMixin).

Throws:

IllegalStateException - If no coefficient matrix has been specified for this solver by first calling one of the following:

• decompose(MatrixMixin)
• solve(MatrixMixin, VectorMixin)
• solve(MatrixMixin, MatrixMixin)

decompose

public void decompose(T A)

Computes (or updates) the QR decomposition of the given matrix A for use in subsequent solves.

Subclasses may override this method to customize how the QR decomposition is computed or updated.

Parameters:

A - Coefficient matrix to decompose.