2
$\begingroup$

For the following I use the terms “time domain signal” and “frequency domain signal” as a Fourier Transform pair. The question is for generalized cases of continuous-time signals that once sampled in the time domain will then be discrete-time signals. I will also use the phrase “sampling in the frequency domain” which refers to selecting samples of a continuous frequency spectrum, which occurs in the Discrete Fourier Transform as one example, but also occurs for any signal that repeats periodically in time at period $T$ seconds: “sampling in the frequency domain” meaning the only non-zero values that can exist in the frequency domain will be spaced at frequency $1/T$ Hz including “DC” (f=0). I state all this to make my description of the question clearer and to provide a generalized description on what “time-domain aliasing” is, specifically to the sampling process of signals.

With that in mind, frequency domain aliasing occurs when we sample in the time domain a time-domain signal with a frequency domain “duration” (which itself is bandwidth) that exceeds half the sampling rate for real signals, and more generally that exceed the sampling rate for complex signals. The “sampling rate” is the reciprocal of the spacing between successive samples in time. For practical purposes in managing distortion, I am considering aliasing below a defined level to be “no aliasing”, since we could argue mathematically that some aliasing will always occur (and that is not what this question is getting at).

“Time domain aliasing” is simply the same process, just swapping time and frequency, given the reciprocal time - freq properties of the Fourier Transform. With similar consideration given above, time domain aliasing occurs when we sample in the frequency domain a frequency domain signal (a complex spectrum) with a time-domain duration that exceeds the reciprocal of the spacing beteeen successive samples in frequency. (If that isn’t immediately clear, first reread the frequency domain aliasing paragraph to see the parallel and then read the next paragraph where I provide more details on time-domain duration). For periodic signals in time with period $T$, this spacing in frequency is $1/T$. More generally we consider the spacing for discrete spectrums whenever they exist, which is the over-arching reason to consider the associated time domain aliasing effects with the conditions above.

Our concern with time domain aliasing typically comes about with the association between the impulse response of a system and it’s frequency response, as the two are Fourier Transform pairs. The impulse response IS the time domain duration referred to above: if the duration of the true impulse response for a continuous-time system exceeds the spacing between successive samples in frequency when the frequency spectrum for that system is sampled, time domain aliasing will occur. In the context of filtering, it is the impulse response of the filter that convolves with the input time-domain signal to the filter that creates the output time-domain signal. Convolution in time is a product in frequency, so filtering and “fast convolution” can be done efficiently using the FFT with additional consideration to the resulting circular convolution and its time-domain aliasing effects.

My question then is if we could we have conditions where time domain aliasing occurs but it is impossible for a peak to get introduced in the resulting time domain response? A “peak” meaning the time response rises and falls before the conclusion of the observable unique time response (if the “sampling in frequency” occurred due to periodicity in time, the “observable unique time response” would be one period).

$\endgroup$
17
  • $\begingroup$ (context: question motivated by my comment) To be clear, I referred to "time aliasing" in context of filtering (convolving). My exact claim is, circular convolution cannot cause peaks that don't already exist with linear (zero-padded) convolution, "peak" defined as a value >x2 the max of a peakless result (the higher, the more impossible). Time aliasing of a general waveform can absolutely create peaks, just sample the other domain more spaced out-ly. The one-waveform-equivalent of my context, however, is constrained in a way that makes this impossible. If this is of interest, I can answer. $\endgroup$ May 25, 2023 at 4:04
  • 2
    $\begingroup$ I'm still trying to decode this. I wish you would pose the question more strictly with mathematical expression. BTW, when sampling both in the time domain and in the frequency domain, you can't really use the same "$T$" (or "$\frac{1}{T}$" in frequency). For instance, with the DFT, if $T$ is the sampling period in the time domain, then $\frac{1}{NT}$ is the sampling spacing in the frequency domain, which is much denser sampling than if it were $\frac{1}{T}$. $\endgroup$ May 25, 2023 at 17:09
  • $\begingroup$ Is this about the uncertainty principle? Like in optics? That, given a certain sampling interval, when two peaks get close enough together that they blur into a single peak that cannot be discriminated from the other? $\endgroup$ May 25, 2023 at 17:12
  • $\begingroup$ Lastly (for now) I will say what I intended to at the beginning. We know, from the sampling theorem, that uniform sampling in one domain (say, with a sampling interval of $\Delta$) causes periodic extension in the other domain. That periodic extension in the other domain infinitely repeats and shifts the function of whatever ("time" or "frequency") by intervals of integer multiples of $\frac{1}{\Delta}$ and overlap adds all of those images. There is a scaling factor of $\Delta$ or $\frac{1}{\Delta}$ to worry about, but I am not worrying about it here. $\endgroup$ May 25, 2023 at 17:20
  • 1
    $\begingroup$ @Ash yes iI believe it makes sense to distinguish, they are two different effects with different considerations- time domain aliasing explains why using the inverse DFT to create an FIR filter from a sampled frequency domain transfer function is inferior to least squares FIR filter design for example. I have another post here that I believe demonstrates that and can dig it up if that interests you. Frequency domain aliasing explains why we need an anti-aliasing filter in front of an A/D converter, two different effects. $\endgroup$ May 25, 2023 at 22:03

1 Answer 1

0
$\begingroup$

Here I answer the question, "Can time aliasing in convolution cause peaks?". It showed up in a recent question, Random Peak at the end Impulse Response, where users suggested time aliasing as a potential cause. The answer is - meaningfully, "no" - strictly, "no" for 'full' as the reference convolution, and "yes" for 'same' but the "caused" peak should be there. That's per a major definition of "peak" - a general discussion is in a later section ("Mini-peaks?"), but long story short: if in doubt, try non-circular convolution, but if the peak is the absolute maximum, it probably should be there.

Convolution is a locally stable operator: outputs close in time are correlated, and most filters will prohibit "wild variations". It's an intuition that can be formalized - instead, I prove the exact claim.

My implied and equivalent claim is, "circular convolution cannot cause peaks that don't already exist with a linear (zero-padded) convolution". What this means is, if we take sequences $a$ and $b$ that are separated in time, with more zeros between them than the filter's support; $a$ is left, $b$ is right. The "yes" case means that joining these sequences can create a peak, without peaks already being created by convolving with the separated $a$ and $b$.

The 'same' vs 'full' distinction is due to the "peaks already being created" part; circular cross-correlation cannot make peaks that are already present in 'full' convolution, but it can make peaks that are not present in 'same' convolution; put differently, if the existing peaks are located inside of bounds defined by 'same' convolution, then circular cross-correlation cannot make new peaks.

For those who want a quick read, the proof actually ends in equivalently three sections, as will be stated.

The setup, and Case 0

On left, we begin with a certain summation - $\sum_n a[n] \cdot h[n]= K_1$. If we slide the filter left, we get another summation, that's potentially larger - the greatest potential is with it fully inside, producing an identical output vs. joined case. Now imagine sliding $b$ closer and closer left. As it begins to overlap $h$, the sum becomes $K_1 + \sum_n b[n] \cdot h[n] = K_3$. Let $K_2$ be the result with the filter over $b$'s edge (still unjoined). Clearly, $K_3 = K_1 + K_2$.

We define "peak" as a value that's more than double the next highest value - put differently, "a peak is a point with more than double the max value of a sequence without the peak". Now, clearly, $|K_3| \leq |K_1| + |K_2|$. To simplify, let all be positive. The highest value that $K_3$ can be, is if $K_1$ and $K_2$ are both maxima of the respective outputs. Following our definition of "peak", since $K_3 = K_1 + K_2$ and $K_1$ and $K_2$ are the maximum and next-maximum (or vice versa) of the convolution before joining, the best case scenario is if $K_3 / \texttt{max}\{K_1, K_2\}$ is maximized, which is achieved with $K_1 = K_2$. This makes $K_3$ exactly double the next maximum.

Now it's possible to skip to "Finalizing" and/or "Alternative proof", then "Out-of-bounds case" to end the proof, and "Peaks odds" and "Mini-peaks?" for extra info. I dug in arithmetic details before I took a bird's-eye view, and it took long enough. But below maybe has more insight.

Other shift cases

To see if better can be done, we exhaust our options. For now, assume $a,b,h\geq 0$.

  1. $K_1$ and/or $K_2$ aren't maxima. Then the ratio of $K_3$ to the existing maximum is even lower.

Let $J_1, J_2$ be $K_1, K_2$, except the filter is to left of $a$'s edge and to right of $b$'s edge by in respective cases, by arbitrary amounts but never fully inside of either so that joining makes a difference. In the joined case, let $s_1$ be the contribution from $a$, and $s_2$ from $b$, in the multiply-sum with $h$, for any arbitrary case, and $s_3 = s_1 + s_2$ (by definition). Note, now $J_3$ doesn't necessarily equal $J_1 + J_2$; they by definition correspond to arbitrary and independent shifts of $h$.

  1. Let $s_1=J_1$ and $s_2=J_2$. This is same as "Case 0".
  2. Let $J_1, J_2$ be maxima of convolutions with $a, b$, and let $s_1=J_1$ and $s_2 < J_2$. Since the best case is $J_1 = J_2$, hence $s_1 = s_2$, this cannot be double or more of $\texttt{max}\{J_1, J_2\}$.
  3. Case 3, except $s_2 > J_2$. This is impossible by definition.
  4. Let neither of $J_1, J_2$ be maxima of convolutions with $a, b$, but let them be maxima within the filter's support with respect to each edge. Since by definition $s_1 \leq J_1$ and $s_2 \leq J_2$ and the maximum $s_1 + s_2$ is $J_1 + J_2$, yet there's points greater than $J_1, J_2$, $J_1 + J_2$ can never reach double the maximum.
  5. Case 5, except $J_1, J_2$ aren't maxima within the filter's support with respect to each edge. This is a contradiction, such maxima exist per how $J_1, J_2$ are defined.
  6. Redefine $s_1$ to permit shifting $h$ to left of $a$ by more than the support of $h$, but $s_2$ stays the same. Then $s_2=0$, and $s_1$ can never exceed the existing maxima of convolutions with the unjoined $a, b$.
  7. Case 7, except swap $s_1, s_2$, same conclusion.

This exhausts every possible location of $h$ before or after $a$ and $b$ are joined, and all pre-join proximities of $a$ to $b$. That's all possibilities. Except, we've assumed $a, b, h \geq 0$.

Arbitrary $a, b, h$

The case for $a, b, h \leq 0$ is completely analogous, with the definition of "peak" amended by replacing "maximum" with "absolute maximum". Now let $a,b,h$ be anything, except complex-valued for now. If all positives (or sign-aligned) case is the best possible case, then all that remains is to prove that.

The proof is simple: if signs for any $a[n_1], h[n_1]$ or $b[n_2], h[n_2]$ aren't aligned, then they're opposite, meaning the sums are less than they would be with alignment: $\left|a[n_1]h[n_1] + b[n_2]h[n_2]\right| < \left|a[n_1]h[n_1]\right| + \left|b[n_2]h[n_2]\right|$. For the general case where we don't know of alignment status, $<$ becomes $\leq$. Hence, $|s_1 + s_2| \leq |s_1| + |s_2|$ in all cases above, yet above is $|s_1 + s_2| = |s_1| + |s_2|$. Since all of the above always strives to maximize $|s_1 + s_2|$, and the general case can do no better, this proves that the sign-aligned case is the best case, and that case itself has been proven, which exhausts all real-valued possibilities.

Now for complex values. Again, it suffices to prove that it's upper-bounded by real-valued sign-alignment. For this, we realize that positive real values are sign-aligned and phase-aligned complex values, whose absolute product doesn't care, but whose absolute sum is strictly greater than with sign-unaligned or phase-unaligned complex values, and hence likewise sum of products.

Finalizing

Thus, or rather it's all a long way of saying,

$$ |s_1 + s_2| \triangleq \left|\sum_{n=0}^{N_a - 1} h[n] a[n] + \sum_{n=N_a}^{N - 1} h[n] b[n] \right| \leq \sum_{n=0}^{N_a - 1} |h[n] a[n]| + \sum_{n=N_a}^{N - 1} |h[n] b[n]| $$

and

$$ \sum_{n=0}^{N_a - 1} |h_{nn}[n] a_{nn}[n]| + \sum_{n=N_a}^{N - 1} |h_{nn}[n] b_{nn}[n]| = \sum_{n=0}^{N_a - 1} h_{nn}[n] a_{nn}[n] + \sum_{n=N_a}^{N - 1} h_{nn}[n] b_{nn}[n] $$

where $a_{nn}, b_{nn}, h_{nn} \geq 0$, and,

$$ \frac{|s_1 + s_2|}{\texttt{max}\{|a * h|, |b * h|\}} \leq 2 $$

which finally, per Cases 7 & 8, is same as

$$ \boxed{ \frac{\texttt{max}\{|[a, b]*h|\}} {\texttt{max}\{|a * h|, |b * h|\}} \leq 2 } $$

In words, convolution of a filter with the sequences joined can't have a value that's more than double the max value of convolution of a filter with the sequences separately.

Of course, by "peak", we usually mean something that's much more than just double the next-highest value - which is, of course, much more than what's already impossible. And, by "peak" we also mean more than just a single point - which just means amending the definition of "next maximum" to exclude all such points, which only lowers the reference "maximum" in above cases. This of course allows exceeding $2$, but not by a factor greater than the ratio of the actual next-maximum to new next-maximum, which simply exposes an oversimplification in the technicality of the definition: we still cannot create peaks that weren't already there.

The proof in continuous time is completely analogous, barring functions that warp reality and break space-time continuum. This concludes the proof.

Interestingly, while time aliasing in convolution cannon create peaks, it can very much destroy them: $K_1 = -K_2$.

Alternative proof

Output of convolution of the joined sequence equals the overlap-adding of outputs of the separate convolutions, which can at best double the maximum of either separate output. I didn't realize this immediately because I'm not very smart.

Out-of-bound case

The exhaustive proof forgot to amend the definition of "peak" to handle an important practical case: the peak being centered to right of $a$ and to left of $b$, but the "reference convolutions" with $a$ and $b$ excluding such points.

Consider the convolution of $e^t$, that's zero past some $t > t_0$, with itself; another remark is that our math so far was based on cross-correlation, and it didn't matter, but it does now. Let $a = h = e^t$, and forget $b$. At the right edge, we're looking at $e^t$ vs $e^{-t}$; now, the difference between the final output point of 'same' and 'full' is colossal. Circular convolution is same as joining $b = a$ onto $a$; the 'full' tails of both will fully overlap. In this example, the joining isn't what causes the peak, but simply the equivalent output domain extension; circ-conv always operates per 'full' in the sense that it guarantees a complete sweep over every input point.

In fact, this is always the case; joining cannot cause peaks - per "Alternative proof", we're just overlap-adding the bounds' tails. So only completed sweeps can cause peaks - and since the full-information convolution is meant to complete the sweep, this cannot be considered a "distortion". Put differently, the peaks cannot be caused by the filter "wrongly interacting" with the joined segment - if the peaks are there, they should be there.

The peak potential is unbounded; let $a=h=$ unit impulse on right edge; 'same' output is zero, 'full' and circular is non-zero, ratio $= \infty$.

Peaks odds

There's little guesswork - the answer to "did time aliasing cause peaks" is same as to "are there peaks near edges of left-zero-padded 'full'" (because, 'full' only fully sweeps to the right of input, not left) - or more precisely, outside of bounds of 'same'. A more important question is, should the "caused" peak be there - per the general definition of convolution, there's no such thing, but practically, it depends on whether the "completed sweep" isn't something that should be happening.

The more precise criterion is, "within $h$'s half-support of 'same''s bounds", since that's how much 'same' discards relative to the left-zero-padded 'full'.

Mini-peaks?

We get it, no new dramatic absolute maxima. What of simply sharp rise-falls, or pulses? All hell breaks loose if we don't define these precisely, but let's just say, if you're worried about detrimental peaks of any sort, try non-circular convolution. But if the peaks aren't within $h$'s full support of the boundaries, it can't possibly be the cause, in any sense at all!


Below, any convolution discussion doesn't concern itself with 'same', only 'full'.

Can time aliasing (general) cause peaks?

Absolutely: Subsampling in time <=> Folding in Fourier. "Folding" is fancy for "overlap-add", and addition is unbounded - so just subsample more, or sample more sparsely, in other domain, to explode the other domain.

"But by convolution theorem, $x*h \Leftrightarrow X\cdot H$, and $Z=X\cdot H$ can be anything?" $X\cdot H$ can't be anything. The continuous-time equivalent is for $x$ to be a joining of $a, b$, and "joining" means not overlapping, which constrains $X$ in terms of $A$ and $B$, and the objective is defined in terms of $X, A, B$. In discrete-time (infinite discrete), it means the amount of permitted time aliasing is limited - note, $s_1 + s_2$ is identically the overlapping of the outputs of the separate convolutions with $a, b$.

Fourier arguments (failed)

I initially tried to prove this by working purely in Fourier domain. It either can't be done, or I've not managed - the Fourier domain is too general and there appears to be no clear way to encode the given restriction (except, I suppose, in the way I did in the previous section, but that doesn't handle CT or D). Just for sake of informativeness, I describe some of it.

The setup is $O_s(\omega) = H(\omega) \cdot \left(A(\omega) + e^{-j\omega s}B(\omega)\right)$, where $s$ is the amount of shift, and $a(t), b(t)$ are originally separated by more than the support of $h(t)$. The idea is to run metrics on $s=0$ (unshifted) vs joined, $s_j = -\texttt{supp}\{h\}$. We don't know what $s_j$ is, and it doesn't matter (for what I tried), but we know $|s_j| > 0$. Failed:

  1. Find $\texttt{max}\{|o(t)|\}$ as described here - unbounded ratio in absence of constraints
  2. Parseval-Plancherel's theorem: forgot, something about bounding and uninformativeness
  3. (1) but using $|O_s(\omega)|$ - this went far, but failed, and I forgot why for both
$\endgroup$
12
  • $\begingroup$ Thank you! This does appear to answer the question with some good analysis, will just take me a while to read through carefully to digest. Just curious with the suggested title change and what I noticed from your earlier use, I suspect you don't like the term "time-domain aliasing" and prefer "time aliasing" specifically. Did you see an issue with "time-domain" and "freq-domain" as the description of the two different aliasing considerations? $\endgroup$ May 26, 2023 at 21:56
  • $\begingroup$ I'm going to make temporary comments that jump out at me as I read - which we can delete once resolved to reduce the number of comments as DSP.SE encourages. 2nd paragraph: "... outputs close in time are correlated, and most filters will prohibit "wild variations". It's an intuition that can be formalized - instead, I prove the exact claim." Outputs close in time may be correlated, but they can also be completely independent even after filtering. A low pass filter will create correlation from sample to sample but a high pass filter will not necessarily do this. $\endgroup$ May 26, 2023 at 22:16
  • $\begingroup$ I'm not really sure what is getting shown in the first graphic. It would help to label what is a, b and the filter. I think the bottom part of the graphic is intended to be the convolution result, but not sure on that since it really wouldn't look that way (the gap would be much smaller and not aligned with the start and stop of the sequence as shown, and if that is the filter the result would transition to zero on each side of the gap.) And what exactly is $K_1$, $K_2$ and $K_3$ in the graphic? Just one sample at a particular overlap of h with the sequence or is it the resulting function? Or? $\endgroup$ May 27, 2023 at 11:47
  • $\begingroup$ Thanks for defining your "peak". I defined peak in my question which sounds very different. Your initial statement "time aliasing cannot cause peaks" from your other post caught my interest with that in mind. So to confirm, if using my definition, the statement "time aliasing cannot cause peaks" is not true? $\endgroup$ May 27, 2023 at 12:33
  • 1
    $\begingroup$ When I write long posts, I write the bottom-most part at top so I can see render in real-time, and then when I put them in the right order, apparently I've cut out the explanation of the plot... Yes you're right, and $a, b$ is just left and right, and blue is $h$. The peak is defined as the convolutional output absolute maximum within the full support of $h$ from each edge. If interpreting the answer right, one also sees many other kinds of peaks are eliminated, but not all - to contrary, some are very much caused. I'll get back to this. $\endgroup$ May 28, 2023 at 8:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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