SingularValueDecomposition.java

  1. /*
  2.  * Licensed to the Apache Software Foundation (ASF) under one or more
  3.  * contributor license agreements.  See the NOTICE file distributed with
  4.  * this work for additional information regarding copyright ownership.
  5.  * The ASF licenses this file to You under the Apache License, Version 2.0
  6.  * (the "License"); you may not use this file except in compliance with
  7.  * the License.  You may obtain a copy of the License at
  8.  *
  9.  *      http://www.apache.org/licenses/LICENSE-2.0
  10.  *
  11.  * Unless required by applicable law or agreed to in writing, software
  12.  * distributed under the License is distributed on an "AS IS" BASIS,
  13.  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14.  * See the License for the specific language governing permissions and
  15.  * limitations under the License.
  16.  */
  17. package org.apache.commons.math4.legacy.linear;

  19. import org.apache.commons.math4.legacy.exception.NumberIsTooLargeException;
  20. import org.apache.commons.math4.legacy.exception.util.LocalizedFormats;
  21. import org.apache.commons.math4.core.jdkmath.JdkMath;
  22. import org.apache.commons.numbers.core.Precision;

  24. /**
  25.  * Calculates the compact Singular Value Decomposition of a matrix.
  26.  * <p>
  27.  * The Singular Value Decomposition of matrix A is a set of three matrices: U,
  28.  * &Sigma; and V such that A = U &times; &Sigma; &times; V<sup>T</sup>. Let A be
  29.  * a m &times; n matrix, then U is a m &times; p orthogonal matrix, &Sigma; is a
  30.  * p &times; p diagonal matrix with positive or null elements, V is a p &times;
  31.  * n orthogonal matrix (hence V<sup>T</sup> is also orthogonal) where
  32.  * p=min(m,n).
  33.  * </p>
  34.  * <p>This class is similar to the class with similar name from the
  35.  * <a href="http://math.nist.gov/javanumerics/jama/">JAMA</a> library, with the
  36.  * following changes:</p>
  37.  * <ul>
  38.  *   <li>the {@code norm2} method which has been renamed as {@link #getNorm()
  39.  *   getNorm},</li>
  40.  *   <li>the {@code cond} method which has been renamed as {@link
  41.  *   #getConditionNumber() getConditionNumber},</li>
  42.  *   <li>the {@code rank} method which has been renamed as {@link #getRank()
  43.  *   getRank},</li>
  44.  *   <li>a {@link #getUT() getUT} method has been added,</li>
  45.  *   <li>a {@link #getVT() getVT} method has been added,</li>
  46.  *   <li>a {@link #getSolver() getSolver} method has been added,</li>
  47.  *   <li>a {@link #getCovariance(double) getCovariance} method has been added.</li>
  48.  * </ul>
  49.  * @see <a href="http://mathworld.wolfram.com/SingularValueDecomposition.html">MathWorld</a>
  50.  * @see <a href="http://en.wikipedia.org/wiki/Singular_value_decomposition">Wikipedia</a>
  51.  * @since 2.0 (changed to concrete class in 3.0)
  52.  */
  53. public class SingularValueDecomposition {
  54.     /** Relative threshold for small singular values. */
  55.     private static final double EPS = 0x1.0p-52;
  56.     /** Absolute threshold for small singular values. */
  57.     private static final double TINY = 0x1.0p-966;
  58.     /** Computed singular values. */
  59.     private final double[] singularValues;
  60.     /** max(row dimension, column dimension). */
  61.     private final int m;
  62.     /** min(row dimension, column dimension). */
  63.     private final int n;
  64.     /** Indicator for transposed matrix. */
  65.     private final boolean transposed;
  66.     /** Cached value of U matrix. */
  67.     private final RealMatrix cachedU;
  68.     /** Cached value of transposed U matrix. */
  69.     private RealMatrix cachedUt;
  70.     /** Cached value of S (diagonal) matrix. */
  71.     private RealMatrix cachedS;
  72.     /** Cached value of V matrix. */
  73.     private final RealMatrix cachedV;
  74.     /** Cached value of transposed V matrix. */
  75.     private RealMatrix cachedVt;
  76.     /**
  77.      * Tolerance value for small singular values, calculated once we have
  78.      * populated "singularValues".
  79.      **/
  80.     private final double tol;

  82.     /**
  83.      * Calculates the compact Singular Value Decomposition of the given matrix.
  84.      *
  85.      * @param matrix Matrix to decompose.
  86.      */
  87.     public SingularValueDecomposition(final RealMatrix matrix) {
  88.         final double[][] A;

  90.          // "m" is always the largest dimension.
  91.         if (matrix.getRowDimension() < matrix.getColumnDimension()) {
  92.             transposed = true;
  93.             A = matrix.transpose().getData();
  94.             m = matrix.getColumnDimension();
  95.             n = matrix.getRowDimension();
  96.         } else {
  97.             transposed = false;
  98.             A = matrix.getData();
  99.             m = matrix.getRowDimension();
  100.             n = matrix.getColumnDimension();
  101.         }

  103.         singularValues = new double[n];
  104.         final double[][] U = new double[m][n];
  105.         final double[][] V = new double[n][n];
  106.         final double[] e = new double[n];
  107.         final double[] work = new double[m];
  108.         // Reduce A to bidiagonal form, storing the diagonal elements
  109.         // in s and the super-diagonal elements in e.
  110.         final int nct = JdkMath.min(m - 1, n);
  111.         final int nrt = JdkMath.max(0, n - 2);
  112.         for (int k = 0; k < JdkMath.max(nct, nrt); k++) {
  113.             if (k < nct) {
  114.                 // Compute the transformation for the k-th column and
  115.                 // place the k-th diagonal in s[k].
  116.                 // Compute 2-norm of k-th column without under/overflow.
  117.                 singularValues[k] = 0;
  118.                 for (int i = k; i < m; i++) {
  119.                     singularValues[k] = JdkMath.hypot(singularValues[k], A[i][k]);
  120.                 }
  121.                 if (singularValues[k] != 0) {
  122.                     if (A[k][k] < 0) {
  123.                         singularValues[k] = -singularValues[k];
  124.                     }
  125.                     for (int i = k; i < m; i++) {
  126.                         A[i][k] /= singularValues[k];
  127.                     }
  128.                     A[k][k] += 1;
  129.                 }
  130.                 singularValues[k] = -singularValues[k];
  131.             }
  132.             for (int j = k + 1; j < n; j++) {
  133.                 if (k < nct &&
  134.                     singularValues[k] != 0) {
  135.                     // Apply the transformation.
  136.                     double t = 0;
  137.                     for (int i = k; i < m; i++) {
  138.                         t += A[i][k] * A[i][j];
  139.                     }
  140.                     t = -t / A[k][k];
  141.                     for (int i = k; i < m; i++) {
  142.                         A[i][j] += t * A[i][k];
  143.                     }
  144.                 }
  145.                 // Place the k-th row of A into e for the
  146.                 // subsequent calculation of the row transformation.
  147.                 e[j] = A[k][j];
  148.             }
  149.             if (k < nct) {
  150.                 // Place the transformation in U for subsequent back
  151.                 // multiplication.
  152.                 for (int i = k; i < m; i++) {
  153.                     U[i][k] = A[i][k];
  154.                 }
  155.             }
  156.             if (k < nrt) {
  157.                 // Compute the k-th row transformation and place the
  158.                 // k-th super-diagonal in e[k].
  159.                 // Compute 2-norm without under/overflow.
  160.                 e[k] = 0;
  161.                 for (int i = k + 1; i < n; i++) {
  162.                     e[k] = JdkMath.hypot(e[k], e[i]);
  163.                 }
  164.                 if (e[k] != 0) {
  165.                     if (e[k + 1] < 0) {
  166.                         e[k] = -e[k];
  167.                     }
  168.                     for (int i = k + 1; i < n; i++) {
  169.                         e[i] /= e[k];
  170.                     }
  171.                     e[k + 1] += 1;
  172.                 }
  173.                 e[k] = -e[k];
  174.                 if (k + 1 < m &&
  175.                     e[k] != 0) {
  176.                     // Apply the transformation.
  177.                     for (int i = k + 1; i < m; i++) {
  178.                         work[i] = 0;
  179.                     }
  180.                     for (int j = k + 1; j < n; j++) {
  181.                         for (int i = k + 1; i < m; i++) {
  182.                             work[i] += e[j] * A[i][j];
  183.                         }
  184.                     }
  185.                     for (int j = k + 1; j < n; j++) {
  186.                         final double t = -e[j] / e[k + 1];
  187.                         for (int i = k + 1; i < m; i++) {
  188.                             A[i][j] += t * work[i];
  189.                         }
  190.                     }
  191.                 }

  193.                 // Place the transformation in V for subsequent
  194.                 // back multiplication.
  195.                 for (int i = k + 1; i < n; i++) {
  196.                     V[i][k] = e[i];
  197.                 }
  198.             }
  199.         }
  200.         // Set up the final bidiagonal matrix or order p.
  201.         int p = n;
  202.         if (nct < n) {
  203.             singularValues[nct] = A[nct][nct];
  204.         }
  205.         if (m < p) {
  206.             singularValues[p - 1] = 0;
  207.         }
  208.         if (nrt + 1 < p) {
  209.             e[nrt] = A[nrt][p - 1];
  210.         }
  211.         e[p - 1] = 0;

  213.         // Generate U.
  214.         for (int j = nct; j < n; j++) {
  215.             for (int i = 0; i < m; i++) {
  216.                 U[i][j] = 0;
  217.             }
  218.             U[j][j] = 1;
  219.         }
  220.         for (int k = nct - 1; k >= 0; k--) {
  221.             if (singularValues[k] != 0) {
  222.                 for (int j = k + 1; j < n; j++) {
  223.                     double t = 0;
  224.                     for (int i = k; i < m; i++) {
  225.                         t += U[i][k] * U[i][j];
  226.                     }
  227.                     t = -t / U[k][k];
  228.                     for (int i = k; i < m; i++) {
  229.                         U[i][j] += t * U[i][k];
  230.                     }
  231.                 }
  232.                 for (int i = k; i < m; i++) {
  233.                     U[i][k] = -U[i][k];
  234.                 }
  235.                 U[k][k] = 1 + U[k][k];
  236.                 for (int i = 0; i < k - 1; i++) {
  237.                     U[i][k] = 0;
  238.                 }
  239.             } else {
  240.                 for (int i = 0; i < m; i++) {
  241.                     U[i][k] = 0;
  242.                 }
  243.                 U[k][k] = 1;
  244.             }
  245.         }

  247.         // Generate V.
  248.         for (int k = n - 1; k >= 0; k--) {
  249.             if (k < nrt &&
  250.                 e[k] != 0) {
  251.                 for (int j = k + 1; j < n; j++) {
  252.                     double t = 0;
  253.                     for (int i = k + 1; i < n; i++) {
  254.                         t += V[i][k] * V[i][j];
  255.                     }
  256.                     t = -t / V[k + 1][k];
  257.                     for (int i = k + 1; i < n; i++) {
  258.                         V[i][j] += t * V[i][k];
  259.                     }
  260.                 }
  261.             }
  262.             for (int i = 0; i < n; i++) {
  263.                 V[i][k] = 0;
  264.             }
  265.             V[k][k] = 1;
  266.         }

  268.         // Main iteration loop for the singular values.
  269.         final int pp = p - 1;
  270.         while (p > 0) {
  271.             int k;
  272.             int kase;
  273.             // Here is where a test for too many iterations would go.
  274.             // This section of the program inspects for
  275.             // negligible elements in the s and e arrays.  On
  276.             // completion the variables kase and k are set as follows.
  277.             // kase = 1     if s(p) and e[k-1] are negligible and k<p
  278.             // kase = 2     if s(k) is negligible and k<p
  279.             // kase = 3     if e[k-1] is negligible, k<p, and
  280.             //              s(k), ..., s(p) are not negligible (qr step).
  281.             // kase = 4     if e(p-1) is negligible (convergence).
  282.             for (k = p - 2; k >= 0; k--) {
  283.                 final double threshold
  284.                     = TINY + EPS * (JdkMath.abs(singularValues[k]) +
  285.                                     JdkMath.abs(singularValues[k + 1]));

  287.                 // the following condition is written this way in order
  288.                 // to break out of the loop when NaN occurs, writing it
  289.                 // as "if (JdkMath.abs(e[k]) <= threshold)" would loop
  290.                 // indefinitely in case of NaNs because comparison on NaNs
  291.                 // always return false, regardless of what is checked
  292.                 // see issue MATH-947
  293.                 if (!(JdkMath.abs(e[k]) > threshold)) {
  294.                     e[k] = 0;
  295.                     break;
  296.                 }
  297.             }

  299.             if (k == p - 2) {
  300.                 kase = 4;
  301.             } else {
  302.                 int ks;
  303.                 for (ks = p - 1; ks >= k; ks--) {
  304.                     if (ks == k) {
  305.                         break;
  306.                     }
  307.                     final double t = (ks != p ? JdkMath.abs(e[ks]) : 0) +
  308.                         (ks != k + 1 ? JdkMath.abs(e[ks - 1]) : 0);
  309.                     if (JdkMath.abs(singularValues[ks]) <= TINY + EPS * t) {
  310.                         singularValues[ks] = 0;
  311.                         break;
  312.                     }
  313.                 }
  314.                 if (ks == k) {
  315.                     kase = 3;
  316.                 } else if (ks == p - 1) {
  317.                     kase = 1;
  318.                 } else {
  319.                     kase = 2;
  320.                     k = ks;
  321.                 }
  322.             }
  323.             k++;
  324.             // Perform the task indicated by kase.
  325.             double f;
  326.             switch (kase) {
  327.                 // Deflate negligible s(p).
  328.                 case 1:
  329.                     f = e[p - 2];
  330.                     e[p - 2] = 0;
  331.                     for (int j = p - 2; j >= k; j--) {
  332.                         double t = JdkMath.hypot(singularValues[j], f);
  333.                         final double cs = singularValues[j] / t;
  334.                         final double sn = f / t;
  335.                         singularValues[j] = t;
  336.                         if (j != k) {
  337.                             f = -sn * e[j - 1];
  338.                             e[j - 1] = cs * e[j - 1];
  339.                         }

  341.                         for (int i = 0; i < n; i++) {
  342.                             t = cs * V[i][j] + sn * V[i][p - 1];
  343.                             V[i][p - 1] = -sn * V[i][j] + cs * V[i][p - 1];
  344.                             V[i][j] = t;
  345.                         }
  346.                     }
  347.                     break;
  348.                 // Split at negligible s(k).
  349.                 case 2:
  350.                     f = e[k - 1];
  351.                     e[k - 1] = 0;
  352.                     for (int j = k; j < p; j++) {
  353.                         double t = JdkMath.hypot(singularValues[j], f);
  354.                         final double cs = singularValues[j] / t;
  355.                         final double sn = f / t;
  356.                         singularValues[j] = t;
  357.                         f = -sn * e[j];
  358.                         e[j] = cs * e[j];

  360.                         for (int i = 0; i < m; i++) {
  361.                             t = cs * U[i][j] + sn * U[i][k - 1];
  362.                             U[i][k - 1] = -sn * U[i][j] + cs * U[i][k - 1];
  363.                             U[i][j] = t;
  364.                         }
  365.                     }
  366.                     break;
  367.                 // Perform one qr step.
  368.                 case 3:
  369.                     // Calculate the shift.
  370.                     final double maxPm1Pm2 = JdkMath.max(JdkMath.abs(singularValues[p - 1]),
  371.                                                           JdkMath.abs(singularValues[p - 2]));
  372.                     final double scale = JdkMath.max(JdkMath.max(JdkMath.max(maxPm1Pm2,
  373.                                                                                 JdkMath.abs(e[p - 2])),
  374.                                                                    JdkMath.abs(singularValues[k])),
  375.                                                       JdkMath.abs(e[k]));
  376.                     final double sp = singularValues[p - 1] / scale;
  377.                     final double spm1 = singularValues[p - 2] / scale;
  378.                     final double epm1 = e[p - 2] / scale;
  379.                     final double sk = singularValues[k] / scale;
  380.                     final double ek = e[k] / scale;
  381.                     final double b = ((spm1 + sp) * (spm1 - sp) + epm1 * epm1) / 2.0;
  382.                     final double c = (sp * epm1) * (sp * epm1);
  383.                     double shift = 0;
  384.                     if (b != 0 ||
  385.                         c != 0) {
  386.                         shift = JdkMath.sqrt(b * b + c);
  387.                         if (b < 0) {
  388.                             shift = -shift;
  389.                         }
  390.                         shift = c / (b + shift);
  391.                     }
  392.                     f = (sk + sp) * (sk - sp) + shift;
  393.                     double g = sk * ek;
  394.                     // Chase zeros.
  395.                     for (int j = k; j < p - 1; j++) {
  396.                         double t = JdkMath.hypot(f, g);
  397.                         double cs = f / t;
  398.                         double sn = g / t;
  399.                         if (j != k) {
  400.                             e[j - 1] = t;
  401.                         }
  402.                         f = cs * singularValues[j] + sn * e[j];
  403.                         e[j] = cs * e[j] - sn * singularValues[j];
  404.                         g = sn * singularValues[j + 1];
  405.                         singularValues[j + 1] = cs * singularValues[j + 1];

  407.                         for (int i = 0; i < n; i++) {
  408.                             t = cs * V[i][j] + sn * V[i][j + 1];
  409.                             V[i][j + 1] = -sn * V[i][j] + cs * V[i][j + 1];
  410.                             V[i][j] = t;
  411.                         }
  412.                         t = JdkMath.hypot(f, g);
  413.                         cs = f / t;
  414.                         sn = g / t;
  415.                         singularValues[j] = t;
  416.                         f = cs * e[j] + sn * singularValues[j + 1];
  417.                         singularValues[j + 1] = -sn * e[j] + cs * singularValues[j + 1];
  418.                         g = sn * e[j + 1];
  419.                         e[j + 1] = cs * e[j + 1];
  420.                         if (j < m - 1) {
  421.                             for (int i = 0; i < m; i++) {
  422.                                 t = cs * U[i][j] + sn * U[i][j + 1];
  423.                                 U[i][j + 1] = -sn * U[i][j] + cs * U[i][j + 1];
  424.                                 U[i][j] = t;
  425.                             }
  426.                         }
  427.                     }
  428.                     e[p - 2] = f;
  429.                     break;
  430.                 // Convergence.
  431.                 default:
  432.                     // Make the singular values positive.
  433.                     if (singularValues[k] <= 0) {
  434.                         singularValues[k] = singularValues[k] < 0 ? -singularValues[k] : 0;

  436.                         for (int i = 0; i <= pp; i++) {
  437.                             V[i][k] = -V[i][k];
  438.                         }
  439.                     }
  440.                     // Order the singular values.
  441.                     while (k < pp) {
  442.                         if (singularValues[k] >= singularValues[k + 1]) {
  443.                             break;
  444.                         }
  445.                         double t = singularValues[k];
  446.                         singularValues[k] = singularValues[k + 1];
  447.                         singularValues[k + 1] = t;
  448.                         if (k < n - 1) {
  449.                             for (int i = 0; i < n; i++) {
  450.                                 t = V[i][k + 1];
  451.                                 V[i][k + 1] = V[i][k];
  452.                                 V[i][k] = t;
  453.                             }
  454.                         }
  455.                         if (k < m - 1) {
  456.                             for (int i = 0; i < m; i++) {
  457.                                 t = U[i][k + 1];
  458.                                 U[i][k + 1] = U[i][k];
  459.                                 U[i][k] = t;
  460.                             }
  461.                         }
  462.                         k++;
  463.                     }
  464.                     p--;
  465.                     break;
  466.             }
  467.         }

  469.         // Set the small value tolerance used to calculate rank and pseudo-inverse
  470.         tol = JdkMath.max(m * singularValues[0] * EPS,
  471.                            JdkMath.sqrt(Precision.SAFE_MIN));

  473.         if (!transposed) {
  474.             cachedU = MatrixUtils.createRealMatrix(U);
  475.             cachedV = MatrixUtils.createRealMatrix(V);
  476.         } else {
  477.             cachedU = MatrixUtils.createRealMatrix(V);
  478.             cachedV = MatrixUtils.createRealMatrix(U);
  479.         }
  480.     }

  482.     /**
  483.      * Returns the matrix U of the decomposition.
  484.      * <p>U is an orthogonal matrix, i.e. its transpose is also its inverse.</p>
  485.      * @return the U matrix
  486.      * @see #getUT()
  487.      */
  488.     public RealMatrix getU() {
  489.         // return the cached matrix
  490.         return cachedU;
  491.     }

  493.     /**
  494.      * Returns the transpose of the matrix U of the decomposition.
  495.      * <p>U is an orthogonal matrix, i.e. its transpose is also its inverse.</p>
  496.      * @return the U matrix (or null if decomposed matrix is singular)
  497.      * @see #getU()
  498.      */
  499.     public RealMatrix getUT() {
  500.         if (cachedUt == null) {
  501.             cachedUt = getU().transpose();
  502.         }
  503.         // return the cached matrix
  504.         return cachedUt;
  505.     }

  507.     /**
  508.      * Returns the diagonal matrix &Sigma; of the decomposition.
  509.      * <p>&Sigma; is a diagonal matrix. The singular values are provided in
  510.      * non-increasing order, for compatibility with Jama.</p>
  511.      * @return the &Sigma; matrix
  512.      */
  513.     public RealMatrix getS() {
  514.         if (cachedS == null) {
  515.             // cache the matrix for subsequent calls
  516.             cachedS = MatrixUtils.createRealDiagonalMatrix(singularValues);
  517.         }
  518.         return cachedS;
  519.     }

  521.     /**
  522.      * Returns the diagonal elements of the matrix &Sigma; of the decomposition.
  523.      * <p>The singular values are provided in non-increasing order, for
  524.      * compatibility with Jama.</p>
  525.      * @return the diagonal elements of the &Sigma; matrix
  526.      */
  527.     public double[] getSingularValues() {
  528.         return singularValues.clone();
  529.     }

  531.     /**
  532.      * Returns the matrix V of the decomposition.
  533.      * <p>V is an orthogonal matrix, i.e. its transpose is also its inverse.</p>
  534.      * @return the V matrix (or null if decomposed matrix is singular)
  535.      * @see #getVT()
  536.      */
  537.     public RealMatrix getV() {
  538.         // return the cached matrix
  539.         return cachedV;
  540.     }

  542.     /**
  543.      * Returns the transpose of the matrix V of the decomposition.
  544.      * <p>V is an orthogonal matrix, i.e. its transpose is also its inverse.</p>
  545.      * @return the V matrix (or null if decomposed matrix is singular)
  546.      * @see #getV()
  547.      */
  548.     public RealMatrix getVT() {
  549.         if (cachedVt == null) {
  550.             cachedVt = getV().transpose();
  551.         }
  552.         // return the cached matrix
  553.         return cachedVt;
  554.     }

  556.     /**
  557.      * Returns the n &times; n covariance matrix.
  558.      * <p>The covariance matrix is V &times; J &times; V<sup>T</sup>
  559.      * where J is the diagonal matrix of the inverse of the squares of
  560.      * the singular values.</p>
  561.      * @param minSingularValue value below which singular values are ignored
  562.      * (a 0 or negative value implies all singular value will be used)
  563.      * @return covariance matrix
  564.      * @exception IllegalArgumentException if minSingularValue is larger than
  565.      * the largest singular value, meaning all singular values are ignored
  566.      */
  567.     public RealMatrix getCovariance(final double minSingularValue) {
  568.         // get the number of singular values to consider
  569.         final int p = singularValues.length;
  570.         int dimension = 0;
  571.         while (dimension < p &&
  572.                singularValues[dimension] >= minSingularValue) {
  573.             ++dimension;
  574.         }

  576.         if (dimension == 0) {
  577.             throw new NumberIsTooLargeException(LocalizedFormats.TOO_LARGE_CUTOFF_SINGULAR_VALUE,
  578.                                                 minSingularValue, singularValues[0], true);
  579.         }

  581.         final double[][] data = new double[dimension][p];
  582.         getVT().walkInOptimizedOrder(new DefaultRealMatrixPreservingVisitor() {
  583.             /** {@inheritDoc} */
  584.             @Override
  585.             public void visit(final int row, final int column,
  586.                     final double value) {
  587.                 data[row][column] = value / singularValues[row];
  588.             }
  589.         }, 0, dimension - 1, 0, p - 1);

  591.         RealMatrix jv = new Array2DRowRealMatrix(data, false);
  592.         return jv.transpose().multiply(jv);
  593.     }

  595.     /**
  596.      * Returns the L<sub>2</sub> norm of the matrix.
  597.      * <p>The L<sub>2</sub> norm is max(|A &times; u|<sub>2</sub> /
  598.      * |u|<sub>2</sub>), where |.|<sub>2</sub> denotes the vectorial 2-norm
  599.      * (i.e. the traditional euclidean norm).</p>
  600.      * @return norm
  601.      */
  602.     public double getNorm() {
  603.         return singularValues[0];
  604.     }

  606.     /**
  607.      * Return the condition number of the matrix.
  608.      * @return condition number of the matrix
  609.      */
  610.     public double getConditionNumber() {
  611.         return singularValues[0] / singularValues[n - 1];
  612.     }

  614.     /**
  615.      * Computes the inverse of the condition number.
  616.      * In cases of rank deficiency, the {@link #getConditionNumber() condition
  617.      * number} will become undefined.
  618.      *
  619.      * @return the inverse of the condition number.
  620.      */
  621.     public double getInverseConditionNumber() {
  622.         return singularValues[n - 1] / singularValues[0];
  623.     }

  625.     /**
  626.      * Return the effective numerical matrix rank.
  627.      * <p>The effective numerical rank is the number of non-negligible
  628.      * singular values. The threshold used to identify non-negligible
  629.      * terms is max(m,n) &times; ulp(s<sub>1</sub>) where ulp(s<sub>1</sub>)
  630.      * is the least significant bit of the largest singular value.</p>
  631.      * @return effective numerical matrix rank
  632.      */
  633.     public int getRank() {
  634.         int r = 0;
  635.         for (int i = 0; i < singularValues.length; i++) {
  636.             if (singularValues[i] > tol) {
  637.                 r++;
  638.             }
  639.         }
  640.         return r;
  641.     }

  643.     /**
  644.      * Get a solver for finding the A &times; X = B solution in least square sense.
  645.      * @return a solver
  646.      */
  647.     public DecompositionSolver getSolver() {
  648.         return new Solver(singularValues, getUT(), getV(), getRank() == m, tol);
  649.     }

  651.     /** Specialized solver. */
  652.     private static final class Solver implements DecompositionSolver {
  653.         /** Pseudo-inverse of the initial matrix. */
  654.         private final RealMatrix pseudoInverse;
  655.         /** Singularity indicator. */
  656.         private final boolean nonSingular;

  658.         /**
  659.          * Build a solver from decomposed matrix.
  660.          *
  661.          * @param singularValues Singular values.
  662.          * @param uT U<sup>T</sup> matrix of the decomposition.
  663.          * @param v V matrix of the decomposition.
  664.          * @param nonSingular Singularity indicator.
  665.          * @param tol tolerance for singular values
  666.          */
  667.         private Solver(final double[] singularValues, final RealMatrix uT,
  668.                        final RealMatrix v, final boolean nonSingular, final double tol) {
  669.             final double[][] suT = uT.getData();
  670.             for (int i = 0; i < singularValues.length; ++i) {
  671.                 final double a;
  672.                 if (singularValues[i] > tol) {
  673.                     a = 1 / singularValues[i];
  674.                 } else {
  675.                     a = 0;
  676.                 }
  677.                 final double[] suTi = suT[i];
  678.                 for (int j = 0; j < suTi.length; ++j) {
  679.                     suTi[j] *= a;
  680.                 }
  681.             }
  682.             pseudoInverse = v.multiply(new Array2DRowRealMatrix(suT, false));
  683.             this.nonSingular = nonSingular;
  684.         }

  686.         /**
  687.          * Solve the linear equation A &times; X = B in least square sense.
  688.          * <p>
  689.          * The m&times;n matrix A may not be square, the solution X is such that
  690.          * ||A &times; X - B|| is minimal.
  691.          * </p>
  692.          * @param b Right-hand side of the equation A &times; X = B
  693.          * @return a vector X that minimizes the two norm of A &times; X - B
  694.          * @throws org.apache.commons.math4.legacy.exception.DimensionMismatchException
  695.          * if the matrices dimensions do not match.
  696.          */
  697.         @Override
  698.         public RealVector solve(final RealVector b) {
  699.             return pseudoInverse.operate(b);
  700.         }

  702.         /**
  703.          * Solve the linear equation A &times; X = B in least square sense.
  704.          * <p>
  705.          * The m&times;n matrix A may not be square, the solution X is such that
  706.          * ||A &times; X - B|| is minimal.
  707.          * </p>
  708.          *
  709.          * @param b Right-hand side of the equation A &times; X = B
  710.          * @return a matrix X that minimizes the two norm of A &times; X - B
  711.          * @throws org.apache.commons.math4.legacy.exception.DimensionMismatchException
  712.          * if the matrices dimensions do not match.
  713.          */
  714.         @Override
  715.         public RealMatrix solve(final RealMatrix b) {
  716.             return pseudoInverse.multiply(b);
  717.         }

  719.         /**
  720.          * Check if the decomposed matrix is non-singular.
  721.          *
  722.          * @return {@code true} if the decomposed matrix is non-singular.
  723.          */
  724.         @Override
  725.         public boolean isNonSingular() {
  726.             return nonSingular;
  727.         }

  729.         /**
  730.          * Get the pseudo-inverse of the decomposed matrix.
  731.          *
  732.          * @return the inverse matrix.
  733.          */
  734.         @Override
  735.         public RealMatrix getInverse() {
  736.             return pseudoInverse;
  737.         }
  738.     }
  739. }
Created with JaCoCo 0.8.10.202304240956Code Coverage Report for Apache Commons Math 4.0-SNAPSHOT