Re: Question abot the SVD of 1-dimensional data
- From: spellucci@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx (Peter Spellucci)
- Date: Tue, 25 Apr 2006 18:08:16 +0000 (UTC)
In article <1145974470.686441.5500@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
jw12jw12jw12@xxxxxxxxx writes:
Hello
If I have some exact data created by sampling a polynomial at evenly
spaced points, say v[i]=3*i^2+2*i+4, and then put my data in matrix
form, say matrix A where a[i,j] = v[i+j-1], so the original data
appears as columns of A with the starting value of each column shifted
one step, then
the rank of the matrix will be the degree of the polynomial plus 1. (A
constant polynomial gives a rank 1 matrix, a linear polynomial gives a
rank 2 matrix, etc)
Now suppose I use floating point values generated by a polynomial of
degree n . There will be rounding errors in the samples resulting in
problems computing the rank in a naive way but if I find the SVD of the
matrix the first n+1 singular values will be larger than the remaining
ones and this can be used to estimate the rank.
Finally suppose I add noise in the form of small random values to my
data...
Now (1) When using floating point without added noise the cutoff
between the first n+1 singular values and the rest is not as large as I
expected. For example, in the case of a cubic polynomial I got 186.5,
1.1, .03, .0005, and then falling off to 10^(-14). Now relatively
speaking that's a large drop but it's not as dramatic as I expected
given the rapid decrease in the first 4 singular values.
The context of this is trying to determine the appropriate degree of a
polymial that should be used in fitting some data.
and (2) when I add a relatively small amount of noise (data values
ranged from 0 to 25, noise was random in the range -0.1 to 0.1) the
singular values for the above example became 186.5, 1.3, .6, .6, .5,
.5, and the rest essentially 0. So the cubic nature of the generating
polynomial was totally hidden.
Again, I didn't expect the SVD to be this sensitive to what seems like
a small corruption of the initial data.
Is this approach totally wrong-headed? Can the SVD be used in this way
to determine the degree of the polynomial which generates some data?
Should the data be filtered or treated in some way before applying the
SVD?
Thanks
j wales
theorem 1: given a matrix A and a matrix B of the same shape, with singular
values s_1(A)>= ... >= s_n(A) and s_1(B) >= .. >= s_n(B)
then
| s_i(A) - s_i(B) | <= ||A - B|| = s_1(A-B)
hence the noise in your data determines the noise in the singular values and it
may well be that they all are unequal zero whatever is n (the column number)
what you forgot: the polynomial representation of a polynomial in the
standard basis is itself badly conditioned, that means will have a wide spread
of singular values , and, depending on the scale, some very small, below the
level of your noise, as you observed.
that is no failure of the svd, it is a failure of the polynomial representation.
better: transform the independent variable linearly to the interval [-1,1]
and use there the chebyhev basis (chebyshev polynomials of the first kind)
the use of the orthogonal polynomials relative to the discrete scalar
product sum_i f(x(i))*g(x(i)) which are theoretically optimal here
is discouraged because the computation of these polynomials themselves is
a badly conditioned process
hth
peter
.
- Follow-Ups:
- Re: Question abot the SVD of 1-dimensional data
- From: Duncan Muirhead
- Re: Question abot the SVD of 1-dimensional data
- Prev by Date: Re: Inverse problem with too many parameters?
- Next by Date: Re: generating nonrepeating random numbers
- Previous by thread: Coding for arbitrary dimensional problems?
- Next by thread: Re: Question abot the SVD of 1-dimensional data
- Index(es):
Relevant Pages
|
