Author: tn
Date: Sat Feb 8 14:13:34 2014
New Revision: 1566017
URL: http://svn.apache.org/r1566017
Log:
[MATH-1044] Clarify javadoc of DecompositionSolver#getInverse and corresponding
implementations. Thanks to Sean Owen.
Modified:
commons/proper/math/trunk/src/changes/changes.xml
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/linear/CholeskyDecomposition.java
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/linear/DecompositionSolver.java
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/linear/LUDecomposition.java
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/linear/QRDecomposition.java
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/linear/RRQRDecomposition.java
commons/proper/math/trunk/src/test/java/org/apache/commons/math3/linear/SingularValueSolverTest.java
Modified: commons/proper/math/trunk/src/changes/changes.xml
URL:
http://svn.apache.org/viewvc/commons/proper/math/trunk/src/changes/changes.xml?rev=1566017&r1=1566016&r2=1566017&view=diff
==============================================================================
--- commons/proper/math/trunk/src/changes/changes.xml (original)
+++ commons/proper/math/trunk/src/changes/changes.xml Sat Feb 8 14:13:34 2014
@@ -51,6 +51,11 @@ If the output is not quite correct, chec
</properties>
<body>
<release version="3.3" date="TBD" description="TBD">
+ <action dev="tn" type="fix" issue="MATH-1044" due-to="Sean Owen">
+ Clarify javadoc of "DecompositionSolver#getInverse()" and corresponding
implementations
+ wrt the actualy returned inverse. Several decomposition implementations
are able
+ to return a pseudo-inverse in case of a singular matrix.
+ </action>
<action dev="luc" type="add" issue="MATH-1095">
Added Emo Welzl algorithm to find the smallest enclosing ball of a
collection of points.
</action>
Modified:
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/linear/CholeskyDecomposition.java
URL:
http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/linear/CholeskyDecomposition.java?rev=1566017&r1=1566016&r2=1566017&view=diff
==============================================================================
---
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/linear/CholeskyDecomposition.java
(original)
+++
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/linear/CholeskyDecomposition.java
Sat Feb 8 14:13:34 2014
@@ -299,7 +299,11 @@ public class CholeskyDecomposition {
return new Array2DRowRealMatrix(x);
}
- /** {@inheritDoc} */
+ /**
+ * Get the inverse of the decomposed matrix.
+ *
+ * @return the inverse matrix.
+ */
public RealMatrix getInverse() {
return solve(MatrixUtils.createRealIdentityMatrix(lTData.length));
}
Modified:
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/linear/DecompositionSolver.java
URL:
http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/linear/DecompositionSolver.java?rev=1566017&r1=1566016&r2=1566017&view=diff
==============================================================================
---
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/linear/DecompositionSolver.java
(original)
+++
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/linear/DecompositionSolver.java
Sat Feb 8 14:13:34 2014
@@ -17,47 +17,51 @@
package org.apache.commons.math3.linear;
-
-
/**
* Interface handling decomposition algorithms that can solve A × X = B.
- * <p>Decomposition algorithms decompose an A matrix has a product of several
specific
+ * <p>
+ * Decomposition algorithms decompose an A matrix has a product of several
specific
* matrices from which they can solve A × X = B in least squares sense:
they find X
- * such that ||A × X - B|| is minimal.</p>
- * <p>Some solvers like {@link LUDecomposition} can only find the solution for
+ * such that ||A × X - B|| is minimal.
+ * <p>
+ * Some solvers like {@link LUDecomposition} can only find the solution for
* square matrices and when the solution is an exact linear solution, i.e. when
* ||A × X - B|| is exactly 0. Other solvers can also find solutions
* with non-square matrix A and with non-null minimal norm. If an exact linear
- * solution exists it is also the minimal norm solution.</p>
+ * solution exists it is also the minimal norm solution.
*
* @version $Id$
* @since 2.0
*/
public interface DecompositionSolver {
- /** Solve the linear equation A × X = B for matrices A.
- * <p>The A matrix is implicit, it is provided by the underlying
- * decomposition algorithm.</p>
+ /**
+ * Solve the linear equation A × X = B for matrices A.
+ * <p>
+ * The A matrix is implicit, it is provided by the underlying
+ * decomposition algorithm.
+ *
* @param b right-hand side of the equation A × X = B
* @return a vector X that minimizes the two norm of A × X - B
* @throws org.apache.commons.math3.exception.DimensionMismatchException
* if the matrices dimensions do not match.
- * @throws SingularMatrixException
- * if the decomposed matrix is singular.
+ * @throws SingularMatrixException if the decomposed matrix is singular.
*/
- RealVector solve(final RealVector b);
+ RealVector solve(final RealVector b) throws SingularMatrixException;
- /** Solve the linear equation A × X = B for matrices A.
- * <p>The A matrix is implicit, it is provided by the underlying
- * decomposition algorithm.</p>
+ /**
+ * Solve the linear equation A × X = B for matrices A.
+ * <p>
+ * The A matrix is implicit, it is provided by the underlying
+ * decomposition algorithm.
+ *
* @param b right-hand side of the equation A × X = B
* @return a matrix X that minimizes the two norm of A × X - B
* @throws org.apache.commons.math3.exception.DimensionMismatchException
* if the matrices dimensions do not match.
- * @throws SingularMatrixException
- * if the decomposed matrix is singular.
+ * @throws SingularMatrixException if the decomposed matrix is singular.
*/
- RealMatrix solve(final RealMatrix b);
+ RealMatrix solve(final RealMatrix b) throws SingularMatrixException;
/**
* Check if the decomposed matrix is non-singular.
@@ -65,10 +69,30 @@ public interface DecompositionSolver {
*/
boolean isNonSingular();
- /** Get the inverse (or pseudo-inverse) of the decomposed matrix.
- * @return inverse matrix
- * @throws SingularMatrixException
- * if the decomposed matrix is singular.
+ /**
+ * Get the <a
href="http://en.wikipedia.org/wiki/Moore%E2%80%93Penrose_pseudoinverse";>pseudo-inverse</a>
+ * of the decomposed matrix.
+ * <p>
+ * <em>This is equal to the inverse of the decomposed matrix, if such an
inverse exists.</em>
+ * <p>
+ * If no such inverse exists, then the result has properties that resemble
that of an inverse.
+ * <p>
+ * In particular, in this case, if the decomposed matrix is A, then the
system of equations
+ * \( A x = b \) may have no solutions, or many. If it has no solutions,
then the pseudo-inverse
+ * \( A^+ \) gives the "closest" solution \( z = A^+ b \), meaning \(
\left \| A z - b \right \|_2 \)
+ * is minimized. If there are many solutions, then \( z = A^+ b \) is the
smallest solution,
+ * meaning \( \left \| z \right \|_2 \) is minimized.
+ * <p>
+ * Note however that some decompositions cannot compute a pseudo-inverse
for all matrices.
+ * For example, the {@link LUDecomposition} is not defined for non-square
matrices to begin
+ * with. The {@link QRDecomposition} can operate on non-square matrices,
but will throw
+ * {@link SingularMatrixException} if the decomposed matrix is singular.
Refer to the javadoc
+ * of specific decomposition implementations for more details.
+ *
+ * @return pseudo-inverse matrix (which is the inverse, if it exists),
+ * if the decomposition can pseudo-invert the decomposed matrix
+ * @throws SingularMatrixException if the decomposed matrix is singular
and the decomposition
+ * can not compute a pseudo-inverse
*/
- RealMatrix getInverse();
+ RealMatrix getInverse() throws SingularMatrixException;
}
Modified:
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/linear/LUDecomposition.java
URL:
http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/linear/LUDecomposition.java?rev=1566017&r1=1566016&r2=1566017&view=diff
==============================================================================
---
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/linear/LUDecomposition.java
(original)
+++
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/linear/LUDecomposition.java
Sat Feb 8 14:13:34 2014
@@ -378,7 +378,12 @@ public class LUDecomposition {
return new Array2DRowRealMatrix(bp, false);
}
- /** {@inheritDoc} */
+ /**
+ * Get the inverse of the decomposed matrix.
+ *
+ * @return the inverse matrix.
+ * @throws SingularMatrixException if the decomposed matrix is
singular.
+ */
public RealMatrix getInverse() {
return solve(MatrixUtils.createRealIdentityMatrix(pivot.length));
}
Modified:
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/linear/QRDecomposition.java
URL:
http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/linear/QRDecomposition.java?rev=1566017&r1=1566016&r2=1566017&view=diff
==============================================================================
---
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/linear/QRDecomposition.java
(original)
+++
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/linear/QRDecomposition.java
Sat Feb 8 14:13:34 2014
@@ -458,7 +458,10 @@ public class QRDecomposition {
return new BlockRealMatrix(n, columns, xBlocks, false);
}
- /** {@inheritDoc} */
+ /**
+ * {@inheritDoc}
+ * @throws SingularMatrixException if the decomposed matrix is
singular.
+ */
public RealMatrix getInverse() {
return solve(MatrixUtils.createRealIdentityMatrix(rDiag.length));
}
Modified:
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/linear/RRQRDecomposition.java
URL:
http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/linear/RRQRDecomposition.java?rev=1566017&r1=1566016&r2=1566017&view=diff
==============================================================================
---
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/linear/RRQRDecomposition.java
(original)
+++
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/linear/RRQRDecomposition.java
Sat Feb 8 14:13:34 2014
@@ -226,7 +226,10 @@ public class RRQRDecomposition extends Q
return p.multiply(upper.solve(b));
}
- /** {@inheritDoc} */
+ /**
+ * {@inheritDoc}
+ * @throws SingularMatrixException if the decomposed matrix is
singular.
+ */
public RealMatrix getInverse() {
return
solve(MatrixUtils.createRealIdentityMatrix(p.getRowDimension()));
}
Modified:
commons/proper/math/trunk/src/test/java/org/apache/commons/math3/linear/SingularValueSolverTest.java
URL:
http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/java/org/apache/commons/math3/linear/SingularValueSolverTest.java?rev=1566017&r1=1566016&r2=1566017&view=diff
==============================================================================
---
commons/proper/math/trunk/src/test/java/org/apache/commons/math3/linear/SingularValueSolverTest.java
(original)
+++
commons/proper/math/trunk/src/test/java/org/apache/commons/math3/linear/SingularValueSolverTest.java
Sat Feb 8 14:13:34 2014
@@ -28,6 +28,12 @@ public class SingularValueSolverTest {
{ 24.0 / 25.0, 43.0 / 25.0 },
{ 57.0 / 25.0, 24.0 / 25.0 }
};
+ private double[][] bigSingular = {
+ { 1.0, 2.0, 3.0, 4.0 },
+ { 2.0, 5.0, 3.0, 4.0 },
+ { 7.0, 3.0, 256.0, 1930.0 },
+ { 3.0, 7.0, 6.0, 8.0 }
+ }; // 4th row = 1st + 2nd
private static final double normTolerance = 10e-14;
@@ -136,4 +142,18 @@ public class SingularValueSolverTest {
Assert.assertEquals(0.0, recomposed.subtract(rm).getNorm(), 2.0e-15);
}
+ @Test
+ public void testSingular() {
+ SingularValueDecomposition svd =
+ new
SingularValueDecomposition(MatrixUtils.createRealMatrix(bigSingular));
+ RealMatrix pseudoInverse = svd.getSolver().getInverse();
+ RealMatrix expected = new Array2DRowRealMatrix(new double[][] {
+ {-0.0355022687,0.0512742236,-0.0001045523,0.0157719549},
+ {-0.3214992438,0.3162419255,0.0000348508,-0.0052573183},
+ {0.5437098346,-0.4107754586,-0.0008256918,0.132934376},
+ {-0.0714905202,0.053808742,0.0006279816,-0.0176817782}
+ });
+ Assert.assertEquals(0, expected.subtract(pseudoInverse).getNorm(),
1.0e-9);
+ }
+
}
