Re: Question abot the SVD of 1-dimensional data
- From: Ivan Oseledets <ivan.oseledets@xxxxxxxxx>
- Date: Wed, 26 Apr 2006 09:09:18 EDT
Hello
If I have some exact data created by sampling a
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
y 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
When you have a function f(x)
and build a matrix
A = f(i+j-1) (it is a Hankel matrix)
the matrix A will be rank-deficient not only when f is polynomial but also when f is a sum of a few exponentials:
f = \sum_{k=1}^r c_k exp(a_k x)
In this case A will have rank r.
This fact forms a basis for a well-known (but unstable) Prony method for the approximation of a function by a sum of exponentials. Check the paper by G. Beylkin "Approximation by exponential sums"
So I strongly doubt that you can use the same approach for the approximation by polynomials, it is better to use for example approximation by a sum of Chebyshev polynomials.
Your (2) I suppose is due to the fact that the noise is greater that the smallest non-vanishing singular values of A.
.
- Prev by Date: Re: linear interpolation error bound
- Next by Date: Re: Positive definite matrices
- Previous by thread: Re: Question abot the SVD of 1-dimensional data
- Next by thread: linear interpolation error bound
- Index(es):
Relevant Pages
|
|
