> Hi all,
>
> I need your help on the following difficulties:
>
> I am designing something like "automatic" detection of aliasing,
> programmatically.

Can't be done. Just one of those facts of life.

> For a given signal discrete time signal x(n), possibly infinite support, we
> know its values are all positive, they are absolutely summable, so DTFT
> exists and we know that the signal die down for large n, and it can be
> roughly deemed as zero for some N and for all n>=N.
>
> Now suppose we don't have the signal x(n) in the time domain, so we don't
> know N, but we have its DTFT available, called X(w).
>
> The problem is to decide the smallest number of sampling point needed to
> sample the X(w) in the frequency domain.

This has nothing to do with aliasing. "Aliasing" means that
there is an ambiguity between the spectrum and time-domain
representations of a signal. What you want, is an efficient
way of reconstructing the time-domain signal based on its
spectrum.
This happens to be a standard problem in acoustic propagation
modeling, albeit concerning spatial rather than temporal
spectra. Find a copy of jensen et al's "Computational
Ocean Acoustics" and check out "adaptive wavenumber
integration." The key is to sample the wavenumber specrtum
densely where lot of energy is located, and more sparsely
elsewhere.
You might also want to check out Henrik Schmidt's articles
on wavenumber integration in the Journal of the American
Society of Acoustics and Journal of Computational Acoustics.
He wrote a lot from, say, 1984 and onwards.
Rune

Reply by Ron N.●June 3, 20072007-06-03

On Jun 2, 10:50 pm, Eric Jacobsen <eric.jacob...@ieee.org> wrote:

> Unless they're both aliased with the aliased energy falling within the
> first 256 points.
>
> I don't see how that gets resolved until you've accumulated an
> infinite number of points.
>
> Theoretically, of course. In any practical system there will be
> natural, unavoidable bandlimiting at some point. The number of
> samples needed may still be completely impractical, though.

Practical systems are not bandlimited. Being bandlimited is
a fictional concept involving infinite precision and time.
Usually, though, the real world has a noise floor so high we
don't care about a signal or systems energy (quantum at the
limit) above a certain bound any more. In mechanical systems
we just change the name of some portion of the systems state,
from position/velocity to temperature for instance.
Impractical or Platonic models can be chaotic and exist in a
fictional world which has no noise or quantum limits, and
thus have infinite spectral energy. The OP hasn't told us
whether he can prove he's not dealing with such from his
model or equations before proceeding.
IMHO. YMMV.
--
rhn A.T nicholson d.0.t C-o-M

Reply by Ron N.●June 3, 20072007-06-03

On Jun 2, 2:18 pm, "Vista" <a...@gmai.com> wrote:

> "Jerry Avins" <j...@ieee.org> wrote in message
>
> news:haOdndxyQrQpR_zbnZ2dnUVZ_gSdnZ2d@rcn.net...
>
>
>
> > Vista wrote:
> >> Hi all,
>
> >> I need your help on the following difficulties:
>
> >> I am designing something like "automatic" detection of aliasing,
> >> programmatically.
>
> >> For a given signal discrete time signal x(n), possibly infinite support,
> >> we know its values are all positive, they are absolutely summable, so
> >> DTFT exists and we know that the signal die down for large n, and it can
> >> be roughly deemed as zero for some N and for all n>=N.
>
> >> Now suppose we don't have the signal x(n) in the time domain, so we don't
> >> know N, but we have its DTFT available, called X(w).
>
> >> The problem is to decide the smallest number of sampling point needed to
> >> sample the X(w) in the frequency domain.
>
> >> Sampling X(w) will lead to aliasing and periodic overlapping of x(n). But
> >> for a suitable number of sampling points (related to the unknown N), the
> >> aliasing error can be controlled under a prespecified threshold epsilon.
>
> >> Let's say we start with 128 sampling points, and by eye inspection of the
> >> reconstructed signal x_hat(n) in the time domain, we found aliasing, so
> >> we decide to move to 256 sampling points, so on and so forth.
>
> > You can't detect aliasing by eye or any other way if you don't know the
> > original signal. Every set of samples represents one non-aliased signal
> > and an infinite number of aliased ones.
>
> Why not? If I see 256 and 512 sample points do not yield visual difference,
> then I know 256 is a good number.

What if 99% of the energy is at the very top end of a spectrum that
would only show up with 1 million sample points? Then you might say
256 periodic sample points, 512 points, 1024 points, etc. up to 32k,
all look the same visually, and think you had found all the aliasing,
when in fact you stopped looking with only 1% of the signals energy in
view.
You need to know something about the signals roll-off characteristics
to know when to stop looking. Random sampling might give you more of
a hint, but not with certainty.
IMHO. YMMV.
--
rhn A.T nicholson d.0.t C-o-M

Reply by Eric Jacobsen●June 3, 20072007-06-03

On Sun, 03 Jun 2007 13:53:53 GMT, Vladimir Vassilevsky
<antispam_bogus@hotmail.com> wrote:

>julius wrote:
>
>>
>> For *parametric* signals, there are methods for automatic
>> detection of aliasing without having to resort back to the
>> analog domain, but you don't say what your signal is.
>>
>
>If the signal is sampled with the proper rate then adding the extra
>samples is not going to add any new information. For example, we can
>make a polynomial interpolation of the signal and integrate the squared
>difference between the polynoms for the different sample rates. This can
>be a measure of the amount of aliasing.
>
>Vladimir Vassilevsky

That works in the time domain...the OP is apparently sampling in the
frequency domain.
Eric Jacobsen
Minister of Algorithms
Abineau Communications
http://www.ericjacobsen.org

Reply by Jerry Avins●June 3, 20072007-06-03

Vista wrote:

> "Jerry Avins" <jya@ieee.org> wrote in message
> news:6MqdnVa99MXmYPzbnZ2dnUVZ_sWdnZ2d@rcn.net...
>> Vista wrote:
>>> "Jerry Avins" <jya@ieee.org> wrote in message
>>> news:-OydnVWHs_4Kc_zbnZ2dnUVZ_hOdnZ2d@rcn.net...
>>>> Vista wrote:
>>>>> "Jerry Avins" <jya@ieee.org> wrote in message
>>>>> news:haOdndxyQrQpR_zbnZ2dnUVZ_gSdnZ2d@rcn.net...
>>>>>> Vista wrote:
>>>>>>> Hi all,
>>>>>>>
>>>>>>> I need your help on the following difficulties:
>>>>>>>
>>>>>>> I am designing something like "automatic" detection of aliasing,
>>>>>>> programmatically.
>>>>>>>
>>>>>>> For a given signal discrete time signal x(n), possibly infinite
>>>>>>> support, we know its values are all positive, they are absolutely
>>>>>>> summable, so DTFT exists and we know that the signal die down for
>>>>>>> large n, and it can be roughly deemed as zero for some N and for all
>>>>>>> n>=N.
>>>>>>>
>>>>>>> Now suppose we don't have the signal x(n) in the time domain, so we
>>>>>>> don't know N, but we have its DTFT available, called X(w).
>>>>>>>
>>>>>>> The problem is to decide the smallest number of sampling point needed
>>>>>>> to sample the X(w) in the frequency domain.
>>>>>>>
>>>>>>> Sampling X(w) will lead to aliasing and periodic overlapping of x(n).
>>>>>>> But for a suitable number of sampling points (related to the unknown
>>>>>>> N), the aliasing error can be controlled under a prespecified
>>>>>>> threshold epsilon.
>>>>>>>
>>>>>>> Let's say we start with 128 sampling points, and by eye inspection of
>>>>>>> the reconstructed signal x_hat(n) in the time domain, we found
>>>>>>> aliasing, so we decide to move to 256 sampling points, so on and so
>>>>>>> forth.
>>>>>> You can't detect aliasing by eye or any other way if you don't know
>>>>>> the original signal. Every set of samples represents one non-aliased
>>>>>> signal and an infinite number of aliased ones.
>>>>>>
>>>>> Why not? If I see 256 and 512 sample points do not yield visual
>>>>> difference, then I know 256 is a good number.
>>>> What are you sampling if you have only the DTFT?
>>> As I said, I am sampling the DTFT in frequency domain in [0, 2*pi], and
>>> then apply IFFT to reconstruct x(n) in time domain. And there is aliasing
>>> depending on how many samples I use in sampling.
>>>
>>>>>>> How to automate the above eye inspection process? How to let computer
>>>>>>> decide, programmatically, what is an aliased reconstruction and what
>>>>>>> is not an aliased reconstruction? I hope to find a "quality"
>>>>>>> function, which costs minimal amount of computations, based on which
>>>>>>> the program can decide whether there is aliasing or not. The added
>>>>>>> computational overhead has to be small because we have to run
>>>>>>> millions of this type of "automatic" aliasing detector in real
>>>>>>> time...
>>>>>> Are you sampling in time or frequency? If you have the DTFT, then you
>>>>>> have the highest significant frequency by inspection (once you decide
>>>>>> what "significant" is).
>>>>>>
>>>>> As you see, I am sampling the DTFT X(w). And this is the sampling in
>>>>> frequency. I want to detect the aliasing of time domain signal x(n) due
>>>>> to frequency domain sampling on X(w).
>>>> You can construe the frequency data as a time series and anti-alias
>>>> filter it.
>>>>
>>>
>>> Good idea. Yes, filter in the frequency domain. However I first have to
>>> decide how many samples do I use for [0, 2*pi].
>>>
>>> So you are talking about an analog filter or digital filter?
>> Digital. I didn't imagine you had an analog DTFT. Is there such a thing?
>>
>
>
> If you apply a digital filter in the frequecy domain on the sampled X(w)
> values, treating it as a time series, then you already sample it before you
> apply the anti-aliasing filter. And our original question was exactly how
> many samples do we need to sample the X(w) at the first place.
>
> That's why I felt there is a problem with applying the digital filter...
>
> Any more thoughts?

DTFT stands for DISCRETE TIME Fourier Transform. By its nature, it is
already sampled, or at least exists only at discrete times. "Sampling"
it means decimating it. *There is nothing to sample* between the numbers
that make it up.
Jerry
--
Engineering is the art of making what you want from things you can get.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

Reply by John Herman●June 3, 20072007-06-03

I think Jerry was asking the right question. If the signal is in the
frequency domain with infinite support, at what point is the signal no longer
significant? You then do that size of inverse FFT and perform whatever
antialiasing is required on the time series output and you're done.
In article <RJz8i.24125$YL5.22280@newssvr29.news.prodigy.net>, Vladimir
Vassilevsky <antispam_bogus@hotmail.com> wrote:

>
>
>julius wrote:
>
>>
>> For *parametric* signals, there are methods for automatic
>> detection of aliasing without having to resort back to the
>> analog domain, but you don't say what your signal is.
>>
>
>If the signal is sampled with the proper rate then adding the extra
>samples is not going to add any new information. For example, we can
>make a polynomial interpolation of the signal and integrate the squared
>difference between the polynoms for the different sample rates. This can
>be a measure of the amount of aliasing.
>
>Vladimir Vassilevsky
>
>DSP and Mixed Signal Design Consultant
>
>http://www.abvolt.com
>

Reply by Vladimir Vassilevsky●June 3, 20072007-06-03

julius wrote:

>
> For *parametric* signals, there are methods for automatic
> detection of aliasing without having to resort back to the
> analog domain, but you don't say what your signal is.
>

If the signal is sampled with the proper rate then adding the extra
samples is not going to add any new information. For example, we can
make a polynomial interpolation of the signal and integrate the squared
difference between the polynoms for the different sample rates. This can
be a measure of the amount of aliasing.
Vladimir Vassilevsky
DSP and Mixed Signal Design Consultant
http://www.abvolt.com

Reply by julius●June 3, 20072007-06-03

On Jun 3, 12:50 am, Eric Jacobsen <eric.jacob...@ieee.org> wrote:

>
> Unless they're both aliased with the aliased energy falling within the
> first 256 points.
>
> I don't see how that gets resolved until you've accumulated an
> infinite number of points.
>
> Theoretically, of course. In any practical system there will be
> natural, unavoidable bandlimiting at some point. The number of
> samples needed may still be completely impractical, though.
>
> Eric Jacobsen
> Minister of Algorithms
> Abineau Communicationshttp://www.ericjacobsen.org

What Eric is getting at here, I think, is whether you have any
prior knowledge of your signal of interest. If you do not, then
how can you "know" when there is aliasing?
For *parametric* signals, there are methods for automatic
detection of aliasing without having to resort back to the
analog domain, but you don't say what your signal is.
Julius

Reply by Eric Jacobsen●June 3, 20072007-06-03

On Sat, 2 Jun 2007 14:18:55 -0700, "Vista" <abc@gmai.com> wrote:

>
>"Jerry Avins" <jya@ieee.org> wrote in message
>news:haOdndxyQrQpR_zbnZ2dnUVZ_gSdnZ2d@rcn.net...
>> Vista wrote:
>>> Hi all,
>>>
>>> I need your help on the following difficulties:
>>>
>>> I am designing something like "automatic" detection of aliasing,
>>> programmatically.
>>>
>>> For a given signal discrete time signal x(n), possibly infinite support,
>>> we know its values are all positive, they are absolutely summable, so
>>> DTFT exists and we know that the signal die down for large n, and it can
>>> be roughly deemed as zero for some N and for all n>=N.
>>>
>>> Now suppose we don't have the signal x(n) in the time domain, so we don't
>>> know N, but we have its DTFT available, called X(w).
>>>
>>> The problem is to decide the smallest number of sampling point needed to
>>> sample the X(w) in the frequency domain.
>>>
>>> Sampling X(w) will lead to aliasing and periodic overlapping of x(n). But
>>> for a suitable number of sampling points (related to the unknown N), the
>>> aliasing error can be controlled under a prespecified threshold epsilon.
>>>
>>> Let's say we start with 128 sampling points, and by eye inspection of the
>>> reconstructed signal x_hat(n) in the time domain, we found aliasing, so
>>> we decide to move to 256 sampling points, so on and so forth.
>>
>> You can't detect aliasing by eye or any other way if you don't know the
>> original signal. Every set of samples represents one non-aliased signal
>> and an infinite number of aliased ones.
>>
>
>Why not? If I see 256 and 512 sample points do not yield visual difference,
>then I know 256 is a good number.

Unless they're both aliased with the aliased energy falling within the
first 256 points.
I don't see how that gets resolved until you've accumulated an
infinite number of points.
Theoretically, of course. In any practical system there will be
natural, unavoidable bandlimiting at some point. The number of
samples needed may still be completely impractical, though.
Eric Jacobsen
Minister of Algorithms
Abineau Communications
http://www.ericjacobsen.org

Reply by Vista●June 3, 20072007-06-03

"Jerry Avins" <jya@ieee.org> wrote in message
news:6MqdnVa99MXmYPzbnZ2dnUVZ_sWdnZ2d@rcn.net...

> Vista wrote:
>> "Jerry Avins" <jya@ieee.org> wrote in message
>> news:-OydnVWHs_4Kc_zbnZ2dnUVZ_hOdnZ2d@rcn.net...
>>> Vista wrote:
>>>> "Jerry Avins" <jya@ieee.org> wrote in message
>>>> news:haOdndxyQrQpR_zbnZ2dnUVZ_gSdnZ2d@rcn.net...
>>>>> Vista wrote:
>>>>>> Hi all,
>>>>>>
>>>>>> I need your help on the following difficulties:
>>>>>>
>>>>>> I am designing something like "automatic" detection of aliasing,
>>>>>> programmatically.
>>>>>>
>>>>>> For a given signal discrete time signal x(n), possibly infinite
>>>>>> support, we know its values are all positive, they are absolutely
>>>>>> summable, so DTFT exists and we know that the signal die down for
>>>>>> large n, and it can be roughly deemed as zero for some N and for all
>>>>>> n>=N.
>>>>>>
>>>>>> Now suppose we don't have the signal x(n) in the time domain, so we
>>>>>> don't know N, but we have its DTFT available, called X(w).
>>>>>>
>>>>>> The problem is to decide the smallest number of sampling point needed
>>>>>> to sample the X(w) in the frequency domain.
>>>>>>
>>>>>> Sampling X(w) will lead to aliasing and periodic overlapping of x(n).
>>>>>> But for a suitable number of sampling points (related to the unknown
>>>>>> N), the aliasing error can be controlled under a prespecified
>>>>>> threshold epsilon.
>>>>>>
>>>>>> Let's say we start with 128 sampling points, and by eye inspection of
>>>>>> the reconstructed signal x_hat(n) in the time domain, we found
>>>>>> aliasing, so we decide to move to 256 sampling points, so on and so
>>>>>> forth.
>>>>> You can't detect aliasing by eye or any other way if you don't know
>>>>> the original signal. Every set of samples represents one non-aliased
>>>>> signal and an infinite number of aliased ones.
>>>>>
>>>> Why not? If I see 256 and 512 sample points do not yield visual
>>>> difference, then I know 256 is a good number.
>>> What are you sampling if you have only the DTFT?
>>
>> As I said, I am sampling the DTFT in frequency domain in [0, 2*pi], and
>> then apply IFFT to reconstruct x(n) in time domain. And there is aliasing
>> depending on how many samples I use in sampling.
>>
>>>>>> How to automate the above eye inspection process? How to let computer
>>>>>> decide, programmatically, what is an aliased reconstruction and what
>>>>>> is not an aliased reconstruction? I hope to find a "quality"
>>>>>> function, which costs minimal amount of computations, based on which
>>>>>> the program can decide whether there is aliasing or not. The added
>>>>>> computational overhead has to be small because we have to run
>>>>>> millions of this type of "automatic" aliasing detector in real
>>>>>> time...
>>>>> Are you sampling in time or frequency? If you have the DTFT, then you
>>>>> have the highest significant frequency by inspection (once you decide
>>>>> what "significant" is).
>>>>>
>>>> As you see, I am sampling the DTFT X(w). And this is the sampling in
>>>> frequency. I want to detect the aliasing of time domain signal x(n) due
>>>> to frequency domain sampling on X(w).
>>> You can construe the frequency data as a time series and anti-alias
>>> filter it.
>>>
>>
>>
>> Good idea. Yes, filter in the frequency domain. However I first have to
>> decide how many samples do I use for [0, 2*pi].
>>
>> So you are talking about an analog filter or digital filter?
>
> Digital. I didn't imagine you had an analog DTFT. Is there such a thing?
>

If you apply a digital filter in the frequecy domain on the sampled X(w)
values, treating it as a time series, then you already sample it before you
apply the anti-aliasing filter. And our original question was exactly how
many samples do we need to sample the X(w) at the first place.
That's why I felt there is a problem with applying the digital filter...
Any more thoughts?