[Fwd: SVD woe revisited (LINPACK derived possible remedy)]
- Subject: [Fwd: SVD woe revisited (LINPACK derived possible remedy)]
- From: Ron Boisvert <boisvert@nist.gov>
- Date: Wed, 12 Dec 2007 09:42:23 -0500
- Content-Type: multipart/mixed; boundary="------------000400070308060302010906"
- User-Agent: Thunderbird 2.0.0.9 (Windows/20071031)
-------- Original Message --------
Subject: SVD woe revisited (LINPACK derived possible remedy)
Date: Tue, 11 Dec 2007 23:48:50 -0500
From: Andreas Kyrmegalos <andreask1@vivodinet.gr>
Reply-To: andreask1@vivodinet.gr
To: boisvert@nist.gov
Hey there,
my name's Andreas and have been using JAMA for a few years now. It
offers very efficient implementations of matrix algorithms.
However the whole m>=n restriction in SVD has always bugged me. So, I
compiled the relative LINPACK code (dsvdc.f plus other necessary files)
and run a single test of this matrix:
1 1 1 1
1 2 3 4
1 3 6 10
It's the same matrix as the one in
http://www.egwald.com/linearalgebra/matrices.php
The LINPACK compiled code agrees with the result in the aforementioned
page(likely because it uses LINPACK).
However because of the known restriction in JAMA, its SVD implementation
doesn't offer the same result.
After some debugging I noticed this:
JAMA CODE
..
int nu = Math.min(m,n);
..
// If required, generate V.
if (wantv) {
for (int k = n-1; k >= 0; k--) {
if ((k < nrt) & (e[k] != 0.0)) {
---> for (int j = k+1; j < nu; j++) {
double t = 0;
for (int i = k+1; i < n; i++) {
t += V[i][k]*V[i][j];
}
t = -t/V[k+1][k];
for (int i = k+1; i < n; i++) {
V[i][j] += t*V[i][k];
}
}
}
for (int i = 0; i < n; i++) {
V[i][k] = 0.0;
}
V[k][k] = 1.0;
}
}
LINPACK CODE
here m -> n, n -> p
c
c if it is required, generate v.
c
if (.not.wantv) go to 350
do 340 ll = 1, p
l = p - ll + 1
lp1 = l + 1
if (l .gt. nrt) go to 320
if (e(l) .eq. 0.0d0) go to 320
---> do 310 j = lp1, p
t = -ddot(p-l,v(lp1,l),1,v(lp1,j),1)/v(lp1,l)
call daxpy(p-l,t,v(lp1,l),1,v(lp1,j),1)
310 continue
320 continue
do 330 i = 1, p
v(i,l) = 0.0d0
330 continue
v(l,l) = 1.0d0
340 continue
350 continue
The lines denoted with ---> point to a difference between the JAMA and
LINPACK code, the former an almost 1:1 port of the latter.
If the JAMA code :
for (int j = k+1; j < nu; j++) {
is replaced by :
for (int j = k+1; j < n; j++) {
the results match. I have not tried it with other data but I'm
relatively confident that the JAMA results shouldn't differ anymore.
Typical results for the m>n case don't seem to be affected.
The use of nu instead of n is obviously connected to the generation of a
thin U matrix. Unfortunately, it's use in this part of code results in
improper output.
Using LINPACK code I have updated SingularValueDecomposition.java. It
now outputs correct results regardless of the matrix dimesions' ratio
and offers the option to determine the column-size of the matrix U. The
source to this file is included.
Best Regards,
Andreas
package Jama;
import Jama.util.*;
/** Singular Value Decomposition.
<P>
For an m-by-n matrix A, the singular value decomposition is
an m-by-(m or n) orthogonal matrix U, a (m or n)-by-n diagonal matrix S, and
an n-by-n orthogonal matrix V so that A = U*S*V'.
<P>
The singular values, sigma[k] = S[k][k], are ordered so that
sigma[0] >= sigma[1] >= ... >= sigma[n-1].
<P>
The singular value decompostion always exists, so the constructor will
never fail. The matrix condition number and the effective numerical
rank can be computed from this decomposition.
*/
public class SingularValueDecomposition implements java.io.Serializable {
/* ------------------------
Class variables
* ------------------------ */
/** Arrays for internal storage of U and V.
@serial internal storage of U.
@serial internal storage of V.
*/
private double[][] U, V;
/** Array for internal storage of singular values.
@serial internal storage of singular values.
*/
private double[] s;
/** Row and column dimensions.
@serial row dimension.
@serial column dimension.
@serial U column dimension.
*/
private int m, n, ncu;
/* ------------------------
Constructor
* ------------------------ */
/** Construct the singular value decomposition
@param A Rectangular matrix
@return Structure to access U, S and V.
*/
public SingularValueDecomposition (Matrix Arg, boolean thin, boolean wantu,
boolean wantv) {
// Derived from LINPACK code.
// Initialize.
double[][] A = Arg.getArrayCopy();
m = Arg.getRowDimension();
n = Arg.getColumnDimension();
ncu = thin?Math.min(m,n):m;
s = new double [Math.min(m+1,n)];
if (wantu) U = new double [m][ncu];
if (wantv) V = new double [n][n];
double[] e = new double [n];
double[] work = new double [m];
// Reduce A to bidiagonal form, storing the diagonal elements
// in s and the super-diagonal elements in e.
int nct = Math.min(m-1,n);
int nrt = Math.max(0,Math.min(n-2,m));
int lu = Math.max(nct,nrt);
for (int k = 0; k < lu; k++) {
if (k < nct) {
// Compute the transformation for the k-th column and
// place the k-th diagonal in s[k].
// Compute 2-norm of k-th column without under/overflow.
s[k] = 0;
for (int i = k; i < m; i++) {
s[k] = Maths.hypot(s[k],A[i][k]);
}
if (s[k] != 0.0) {
if (A[k][k] < 0.0) {
s[k] = -s[k];
}
for (int i = k; i < m; i++) {
A[i][k] /= s[k];
}
A[k][k] += 1.0;
}
s[k] = -s[k];
}
for (int j = k+1; j < n; j++) {
if ((k < nct) & (s[k] != 0.0)) {
// Apply the transformation.
double t = 0;
for (int i = k; i < m; i++) {
t += A[i][k]*A[i][j];
}
t = -t/A[k][k];
for (int i = k; i < m; i++) {
A[i][j] += t*A[i][k];
}
}
// Place the k-th row of A into e for the
// subsequent calculation of the row transformation.
e[j] = A[k][j];
}
if (wantu & (k < nct)) {
// Place the transformation in U for subsequent back
// multiplication.
for (int i = k; i < m; i++) {
U[i][k] = A[i][k];
}
}
if (k < nrt) {
// Compute the k-th row transformation and place the
// k-th super-diagonal in e[k].
// Compute 2-norm without under/overflow.
e[k] = 0;
for (int i = k+1; i < n; i++) {
e[k] = Maths.hypot(e[k],e[i]);
}
if (e[k] != 0.0) {
if (e[k+1] < 0.0) {
e[k] = -e[k];
}
for (int i = k+1; i < n; i++) {
e[i] /= e[k];
}
e[k+1] += 1.0;
}
e[k] = -e[k];
if ((k+1 < m) & (e[k] != 0.0)) {
// Apply the transformation.
for (int i = k+1; i < m; i++) {
work[i] = 0.0;
}
for (int j = k+1; j < n; j++) {
for (int i = k+1; i < m; i++) {
work[i] += e[j]*A[i][j];
}
}
for (int j = k+1; j < n; j++) {
double t = -e[j]/e[k+1];
for (int i = k+1; i < m; i++) {
A[i][j] += t*work[i];
}
}
}
if (wantv) {
// Place the transformation in V for subsequent
// back multiplication.
for (int i = k+1; i < n; i++) {
V[i][k] = e[i];
}
}
}
}
// Set up the final bidiagonal matrix or order p.
int p = Math.min(n,m+1);
if (nct < n) {
s[nct] = A[nct][nct];
}
if (m < p) {
s[p-1] = 0.0;
}
if (nrt+1 < p) {
e[nrt] = A[nrt][p-1];
}
e[p-1] = 0.0;
// If required, generate U.
if (wantu) {
for (int j = nct; j < ncu; j++) {
for (int i = 0; i < m; i++) {
U[i][j] = 0.0;
}
U[j][j] = 1.0;
}
for (int k = nct-1; k >= 0; k--) {
if (s[k] != 0.0) {
for (int j = k+1; j < ncu; j++) {
double t = 0;
for (int i = k; i < m; i++) {
t += U[i][k]*U[i][j];
}
t = -t/U[k][k];
for (int i = k; i < m; i++) {
U[i][j] += t*U[i][k];
}
}
for (int i = k; i < m; i++ ) {
U[i][k] = -U[i][k];
}
U[k][k] += 1.0;
for (int i = 0; i < k-1; i++) {
U[i][k] = 0.0;
}
} else {
for (int i = 0; i < m; i++) {
U[i][k] = 0.0;
}
U[k][k] = 1.0;
}
}
}
// If required, generate V.
if (wantv) {
for (int k = n-1; k >= 0; k--) {
if ((k < nrt) & (e[k] != 0.0)) {
for (int j = k+1; j < n; j++) {
double t = 0;
for (int i = k+1; i < n; i++) {
t += V[i][k]*V[i][j];
}
t = -t/V[k+1][k];
for (int i = k+1; i < n; i++) {
V[i][j] += t*V[i][k];
}
}
}
for (int i = 0; i < n; i++) {
V[i][k] = 0.0;
}
V[k][k] = 1.0;
}
}
// Main iteration loop for the singular values.
int pp = p-1;
int iter = 0;
double eps = Math.pow(2.0,-52.0);
double tiny = Math.pow(2.0,-966.0);
while (p > 0) {
int k,kase;
// Here is where a test for too many iterations would go.
// This section of the program inspects for
// negligible elements in the s and e arrays. On
// completion the variables kase and k are set as follows.
// kase = 1 if s(p) and e[k-1] are negligible and k<p
// kase = 2 if s(k) is negligible and k<p
// kase = 3 if e[k-1] is negligible, k<p, and
// s(k), ..., s(p) are not negligible (qr step).
// kase = 4 if e(p-1) is negligible (convergence).
for (k = p-2; k >= -1; k--) {
if (k == -1) {
break;
}
if (Math.abs(e[k]) <=
tiny + eps*(Math.abs(s[k]) + Math.abs(s[k+1]))) {
e[k] = 0.0;
break;
}
}
if (k == p-2) {
kase = 4;
} else {
int ks;
for (ks = p-1; ks >= k; ks--) {
if (ks == k) {
break;
}
double t = (ks != p ? Math.abs(e[ks]) : 0.) +
(ks != k+1 ? Math.abs(e[ks-1]) : 0.);
if (Math.abs(s[ks]) <= tiny + eps*t) {
s[ks] = 0.0;
break;
}
}
if (ks == k) {
kase = 3;
} else if (ks == p-1) {
kase = 1;
} else {
kase = 2;
k = ks;
}
}
k++;
// Perform the task indicated by kase.
switch (kase) {
// Deflate negligible s(p).
case 1: {
double f = e[p-2];
e[p-2] = 0.0;
for (int j = p-2; j >= k; j--) {
double t = Maths.hypot(s[j],f);
double cs = s[j]/t;
double sn = f/t;
s[j] = t;
if (j != k) {
f = -sn*e[j-1];
e[j-1] = cs*e[j-1];
}
if (wantv) {
for (int i = 0; i < n; i++) {
t = cs*V[i][j] + sn*V[i][p-1];
V[i][p-1] = -sn*V[i][j] + cs*V[i][p-1];
V[i][j] = t;
}
}
}
}
break;
// Split at negligible s(k).
case 2: {
double f = e[k-1];
e[k-1] = 0.0;
for (int j = k; j < p; j++) {
double t = Maths.hypot(s[j],f);
double cs = s[j]/t;
double sn = f/t;
s[j] = t;
f = -sn*e[j];
e[j] = cs*e[j];
if (wantu) {
for (int i = 0; i < m; i++) {
t = cs*U[i][j] + sn*U[i][k-1];
U[i][k-1] = -sn*U[i][j] + cs*U[i][k-1];
U[i][j] = t;
}
}
}
}
break;
// Perform one qr step.
case 3: {
// Calculate the shift.
double scale = Math.max(Math.max(Math.max(Math.max(
Math.abs(s[p-1]),Math.abs(s[p-2])),Math.abs(e[p-2])),
Math.abs(s[k])),Math.abs(e[k]));
double sp = s[p-1]/scale;
double spm1 = s[p-2]/scale;
double epm1 = e[p-2]/scale;
double sk = s[k]/scale;
double ek = e[k]/scale;
double b = ((spm1 + sp)*(spm1 - sp) + epm1*epm1)/2.0;
double c = (sp*epm1)*(sp*epm1);
double shift = 0.0;
if ((b != 0.0) | (c != 0.0)) {
shift = Math.sqrt(b*b + c);
if (b < 0.0) {
shift = -shift;
}
shift = c/(b + shift);
}
double f = (sk + sp)*(sk - sp) + shift;
double g = sk*ek;
// Chase zeros.
for (int j = k; j < p-1; j++) {
double t = Maths.hypot(f,g);
double cs = f/t;
double sn = g/t;
if (j != k) {
e[j-1] = t;
}
f = cs*s[j] + sn*e[j];
e[j] = cs*e[j] - sn*s[j];
g = sn*s[j+1];
s[j+1] = cs*s[j+1];
if (wantv) {
for (int i = 0; i < n; i++) {
t = cs*V[i][j] + sn*V[i][j+1];
V[i][j+1] = -sn*V[i][j] + cs*V[i][j+1];
V[i][j] = t;
}
}
t = Maths.hypot(f,g);
cs = f/t;
sn = g/t;
s[j] = t;
f = cs*e[j] + sn*s[j+1];
s[j+1] = -sn*e[j] + cs*s[j+1];
g = sn*e[j+1];
e[j+1] = cs*e[j+1];
if (wantu && (j < m-1)) {
for (int i = 0; i < m; i++) {
t = cs*U[i][j] + sn*U[i][j+1];
U[i][j+1] = -sn*U[i][j] + cs*U[i][j+1];
U[i][j] = t;
}
}
}
e[p-2] = f;
iter++;
}
break;
// Convergence.
case 4: {
// Make the singular values positive.
if (s[k] <= 0.0) {
s[k] = (s[k] < 0.0 ? -s[k] : 0.0);
if (wantv) {
for (int i = 0; i < n; i++) {
V[i][k] = -V[i][k];
}
}
}
// Order the singular values.
while (k < pp) {
if (s[k] >= s[k+1]) {
break;
}
double t = s[k];
s[k] = s[k+1];
s[k+1] = t;
if (wantv && (k < n-1)) {
for (int i = 0; i < n; i++) {
t = V[i][k+1]; V[i][k+1] = V[i][k]; V[i][k] = t;
}
}
if (wantu && (k < m-1)) {
for (int i = 0; i < m; i++) {
t = U[i][k+1]; U[i][k+1] = U[i][k]; U[i][k] = t;
}
}
k++;
}
iter = 0;
p--;
}
break;
}
}
A = null;
}
/* ------------------------
Public Methods
* ------------------------ */
/** Return the left singular vectors
@return U
*/
public Matrix getU () {
return U==null?null:new Matrix(U);
}
/** Return the right singular vectors
@return V
*/
public Matrix getV () {
return V==null?null:new Matrix(V);
}
/** Return the one-dimensional array of singular values
@return diagonal of S.
*/
public double[] getSingularValues () {
return s;
}
/** Return the diagonal matrix of singular values
@return S
*/
public Matrix getS () {
Matrix X = new Matrix(ncu,n);
double[][] S = X.getArray();
for (int i = Math.min(m,n)-1; i>=0; i--)
S[i][i] = s[i];
return X;
}
/** Return the diagonal matrix of the reciprocals of the singular values
@return S+
*/
public Matrix getreciprocalS () {
Matrix X = new Matrix(n,ncu);
double[][] S = X.getArray();
for (int i = Math.min(m,n)-1; i>=0; i--)
S[i][i] = s[i]==0.0?0.0:1.0/s[i];
return X;
}
/** Return the Moore-Penrose (generalized) inverse
* Slightly modified version of Kim van der Linde's code
@return A+
*/
public Matrix inverse(boolean omit) {
double[][] inverse = new double[n][m];
if(rank()> 0) {
double[] reciprocalS = new double[s.length];
if (omit) {
double tol = Math.max(m,n)*s[0]*Math.pow(2.0,-52.0);
for (int i = s.length-1;i>=0;i--)
reciprocalS[i] = Math.abs(s[i])<tol?0.0:1.0/s[i];
}
else
for (int i=s.length-1;i>=0;i--)
reciprocalS[i] = s[i]==0.0?0.0:1.0/s[i];
int min = Math.min(n, ncu);
for (int i = n-1; i >= 0; i--)
for (int j = m-1; j >= 0; j--)
for (int k = min-1; k >= 0; k--)
inverse[i][j] += V[i][k] * reciprocalS[k] * U[j][k];
}
return new Matrix(inverse);
}
/** Two norm
@return max(S)
*/
public double norm2 () {
return s[0];
}
/** Two norm condition number
@return max(S)/min(S)
*/
public double cond () {
return s[0]/s[Math.min(m,n)-1];
}
/** Effective numerical matrix rank
@return Number of nonnegligible singular values.
*/
public int rank () {
double tol = Math.max(m,n)*s[0]*Math.pow(2.0,-52.0);
int r = 0;
for (int i = 0; i < s.length; i++) {
if (s[i] > tol) {
r++;
}
}
return r;
}
}
Date Index |
Thread Index |
Problems or questions? Contact list-master@nist.gov