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||_{2}^{2} \) for vector-based problems, or
  • \( ||AX - B||_{F}^{2} \) for matrix-based where problems
where \( ||\cdot||_{2} \) is the Euclidean vector norm and \( ||\cdot||_{F} \) is the Frobenius norm. This is equivalent to solving the normal equations given by: \( A^{H}Ax = A^{H}b \) or \( A^{H}AX = A^{H}B \)

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:

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: \[ \begin{alignat*}{6} & &A^HAx &= A^Hb &&\; \text{ or }\; &A^HAX &= A^HB \\ &\implies &(QR)^HQRx &= (QR)^Hb &&\; \text{ or }\; &(QR)^HQRX &= (QR)^HB \\ &\implies &R^HQ^HQRx &= R^HQ^Hb &&\; \text{ or }\; &R^HQ^HQRX &= R^HQ^HB \\ &\implies &R^HRx &= R^HQ^Hb &&\; \text{ or }\; &R^HRX &= R^HQ^HB \quad \text{ since } Q \text{ is unitary.} \\ &\implies &Rx &= Q^Hb &&\; \text{ or }\; & RX &= Q^HB \end{alignat*} \] 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 \( c \) 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:

    • 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

      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.