001 /*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements. See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License. You may obtain a copy of the License at
008 *
009 * http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017
018 package org.apache.commons.math.linear;
019
020 import java.util.Random;
021
022 import org.apache.commons.math.linear.MatrixUtils;
023 import org.apache.commons.math.linear.RealMatrix;
024 import org.apache.commons.math.linear.SingularValueDecomposition;
025 import org.apache.commons.math.linear.SingularValueDecompositionImpl;
026
027 import junit.framework.Test;
028 import junit.framework.TestCase;
029 import junit.framework.TestSuite;
030
031 public class SingularValueDecompositionImplTest extends TestCase {
032
033 private double[][] testSquare = {
034 { 24.0 / 25.0, 43.0 / 25.0 },
035 { 57.0 / 25.0, 24.0 / 25.0 }
036 };
037
038 private double[][] testNonSquare = {
039 { -540.0 / 625.0, 963.0 / 625.0, -216.0 / 625.0 },
040 { -1730.0 / 625.0, -744.0 / 625.0, 1008.0 / 625.0 },
041 { -720.0 / 625.0, 1284.0 / 625.0, -288.0 / 625.0 },
042 { -360.0 / 625.0, 192.0 / 625.0, 1756.0 / 625.0 },
043 };
044
045 private static final double normTolerance = 10e-14;
046
047 public SingularValueDecompositionImplTest(String name) {
048 super(name);
049 }
050
051 public static Test suite() {
052 TestSuite suite = new TestSuite(SingularValueDecompositionImplTest.class);
053 suite.setName("SingularValueDecompositionImpl Tests");
054 return suite;
055 }
056
057 public void testMoreRows() {
058 final double[] singularValues = { 123.456, 2.3, 1.001, 0.999 };
059 final int rows = singularValues.length + 2;
060 final int columns = singularValues.length;
061 Random r = new Random(15338437322523l);
062 SingularValueDecomposition svd =
063 new SingularValueDecompositionImpl(createTestMatrix(r, rows, columns, singularValues));
064 double[] computedSV = svd.getSingularValues();
065 assertEquals(singularValues.length, computedSV.length);
066 for (int i = 0; i < singularValues.length; ++i) {
067 assertEquals(singularValues[i], computedSV[i], 1.0e-10);
068 }
069 }
070
071 public void testMoreColumns() {
072 final double[] singularValues = { 123.456, 2.3, 1.001, 0.999 };
073 final int rows = singularValues.length;
074 final int columns = singularValues.length + 2;
075 Random r = new Random(732763225836210l);
076 SingularValueDecomposition svd =
077 new SingularValueDecompositionImpl(createTestMatrix(r, rows, columns, singularValues));
078 double[] computedSV = svd.getSingularValues();
079 assertEquals(singularValues.length, computedSV.length);
080 for (int i = 0; i < singularValues.length; ++i) {
081 assertEquals(singularValues[i], computedSV[i], 1.0e-10);
082 }
083 }
084
085 /** test dimensions */
086 public void testDimensions() {
087 RealMatrix matrix = MatrixUtils.createRealMatrix(testSquare);
088 final int m = matrix.getRowDimension();
089 final int n = matrix.getColumnDimension();
090 SingularValueDecomposition svd = new SingularValueDecompositionImpl(matrix);
091 assertEquals(m, svd.getU().getRowDimension());
092 assertEquals(m, svd.getU().getColumnDimension());
093 assertEquals(m, svd.getS().getColumnDimension());
094 assertEquals(n, svd.getS().getColumnDimension());
095 assertEquals(n, svd.getV().getRowDimension());
096 assertEquals(n, svd.getV().getColumnDimension());
097
098 }
099
100 /** Test based on a dimension 4 Hadamard matrix. */
101 public void testHadamard() {
102 RealMatrix matrix = new Array2DRowRealMatrix(new double[][] {
103 {15.0 / 2.0, 5.0 / 2.0, 9.0 / 2.0, 3.0 / 2.0 },
104 { 5.0 / 2.0, 15.0 / 2.0, 3.0 / 2.0, 9.0 / 2.0 },
105 { 9.0 / 2.0, 3.0 / 2.0, 15.0 / 2.0, 5.0 / 2.0 },
106 { 3.0 / 2.0, 9.0 / 2.0, 5.0 / 2.0, 15.0 / 2.0 }
107 }, false);
108 SingularValueDecomposition svd = new SingularValueDecompositionImpl(matrix);
109 assertEquals(16.0, svd.getSingularValues()[0], 1.0e-14);
110 assertEquals( 8.0, svd.getSingularValues()[1], 1.0e-14);
111 assertEquals( 4.0, svd.getSingularValues()[2], 1.0e-14);
112 assertEquals( 2.0, svd.getSingularValues()[3], 1.0e-14);
113
114 RealMatrix fullCovariance = new Array2DRowRealMatrix(new double[][] {
115 { 85.0 / 1024, -51.0 / 1024, -75.0 / 1024, 45.0 / 1024 },
116 { -51.0 / 1024, 85.0 / 1024, 45.0 / 1024, -75.0 / 1024 },
117 { -75.0 / 1024, 45.0 / 1024, 85.0 / 1024, -51.0 / 1024 },
118 { 45.0 / 1024, -75.0 / 1024, -51.0 / 1024, 85.0 / 1024 }
119 }, false);
120 assertEquals(0.0,
121 fullCovariance.subtract(svd.getCovariance(0.0)).getNorm(),
122 1.0e-14);
123
124 RealMatrix halfCovariance = new Array2DRowRealMatrix(new double[][] {
125 { 5.0 / 1024, -3.0 / 1024, 5.0 / 1024, -3.0 / 1024 },
126 { -3.0 / 1024, 5.0 / 1024, -3.0 / 1024, 5.0 / 1024 },
127 { 5.0 / 1024, -3.0 / 1024, 5.0 / 1024, -3.0 / 1024 },
128 { -3.0 / 1024, 5.0 / 1024, -3.0 / 1024, 5.0 / 1024 }
129 }, false);
130 assertEquals(0.0,
131 halfCovariance.subtract(svd.getCovariance(6.0)).getNorm(),
132 1.0e-14);
133
134 }
135
136 /** test A = USVt */
137 public void testAEqualUSVt() {
138 checkAEqualUSVt(MatrixUtils.createRealMatrix(testSquare));
139 checkAEqualUSVt(MatrixUtils.createRealMatrix(testNonSquare));
140 checkAEqualUSVt(MatrixUtils.createRealMatrix(testNonSquare).transpose());
141 }
142
143 public void checkAEqualUSVt(final RealMatrix matrix) {
144 SingularValueDecomposition svd = new SingularValueDecompositionImpl(matrix);
145 RealMatrix u = svd.getU();
146 RealMatrix s = svd.getS();
147 RealMatrix v = svd.getV();
148 double norm = u.multiply(s).multiply(v.transpose()).subtract(matrix).getNorm();
149 assertEquals(0, norm, normTolerance);
150
151 }
152
153 /** test that U is orthogonal */
154 public void testUOrthogonal() {
155 checkOrthogonal(new SingularValueDecompositionImpl(MatrixUtils.createRealMatrix(testSquare)).getU());
156 checkOrthogonal(new SingularValueDecompositionImpl(MatrixUtils.createRealMatrix(testNonSquare)).getU());
157 checkOrthogonal(new SingularValueDecompositionImpl(MatrixUtils.createRealMatrix(testNonSquare).transpose()).getU());
158 }
159
160 /** test that V is orthogonal */
161 public void testVOrthogonal() {
162 checkOrthogonal(new SingularValueDecompositionImpl(MatrixUtils.createRealMatrix(testSquare)).getV());
163 checkOrthogonal(new SingularValueDecompositionImpl(MatrixUtils.createRealMatrix(testNonSquare)).getV());
164 checkOrthogonal(new SingularValueDecompositionImpl(MatrixUtils.createRealMatrix(testNonSquare).transpose()).getV());
165 }
166
167 public void checkOrthogonal(final RealMatrix m) {
168 RealMatrix mTm = m.transpose().multiply(m);
169 RealMatrix id = MatrixUtils.createRealIdentityMatrix(mTm.getRowDimension());
170 assertEquals(0, mTm.subtract(id).getNorm(), normTolerance);
171 }
172
173 /** test matrices values */
174 public void testMatricesValues1() {
175 SingularValueDecomposition svd =
176 new SingularValueDecompositionImpl(MatrixUtils.createRealMatrix(testSquare));
177 RealMatrix uRef = MatrixUtils.createRealMatrix(new double[][] {
178 { 3.0 / 5.0, -4.0 / 5.0 },
179 { 4.0 / 5.0, 3.0 / 5.0 }
180 });
181 RealMatrix sRef = MatrixUtils.createRealMatrix(new double[][] {
182 { 3.0, 0.0 },
183 { 0.0, 1.0 }
184 });
185 RealMatrix vRef = MatrixUtils.createRealMatrix(new double[][] {
186 { 4.0 / 5.0, 3.0 / 5.0 },
187 { 3.0 / 5.0, -4.0 / 5.0 }
188 });
189
190 // check values against known references
191 RealMatrix u = svd.getU();
192 assertEquals(0, u.subtract(uRef).getNorm(), normTolerance);
193 RealMatrix s = svd.getS();
194 assertEquals(0, s.subtract(sRef).getNorm(), normTolerance);
195 RealMatrix v = svd.getV();
196 assertEquals(0, v.subtract(vRef).getNorm(), normTolerance);
197
198 // check the same cached instance is returned the second time
199 assertTrue(u == svd.getU());
200 assertTrue(s == svd.getS());
201 assertTrue(v == svd.getV());
202
203 }
204
205 /** test matrices values */
206 public void testMatricesValues2() {
207
208 RealMatrix uRef = MatrixUtils.createRealMatrix(new double[][] {
209 { 0.0 / 5.0, 3.0 / 5.0, 0.0 / 5.0 },
210 { -4.0 / 5.0, 0.0 / 5.0, -3.0 / 5.0 },
211 { 0.0 / 5.0, 4.0 / 5.0, 0.0 / 5.0 },
212 { -3.0 / 5.0, 0.0 / 5.0, 4.0 / 5.0 }
213 });
214 RealMatrix sRef = MatrixUtils.createRealMatrix(new double[][] {
215 { 4.0, 0.0, 0.0 },
216 { 0.0, 3.0, 0.0 },
217 { 0.0, 0.0, 2.0 }
218 });
219 RealMatrix vRef = MatrixUtils.createRealMatrix(new double[][] {
220 { 80.0 / 125.0, -60.0 / 125.0, 75.0 / 125.0 },
221 { 24.0 / 125.0, 107.0 / 125.0, 60.0 / 125.0 },
222 { -93.0 / 125.0, -24.0 / 125.0, 80.0 / 125.0 }
223 });
224
225 // check values against known references
226 SingularValueDecomposition svd =
227 new SingularValueDecompositionImpl(MatrixUtils.createRealMatrix(testNonSquare));
228 RealMatrix u = svd.getU();
229 assertEquals(0, u.subtract(uRef).getNorm(), normTolerance);
230 RealMatrix s = svd.getS();
231 assertEquals(0, s.subtract(sRef).getNorm(), normTolerance);
232 RealMatrix v = svd.getV();
233 assertEquals(0, v.subtract(vRef).getNorm(), normTolerance);
234
235 // check the same cached instance is returned the second time
236 assertTrue(u == svd.getU());
237 assertTrue(s == svd.getS());
238 assertTrue(v == svd.getV());
239
240 }
241
242 /** test condition number */
243 public void testConditionNumber() {
244 SingularValueDecompositionImpl svd =
245 new SingularValueDecompositionImpl(MatrixUtils.createRealMatrix(testSquare));
246 assertEquals(3.0, svd.getConditionNumber(), 1.0e-15);
247 }
248
249 private RealMatrix createTestMatrix(final Random r, final int rows, final int columns,
250 final double[] singularValues) {
251 final RealMatrix u =
252 EigenDecompositionImplTest.createOrthogonalMatrix(r, rows);
253 final RealMatrix d =
254 EigenDecompositionImplTest.createDiagonalMatrix(singularValues, rows, columns);
255 final RealMatrix v =
256 EigenDecompositionImplTest.createOrthogonalMatrix(r, columns);
257 return u.multiply(d).multiply(v);
258 }
259
260 }