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||22 for vector-based problems, or
  • ||AX - B||F2 for matrix-based where problems
where ||·||2 is the Euclidean vector norm and ||·||F is the Frobenius norm. This is equivalent to solving the normal equations given by: AHAx = AHb or AHAX = AHB

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:
AHAx = AHb or AHAX = AHB
(QR)HQRx = (QR)Hb   or   (QR)HQRX = (QR)HB
RHQHQRx = RHQHb   or   RHQHQRX = RHQHB
RHRx = RHQHb   or   RHRX = RHQHB since Q is unitary/orthonormal.
Rx = QHb   or   RX = QHB
which is easily solved by back-substitution on R. In the real case, QH simply becomes QT.
  • Field Summary

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

    Constructors
    Modifier
    Constructor
    Description
    protected
    Constructs a least-squares solver with a specified decomposer to use in the QR decomposition.
  • Method Summary

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