Uploaded image for project: 'Commons Math'
  1. Commons Math
  2. MATH-1101

QR and Rank-revealing QR fail to find a least-squares solution

    Details

    • Type: Bug
    • Status: Closed
    • Priority: Major
    • Resolution: Fixed
    • Affects Version/s: 3.2
    • Fix Version/s: 3.3
    • Labels:

      Description

      QR and RRQR (rank-revealing) algorithms fail to find a least-squares solution in some cases.

      The following code:

      final RealMatrix A = new BlockRealMatrix(3, 3);
      A.setEntry(0, 0, 1);
      A.setEntry(0, 1, 6);
      A.setEntry(0, 2, 4);
      A.setEntry(1, 0, 2);
      A.setEntry(1, 1, 4);
      A.setEntry(1, 2, -1);
      A.setEntry(2, 0, -1);
      A.setEntry(2, 1, 2);
      A.setEntry(2, 2, 5);
      final RealVector b = new ArrayRealVector(new double[]

      {5, 6, 1}

      );
      final QRDecomposition qrDecomposition = new QRDecomposition(A);
      final RRQRDecomposition rrqrDecomposition = new RRQRDecomposition(A);
      final SingularValueDecomposition svd = new SingularValueDecomposition(A);
      final RealVector xQR = qrDecomposition.getSolver().solve(b);
      System.out.printf("QR solution: %s\n", xQR.toString());
      final RealVector xRRQR = rrqrDecomposition.getSolver().solve(b);
      System.out.printf("RRSQ solution: %s\n", xRRQR.toString());
      final RealVector xSVD = svd.getSolver().solve(b);
      System.out.printf("SVD solution: %s\n", xSVD.toString());

      produces

      QR solution: {-3,575,212,378,628,897; 1,462,586,882,166,368; -1,300,077,228,592,326.5}
      RRSQ solution:

      {5,200,308,914,369,308; -2,127,399,101,332,898; 1,891,021,423,407,021}

      SVD solution:

      {0.5050344462; 1.0206677266; -0.2405935347}

      Showing that QR and RRQR algorithms fail to find the least-squares solution. This can also be verified by calculating the dot product between columns of A and A*x - b:

      // x = xQR, xRRQR or xSVD
      final RealVector r = A.operate.subtract(b);
      for (int i = 0; i < x.getDimension(); ++i)

      { final RealVector columnVector = A.getColumnVector(i); assertEquals(name, 0.0, r.dotProduct(columnVector), tolerance); }

      Only SVD method passes this test with decent tolerance (1E-14 or so).

        Attachments

        1. math-1101-bug.java
          2 kB
          Roman Werpachowski

          Activity

            People

            • Assignee:
              Unassigned
              Reporter:
              roman.werpachowski Roman Werpachowski
            • Votes:
              0 Vote for this issue
              Watchers:
              2 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved: