Linear Interpolation Inversion for N even?
in [Matlab]
|
From: Greg Heath on 6 May 2008 03:23 Linear Interpolation Inversion for N even? Under certain conditions the sampled function x(1:N) can be reconstructed from the linearly intepolated midpoints xm = (x(1:end)+x(2:end))/2 For example, if one of the original points (e.g. x(j)) is known, then for i = j:N-1 x(i+1) = 2*xm(i)-x(i); end for i = j:-1:2 x(i-1) = 2*xm(i-1)-x(i); end If x(j) is arbitrarily initialized, the above algorithm will yield errors that are constant in magnitude and alternating in sign. Therefore, if mean(x) = 0 and N is odd, the error is easily removed by using sum(x). y = zeros(N,1); z = cos(pi*(0:N-1)'); % [+1,-1,...,-1]' if rem(N,2) ~= 0 % N odd for j=2:N y(j) = 2*xm(j-1)-y(j-1); end s = sum(y) x = y - s*z; else error('Reconstruction unknown for N even.') end The algorithm obviously doesn't work for N even because sum(y) = 0 for arbitrary x(j). Is there a way to recover x if no original points are known and N is even? Thanks in advance, Greg
From: Gordon Sande on 6 May 2008 08:36 On 2008-05-06 04:23:38 -0300, Greg Heath <heath(a)alumni.brown.edu> said: > Linear Interpolation Inversion for N even? > > Under certain conditions the sampled function > x(1:N) can be reconstructed from the linearly > intepolated midpoints > > xm = (x(1:end)+x(2:end))/2 xm will have one less value than x. > For example, if one of the original points > (e.g. x(j)) is known, then An original point will be a value not supplied in xm. > for i = j:N-1 > x(i+1) = 2*xm(i)-x(i); > end > for i = j:-1:2 > x(i-1) = 2*xm(i-1)-x(i); > end > > If x(j) is arbitrarily initialized, the above > algorithm will yield errors that are constant > in magnitude and alternating in sign. Therefore, > if mean(x) = 0 and N is odd, the error is easily > removed by using sum(x). An external assumption that supplies one value. Why do you need n odd? > y = zeros(N,1); > z = cos(pi*(0:N-1)'); % [+1,-1,...,-1]' > > if rem(N,2) ~= 0 % N odd > for j=2:N > y(j) = 2*xm(j-1)-y(j-1); > end > s = sum(y) > x = y - s*z; > else > error('Reconstruction unknown for N even.') > end > > The algorithm obviously doesn't work for N even > because sum(y) = 0 for arbitrary x(j). > > Is there a way to recover x if no original points > are known and N is even? Find some way to supply an additional value. For some applications the initial value will be available as used above. For others the total (or mean) may be known as also used above. Sometimes the initial difference (derivative) might be know. And so on. Some of the external values will be easy to use and others will take a bit more work. Write it out as a matrix equation. It will be missing one row. Find another row that is linearly independent. > Thanks in advance, > > Greg
From: Roger Stafford on 6 May 2008 23:54 Greg Heath <heath(a)alumni.brown.edu> wrote in message <6ca9feef-9014-4491- b1d2-60acf4d08cd1(a)x41g2000hsb.googlegroups.com>... > This doesn't work for any N. > Greg ------- 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).... 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]; 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. Roger Stafford
From: Greg Heath on 7 May 2008 14:17 On May 6, 11:54 pm, "Roger Stafford" <ellieandrogerxy...(a)mindspring.com.invalid> wrote: > Greg Heath <he...(a)alumni.brown.edu> wrote in message > > <6ca9feef-9014-4491- > b1d2-60acf4d08...(a)x41g2000hsb.googlegroups.com>...> This doesn't work for any N. > > Greg > > ------- > 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. > > 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
|
Pages: 1 Prev: cheap authentic nike air force 1s Next: How to know about binary video file header??? |