Re: Linear Interpolation Inversion for N even?

On May 7, 5:04 pm, "Roger Stafford"
<ellieandrogerxy...@xxxxxxxxxxxxxxxxxxxxxx> wrote:
Greg Heath <he...@xxxxxxxxxxxxxxxx> wrote in message <8c13e682-
e924-4aea-8d41-d5d78bfd4...@xxxxxxxxxxxxxxxxxxxxxxxxxxx>...
On May 6, 11:54 pm, "Roger Stafford"
<ellieandrogerxy...@xxxxxxxxxxxxxxxxxxxxxx> wrote:
Greg Heath <he...@xxxxxxxxxxxxxxxx> wrote in message
<6ca9feef-9014-4491-
b1d2-60acf4d08...@xxxxxxxxxxxxxxxxxxxxxxxxxxxx
...> This doesn't work for any N.
-------
Greg, my understanding of your problem is that from
xm(1),xm(2),...,xm(n-1), and some s, you want to recover
the original x's, where

xm(1) = (x(1)+x(2))/2
xm(2) = (x(2)+x(3))/2
...
xm(n-1) = (x(n-1)+x(n))/2

I proposed s = x(1)-x(2)+x(3)-x(4)+x(5)....

but you don't know x you only know xm.

Now I understand where you are coming from.

I admit you'll have to do a little work, but such an s
would actually suffice to recover the original x's. This
can be shown by the following example.
Let n = 4. Define matrix A by

A = [.5 .5 0 0;
0 .5 .5 0;
0 0 .5 .5;
1 -1 1 -1];

b = [xm;s];

but s(x) is unknown.

where xm is a column vector. The equation

A*x = b;

corresponds to the original equalities above, and solving it
for the x's by way of x = A\b would recover their original
values uniquely. The general formula for the determinant of
A when its size is n x n is (-.5)^(n-1)*n, so A can never
be singular and these linear equations always have a unique
solution.

Of course there is an infinitude of other ways of defining
s that would also work, but I thought this one fit in with
the spirit of your original sum, even though that one didn't
actually work for even values of n. As you see, the
above s works for all n, even or odd.

I see now that

2*sum(j=1,N-1){ xm(j)} = 2*sum(j=1,N){ x(j) } - ( x(1) + x(N) )
= - x(1) - x(N)% for mean(x) = 0

and

2*sum(j=1,N-1){(-1)^(j-1) * xm(j) } = x(1) + (-1)^(N-2) * x(N)
= x(1) - x(N)% for N odd
= x(1) + x(N)% for N even

Which leads to the simultaneous solution of x(1) and x(N) when
N is odd and an undetermined solution when N is even.

Hope this helps.

Greg

-----------------
Greg, I confess I'm feeling a bit exasperated at this point.

Very sorry for the confusion. See my explanation at the bottom of this
post.

Originally, you
asked the question, and I quote, "Is there a way to recover x if no original
points are known and N is even?" (in reference to only knowing the midpoint
values xm.) The answer is a flat NO for both N even or N odd. There is no
way the x's can be recovered without some additional information.

Agree.

You also stated, "Under certain conditions the sampled function x(1:N) can
be reconstructed from the linearly intepolated midpoints." That circumstance
was that N be odd and the sum(x) be known, and this is true. It is not true if
N is even.

I proposed that instead of knowing sum(x), suppose you knew

s = sum((-1).^(0:N-1).*x)

which is just x(1)-x(2)+x(3)-x(4)+... In that case the x's can be recovered if s
is known, no matter whether N is even or odd.

OK. I now see what you are doing.

Your response was to complain that you didn't know s because you didn't
know x. Why in the odd N case doesn't it also bother you that you don't know
sum(x) because you don't know x? What is there so special about sum(x), as
opposed to the sum of the x's with alternating sign reversals?

mean(x) = 0 is a common constraint for my application. See below.

You will never be able to reconstruct the x values knowing only the xm
values. That is a fact. You must know some one other additional bit of
information about them. Answering a hypothesis about such additional
knowledge with the statement that "but you don't know x you only know xm"
is not going to bring you any closer to a resolution to your problem! You
must make up your mind whether or not you are going to permit anything
else to be known about these x's other than their midpoints, xm. If you
aren't, there is no solution to the problem. If you are, it isn't reasonable to
object to such additional knowledge simply because "but you don't know x."

In your last paragraph you appear to be tentatively trying out the hypothesis
of knowing the alternate-signs sum,

No. I wasn't. I was trying to see what information was in the
alternating
sign sum of the xms. So that given mean(x) = 0, perhaps I could
recover
x when N was even.

but your attempt to do the
reconstruction is entirely incorrect. That is not the way it is done. It must be
done as I described in the earlier article, solving the equation A*x = b which I
defined there.


Roger,

I tried to make a simple question out of a step in a more
complicated algorithm. Obviously, the way I worded it was
misleading. I apologize for the time you put in. However,
it was not wasted. I did learn at least three things: The
usefulness of the alternating sum, the framing of an
interpolation inversion as a matrix inversion and how to
handle the inversion with an arbitrary linear constraint
on x.

In the the thread "DFT for Nonuniform Spacing" I proposed
a trapezoidal area approximation to the finite Fourier
Integral. Given the corresponding spectrum, the frequency
to time inversion recovers the linearly interpolated points.
The next step is to recover the original points. I found
that I couldn't do it unless I had additional info. Knowing
an original point worked but was an unusual constraint for
a Fourier inversion. A more natural constraint was mean(x)
= 0 because it is a common step before calculating a
spectrum. However, it only worked for N odd. I couldn't
find a solution for N even ... hence the poorly worded
question of this post.

In spite of the miscommunication, your contribution
was worthwhile.

Hope this apology is enough to unexasperate you,

Greg

P.S. What is the general expression for the determinant when
the bottom row is all 1s?
.

Relevant Pages

  • Re: While statement
    ... > sum off all the odd numbers. ... > inputed value some of the eben integers and sum of odd integers. ... > start loop ... It sounds like your pseudocode will more or less actually do what the ...
    (comp.lang.java.programmer)
  • Re: Enigma 1539 - Board with numbers
    ... consists of a 10-by-10 grid of squares. ... Since successive rows have numbers in opposite orders, the sum of pairs of numbers in consecutive rows is a constant for a given pair of rows - that is, it doesn't change with column number. ... We can choose r so that it's odd ...
    (rec.puzzles)
  • Re: how does this work
    ... Remember that the binary expansion of a 5 nibble is 0101b. ... 0x55555555) are the odd bits, both aligned to the even bit positions. ... Which is a sequence of 8 fields each of which is the sum of the bits ...
    (comp.programming)
  • Re: counting divisors/submultisets
    ... number of k-element submultisets of a multiset that has multiplicities ... this should be one of the things the generating function is good ... If all n_i are even, tauis odd and G= 1, so ... I guess you could look at the sum of tau_k ...
    (sci.math)
  • Re: Linear Interpolation Inversion for N even?
    ... (n-1), and some s, you want to recover the original x's, where ... recover the original x's. ... be singular and these linear equations always have a unique solution. ... above s works for all n, even or odd. ...
    (comp.soft-sys.matlab)
Loading