zero-pad as an interpolation in frequency domain?

Hi all,

I read somewhere that we can derive mathematically the zero padding
equation to show that zero-padding is simply an interpolation in
frequency domain. I tried to derive but still could not see the
interpolation operator. Can you please tell me how to derive it from
DFT formula?

Thanks

On 19 Nov, 15:26, "A.E lover" <aelove...@gmail.com> wrote:
> Hi all,
>
> I read somewhere that we can derive mathematically the zero padding
> equation to show that zero-padding is simply an interpolation in
> frequency domain. I tried to derive but still could not see the
> interpolation operator. Can you please tell me how to derive it from
> DFT formula?

That's partially correct.

If you start with N non-zero samples and pad with q*N
zeros (q a non-zero positive integer) then you will
find that the spectrum coefficients from your original
signal are preserved in the zero-padded spectrum, and
you have q additional equidistantly spaced coefficients
between the original coefficients.

If you don't pad with q*N zeros the original spectrum
coefficients are not preserved, and the term
"interpolation" becomes, well, useless.

Rune

On Nov 19, 7:55 am, Rune Allnor <all...@tele.ntnu.no> wrote:
> On 19 Nov, 15:26, "A.E lover" <aelove...@gmail.com> wrote:
>
> > Hi all,
>
> > I read somewhere that we can derive mathematically the zero padding
> > equation to show that zero-padding is simply an interpolation in
> > frequency domain. I tried to derive but still could not see the
> > interpolation operator. Can you please tell me how to derive it from
> > DFT formula?
>
> That's partially correct.
>
> If you start with N non-zero samples and pad with q*N
> zeros (q a non-zero positive integer) then you will
> find that the spectrum coefficients from your original
> signal are preserved in the zero-padded spectrum, and
> you have q additional equidistantly spaced coefficients
> between the original coefficients.
>
> If you don't pad with q*N zeros the original spectrum
> coefficients are not preserved, and the term
> "interpolation" becomes, well, useless.
>
> Rune

A.E.

If you start with N contiguous non-zero weighted samples and pad with
any positive integer number of zeros you will get perfectly valid
coefficients from your zero-padded spectrum. Just don't call them
'interpolated' where Rune can hear if they don't include the non-zero
padded coefficients.

Dale B. Dalrymple
http://dbdimages.com
http://stores.lulu.com/dbd

On Nov 19, 7:55 am, Rune Allnor <all...@tele.ntnu.no> wrote:
> On 19 Nov, 15:26, "A.E lover" <aelove...@gmail.com> wrote:
>
> > Hi all,
>
> > I read somewhere that we can derive mathematically the zero padding
> > equation to show that zero-padding is simply an interpolation in
> > frequency domain. I tried to derive but still could not see the
> > interpolation operator. Can you please tell me how to derive it from
> > DFT formula?
>
> That's partially correct.
>
> If you start with N non-zero samples and pad with q*N
> zeros (q a non-zero positive integer) then you will
> find that the spectrum coefficients from your original
> signal are preserved in the zero-padded spectrum, and
> you have q additional equidistantly spaced coefficients
> between the original coefficients.
>
> If you don't pad with q*N zeros the original spectrum
> coefficients are not preserved, and the term
> "interpolation" becomes, well, useless.

If you pad with enough zeros so that you end up with a
window of a length equal to the multiple of the two above
cases, those same new coefficients will appear, and the DFT
will be padded with q*N zeros for a larger q.  Why would
you call these identical new coefficients interpolations
in one case and not the other?

On 19 Nov, 20:59, dbd <d...@ieee.org> wrote:
> On Nov 19, 7:55 am, Rune Allnor <all...@tele.ntnu.no> wrote:
>
>
>
>
>
> > On 19 Nov, 15:26, "A.E lover" <aelove...@gmail.com> wrote:
>
> > > Hi all,
>
> > > I read somewhere that we can derive mathematically the zero padding
> > > equation to show that zero-padding is simply an interpolation in
> > > frequency domain. I tried to derive but still could not see the
> > > interpolation operator. Can you please tell me how to derive it from
> > > DFT formula?
>
> > That's partially correct.
>
> > If you start with N non-zero samples and pad with q*N
> > zeros (q a non-zero positive integer) then you will
> > find that the spectrum coefficients from your original
> > signal are preserved in the zero-padded spectrum, and
> > you have q additional equidistantly spaced coefficients
> > between the original coefficients.
>
> > If you don't pad with q*N zeros the original spectrum
> > coefficients are not preserved, and the term
> > "interpolation" becomes, well, useless.
>
> > Rune
>
> A.E.
>
> If you start with N contiguous non-zero weighted samples and pad with
> any positive integer number of zeros you will get perfectly valid
> coefficients from your zero-padded spectrum.

Well, I suppose that's true, as long as you don't claim
that your spectrum has a resolution as 1/Nfft...

> Just don't call them
> 'interpolated' where Rune can hear if they don't include the non-zero
> padded coefficients.

Is the term "interpolate" valid if the modified sequence
of points does not contain the original data?

In the maths dealing with continuous functions there is a
distinct difference between "interpolation" where the
continous function intersects the samples given, and
"approximation" where an intersection is not required.

Which raises two questions:

- How is an "interpolation" defined?
- How do you "interpolate" a discrete sequence
  to form another discrete sequence (as opposed
  to form a continuous function)?

I must admit that I said the term "interpolation"
is useless because I don't know the answers to these
questions. It seems Dale does, though, so I am looking
forward to be enlightened.

Rune

"Rune Allnor" <allnor@tele.ntnu.no> wrote in message 
news:505cd98e->

> Is the term "interpolate" valid if the modified sequence
> of points does not contain the original data?
>
> In the maths dealing with continuous functions there is a
> distinct difference between "interpolation" where the
> continous function intersects the samples given, and
> "approximation" where an intersection is not required.
>
> Which raises two questions:
>
> - How is an "interpolation" defined?
> - How do you "interpolate" a discrete sequence
>  to form another discrete sequence (as opposed
>  to form a continuous function)?
>

"interpolation" == "fill in the blanks"

"approximation" == "estimation"

They are not mutually exclusive.  You can have both 
operations going on in one process.  You can interpolate a 
discrete sequence by modeling the original sequence and then 
generating the requisite samples from the model.  The model 
may or may not pass through the points of the original 
sequence.

On 19 Nov, 23:19, "Ron N." <rhnlo...@yahoo.com> wrote:
> On Nov 19, 7:55 am, Rune Allnor <all...@tele.ntnu.no> wrote:

> > If you don't pad with q*N zeros the original spectrum
> > coefficients are not preserved, and the term
> > "interpolation" becomes, well, useless.
>
> If you pad with enough zeros so that you end up with a
> window of a length equal to the multiple of the two above
> cases, those same new coefficients will appear, and the DFT
> will be padded with q*N zeros for a larger q.  Why would
> you call these identical new coefficients interpolations
> in one case and not the oher?

I don't understand what you mean? I didn't specify q
to be anything else than a non-zero positive integer.
I did not say it needs to be a prime number; that has
nothing to do with anything.

The main issue is that the original spectrum coefficients
(from a non-padded data set) are preserved.

Rune

On 20 Nov, 11:27, "John E. Hadstate" <jh113...@hotmail.com> wrote:

> "interpolation" == "fill in the blanks"
>
> "approximation" == "estimation"
>
> They are not mutually exclusive.

Do you know of an interpolation scheme that does *not*
intersect the given points?

Rune

On Nov 20, 3:22 am, Rune Allnor <all...@tele.ntnu.no> wrote:
> On 19 Nov, 23:19, "Ron N." <rhnlo...@yahoo.com> wrote:
>
> > On Nov 19, 7:55 am, Rune Allnor <all...@tele.ntnu.no> wrote:
> > > If you don't pad with q*N zeros the original spectrum
> > > coefficients are not preserved, and the term
> > > "interpolation" becomes, well, useless.
>
> > If you pad with enough zeros so that you end up with a
> > window of a length equal to the multiple of the two above
> > cases, those same new coefficients will appear, and the DFT
> > will be padded with q*N zeros for a larger q.  Why would
> > you call these identical new coefficients interpolations
> > in one case and not the oher?
>
> I don't understand what you mean? I didn't specify q
> to be anything else than a non-zero positive integer.
> I did not say it needs to be a prime number; that has
> nothing to do with anything.

Not a prime number, but the product of the periodic
and non-periodic zero-padded window lengths (maybe
minus 1, if q is the number of zeros not the length).

> The main issue is that the original spectrum coefficients
> (from a non-padded data set) are preserved.

The spectrum coefficients will be preserved in product
length window, and be identical (minus perhaps a length
scale factor) to those in the non-periodic zero-padded
window.  So why not call these same identical coefficients
in the non-periodic zero-pad length the same thing?

On Nov 19, 11:56 pm, Rune Allnor <all...@tele.ntnu.no> wrote:
> On 19 Nov, 20:59, dbd <d...@ieee.org> wrote:
>
>
>
> Well, I suppose that's true, as long as you don't claim
> that your spectrum has a resolution as 1/Nfft...
>
> > Just don't call them
> > 'interpolated' where Rune can hear if they don't include the non-zero
> > padded coefficients.
>
.> Is the term "interpolate" valid if the modified sequence
.> of points does not contain the original data?
.>
.> In the maths dealing with continuous functions there is a
.> distinct difference between "interpolation" where the
.> continous function intersects the samples given, and
.> "approximation" where an intersection is not required.
.>
.> Which raises two questions:
.>
.> - How is an "interpolation" defined?
.> - How do you "interpolate" a discrete sequence
.>   to form another discrete sequence (as opposed
.>   to form a continuous function)?
.>
.> I must admit that I said the term "interpolation"
.> is useless because I don't know the answers to these
.> questions. It seems Dale does, though, so I am looking
.> forward to be enlightened.
.>
.> Rune

If you thought "interpolation' was useless, why did you apply a
definition? I think that was your answer, here's mine.

I think that the discrete domain definition that matches your
continuous domain definition would be that the process consistently
samples an interpolation function that passes through the original
sample points. 'Consistently' meaning that when the process generates
a sample at a particular frequency, it generates the same value for
that frequency.

One of the differences between the continuous and  the discrete
domains is that in the discrete domain there is no requirement to
generate the function values at the same arguments to specify the
function. In the discrete domain the proper question might be "Do the
points 'represent' the original 'information' ."

Using your q = 1, if I calculate the odd frequency terms of a DFT, are
they not interpolated values unless I also choose to calculate the
even terms which replicate the terms for the non-zero-extended case? I
think that they should be considered interpolated values no matter how
many of them I calculate and this definition allows that. It is a
different question as to how many (and which) interpolated values
would be needed to reconstruct the original samples.

Too restrictive? Too general? Any alternatives?

Dale B. Dalrymple
.