Class GramSchmidt

  • All Implemented Interfaces:
    QRDecomposition

    public class GramSchmidt
    extends Object
    implements QRDecomposition
    The Gram-Schmidt process is a method for orthogonalizing a set of vectors in an inner product space. It does so by iteratively computing the vector orthogonal to the subspace spanned by the previously found orthogonal vectors. An orthogonal vector is the difference between a column vector and its projection on the subspace.

    There is the problem of "loss of orthogonality" during the process. In general, the bigger the matrix is, e.g., dimension = 3500x3500, the less precise the result is. The vectors in Q may not be as orthogonal. This implementation uses a numerically stable Gram-Schmidt process with twice re-orthogonalization to alleviate the problem of rounding errors.

    Numerical determination of rank requires a criterion to decide how small a value should be treated as zero. This is a practical choice which depends on both the matrix and the application. For instance, for a matrix with a big first eigenvector, we should accordingly decrease the precision to compute the rank.

    While the result for the orthogonal basis may match those of the Householder reflection, the result for the orthogonal complement may differ because the kernel basis is not unique.

    See Also:
    • "Luc Giraud, Julien Langou, Miroslav Rozloznik, "On the loss of orthogonality in the Gram-Schmidt orthogonalization process," Computers & Mathematics with Applications, Volume 50, Issue 7, October 2005, p. 1069-1075. Numerical Methods and Computational Mechanics."
    • "Gene H. Golub, Charles F. Van Loan, Matrix Computations (Johns Hopkins Studies in Mathematical Sciences)(3rd Edition)(Paperback)."
    • Wikipedia: Gram-Schmidt process
    • Constructor Detail

      • GramSchmidt

        public GramSchmidt​(Matrix A,
                           boolean pad0Cols,
                           double epsilon)
        Run the Gram-Schmidt process to orthogonalize a matrix.
        Parameters:
        A - a matrix
        pad0Cols - when a column is linearly dependent on the previous columns, there is no orthogonal vector. We pad the basis with a 0-vector.
        epsilon - a precision parameter: when a number |x| ≤ ε, it is considered 0
      • GramSchmidt

        public GramSchmidt​(Matrix A)
        Run the Gram-Schmidt process to orthogonalize a matrix.
        Parameters:
        A - a matrix
    • Method Detail

      • Q

        public Matrix Q()
        Description copied from interface: QRDecomposition
        Get the orthogonal Q matrix in the QR decomposition, A = QR. The dimension of Q is m x n, the same as A, the matrix to be orthogonalized.
        Specified by:
        Q in interface QRDecomposition
        Returns:
        Q
      • R

        public UpperTriangularMatrix R()
        Description copied from interface: QRDecomposition
        Get the upper triangular matrix R in the QR decomposition, A = QR. The dimension of R is n x n, a square matrix.
        Specified by:
        R in interface QRDecomposition
        Returns:
        R
      • rank

        public int rank()
        Description copied from interface: QRDecomposition
        Get the numerical rank of A as computed by the QR decomposition. Numerical determination of rank requires a criterion to decide when a value should be treated as zero, hence a precision parameter. This is a practical choice which depends on both the matrix and the application. For instance, for a matrix with a big first eigenvector, we should accordingly decrease the precision to compute the rank.
        Specified by:
        rank in interface QRDecomposition
        Returns:
        the rank of A
      • squareQ

        public Matrix squareQ()
        Get the square Q matrix. This is an arbitrary orthogonal completion of the Q matrix in the QR decomposition. The dimension is m x m (square). We have A = sqQ * tallR. This implementation extends Q by appending A's orthogonal complement. Suppose Q has the orthogonal basis for a subspace A. To compute the orthogonal complement of A, we apply the Gram-Schmidt procedure to either
        1. the columns of I - P = I - Q * Q', or
        2. the spanning set \(\left \{ u_1, u_2, ..., u_k, e_1, e_2, ..., e_n \right \}\) and keeping only the first n elements of the resulting basis of Rn. The last n-k elements are the basis for the orthogonal complement. k is the rank.
        We implemented the second option.
        Specified by:
        squareQ in interface QRDecomposition
        Returns:
        the spanning set of both the orthogonal basis of A and the orthogonal complement
      • tallR

        public Matrix tallR()
        Description copied from interface: QRDecomposition
        Get the tall R matrix. This is completed by binding zero rows beneath the square upper triangular matrix R in the QR decomposition. The dimension is m x n. It may not be square. We have A = sqQ * tallR.
        Specified by:
        tallR in interface QRDecomposition
        Returns:
        the tall R matrix