3
$\begingroup$

According to Dr. Math the Z-transform can create closed-form solutions for 1D series defined by difference equations (e.g. the Fibonacci series).

My 3D surface $z=LC(x,y)$ is defined by difference equations:

\begin{eqnarray} t_0 &=& N^2 \\ t_1 &=&(N-y)^2 \\ t_i &=&2*t_{i-1}-t_{i-2}+2y^2 \end{eqnarray}

I am interested in preserving the absolute minima of this surface iff it lies on an integer boundary. My first question is: how do I modify the closed-form solution for a 2D signal?

My second question is: should I expect the closed-form solution to be different from the original formula? { The original formula is $t=(N-xy)^2$ }


POSTSCRIPT

The difference equations come from the relation:

\begin{eqnarray} (1) & (N - (i+2)*y)^2 - (N-iy)^2 &=& -4Ny - 4y^2i - 4y^2\\ (2) & (N - (i+1)*y)^2 - (N-iy)^2 &=& -2Ny - 2y^2i - y^2\\ (1)-(2) & t(i+2)-t(i) &=& \hspace{1em}2 ( t(i+1) - t(i) ) - 2y^2 \end{eqnarray}

The function has an absolute minima at zero in t. When N=UV, it is the same absolute minima that occurs for the difference equation:

\begin{eqnarray} (1) & (N - (x+2U)*y)^2 - (N-xy)^2 & = & -4UNy - 4xUy^2 - 4(Uy)^2\\ (2) & (N - (x+U)*y)^2 - (N-xy)^2 & = & -2UNy - 2xUy^2 - (Uy)^2\\ (1),(2) & t_{i+2}-t_i & = & \hspace{1em} 2 ( t_{i+1} - t_i ) - 2U^2y^2 \end{eqnarray}

The initial conditions and the value of U are critical to the problem definition. My feeling is that even though the inverse z-transform is not unique, the set of inverse transforms will not converge at x=U, y=V, t=0 without prior knowledge of U.

z-transform

So, if I understand the process, the generalized z-transform for t along the x axis is:

\begin{eqnarray} Z[ - 2(Uy)^2 ] & = & Z[ t_{i+2} - 2 t_{i+1} + t_{i} ] \\ \frac{-2(Uy)^2z}{z-1}&=& z^2(T_z - t(0) -t(U)/z) - 2z(T_z - t(0)) + T_z \\ \frac{-2(Uy)^2z}{z-1}&=& T_z(z^2 - 2z + 1) -z^2t(0)-z(t(U)-2t(0)) \\ -2(Uy)^2z&=& T_z(z- 1)^3 -z^3t(0)-z^2(t(U)-3t(0))-z(t(U)-2t(0)) \\ -2(Uy)^2z&=& T_z(z- 1)^3 -z^3N^2-z^2((N-Uy)^2-3N^2)-z((N-Uy)^2-2N^2) \\ T_z(z- 1)^3 & = & z^3N^2+z^2((N-Uy)^2-3N^2)-z((N-Uy)^2-2N^2-2(Uy)^2) \\ T_z(z- 1)^3 & = &z^3 N^2 - z^2(2N^2+2NUy-(Uy)^2) + z((Uy)^2+2NUy+N^2 )\\[2em] \frac{T_z}{z} & = &\frac{z^2 N^2 - z(2N^2+2NUy-(Uy)^2) + ((Uy)^2+2NUy+N^2 )}{(z- 1)^3}\\ \frac{T_z}{z} & = N^2&\frac{z^2 - z(2+2y/V-(y/V)^2) + ((y/V)^2+2y/V+1 )}{(z- 1)^3}\\ \frac{T_z}{z} & = N^2&\frac{z^2 -2z +1 - z(2y/V-(y/V)^2) + ((y/V)^2 + 2y/V )}{(z- 1)^3}\\ \frac{T_z}{z} & = N^2&\frac{z^2 -2z +1 - (z-1)(2y/V) + (z-1)(y/V)^2 + 2(y/V)^2}{(z- 1)^3}\\ \frac{T_z}{z} & = N^2&\left(\frac{1}{z- 1}-\frac{2y/V-(y/V)^2}{(z- 1)^2}+\frac{2(y/V)^2}{(z- 1)^3}\right)\\ \frac{T_z}{z} & = N^2&\left(\frac{1}{z- 1}-\frac{2y/V}{(z- 1)^2}+\frac{(y/V)^2*(z-1)+2(y/V)^2}{(z- 1)^3}\right)\\ \frac{T_z}{z} & = N^2&\left(\frac{1}{z- 1}-\frac{2y/V}{(z- 1)^2}+\frac{(y/V)^2z+(y/V)^2}{(z- 1)^3}\right)\\ \frac{T_z}{z} & = N^2&\left(\frac{1}{z- 1}-\frac{2y/V}{(z- 1)^2}+\frac{(y/V)^2(z+1)}{(z- 1)^3}\right) \end{eqnarray}

normalization along y

The final form of the z-transform is dependent on the ratio $\Upsilon$ of $y$ to $V$, which we know will vary from $0$ to $1$. Along the cross-section when $y=V, \Upsilon=1$, the trivial case occurs with a sequence $N^2, 0, N^2, 4N^2, ...$.

\begin{eqnarray} \frac{T_z}{z} & = N^2&\left(\frac{1}{z- 1}-\frac{2y/V-(y/V)^2}{(z- 1)^2}+\frac{2(y/V)^2}{(z- 1)^3}\right)\\ \frac{T_z}{z} & = N^2&\left(\frac{1}{z- 1}-\frac{2\Upsilon-\Upsilon^2}{(z- 1)^2}+\frac{2\Upsilon^2}{(z- 1)^3}\right)\\ \left.\frac{T_z}{z}\right\rvert_{\Upsilon=1} & = N^2&\left(\frac{1}{z- 1}-\frac{1}{(z- 1)^2}+\frac{2}{(z- 1)^3}\right) \end{eqnarray}

inverse z-transform

A unique time-domain function can be obtained using lookup tables and numerical methods such as those found at Wolfram:

\begin{eqnarray} t_i & = N^2(i\Upsilon - 1)^2 \end{eqnarray}

The next step is to use Direct Inversion to calculate the inverse transform. This method involves calculating a closed integral as defined by:

$$t=\frac{1}{2{\pi}j}\oint_H Tz^{x-1} \,dz$$

For $t$ to be unique, $H$ must encircle all poles and zeros (aka ROC), however here it is desired to investigate what happens when $H$ is smaller than the ROC. Specifically, we desire to find a contour $H$ so that the inverse transform is equivalent to spline interpolation of our point cloud.

$\endgroup$
  • $\begingroup$ I'd appreciate anyone's help in checking my math $\endgroup$ – zQAycX Jun 11 '15 at 20:29
  • $\begingroup$ Wouldn't that be a better fit at math.SE? $\endgroup$ – Matt L. Jun 13 '15 at 20:36
1
$\begingroup$

I'm going to go ahead and answer this question with a "Maybe, but not necessary".

I've found an article written by Wolberg G entitled "an energy-minimization framework for monotonic cubic spline interpolation" which seems to be on the mark, at least from reading the abstract.

It will take me a little longer to figure out the paper and how to apply it to my specific example, but in general I think it demonstrates that there is research in the field which can control the amount of oscillation when trying to preserve the absolute minima of a point cloud.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.