4
$\begingroup$

I want to convolve discrete signals A and B. I can compute their energies beforehand by squaring the samples and summing the squares, but I'm curious if I can compute the energy of the signal I will get if I convolve A and B using their energies (or anything about them really) without even doing convolution? Is there any mathematical relationship there?

$\endgroup$
3
  • 1
    $\begingroup$ I think the best you can do is to find an upper bound on the energy of $A * B$ -- think in terms of B being a unity-gain filter with a certain bandpass. Then the most energy that $A * B$ can have is if $A$'s energy is all concentrated in $B$'s bandpass, and the energy of $A * B$ is equal to the energy of $A$. But if $A$ has energy outside of $B$'s bandpass, $A * B$ will have less energy than $A$. Trying to turn that intuition into math makes my head explode, however. $\endgroup$
    – TimWescott
    May 7, 2022 at 14:25
  • $\begingroup$ I've added some new bounds. $\endgroup$ May 11, 2022 at 17:03
  • $\begingroup$ Are A and B knowns? Is it theoretical question or in practice you're trying to preserve some computational efforts? $\endgroup$
    – Royi
    May 16, 2022 at 20:52

3 Answers 3

5
$\begingroup$

Probably not an equality directly, but upper bounds. Let us look at the continuous case first, which is easier to derive. There is a Young's convolution inequality: with proper integrability conditions ($A$ is $L_p$ integrable, $B$ is $L_q$ integrable), $1\le p,q\le\infty$ and conjugation: $$\frac{1}{p}+\frac{1}{q}=\frac{1}{r}+1\,.$$

On the one hand then: $$\|A\ast B \|_r \le c_{p,q} \|A \|_p \|B\|_q$$

for some constant $c_{p,q}$ that can be computed. On the other hand, there are non-zero vectors whose convolution vanishes, see When does the convolution of 2 signals equal zero?. Therefore, knowing something about $A$ and $B$ separately won't get you a precise idea about their convolution: you can hope for lower and upper bounds, but no equality. If you are only interested in the energy of the convolution, set $r=2$.

In the discrete case, with standard or circular convolution, I remember that results were more complicated to derive, but you can hope for inequalities as well (see works of Beckner and related, like Optimal Young's inequality and its converse: a simple proof.

$\endgroup$
1
  • 1
    $\begingroup$ ha! Beautiful! That's exactly the motivation for matched filtering! $\endgroup$ May 7, 2022 at 12:03
1
$\begingroup$
a = ones(64,1);
b = [1 -1];
c = conv(a,b);

In this case, a and b have some non-zero energy while their convolution is exactly zero besides head and tail conditions.

$\endgroup$
3
  • $\begingroup$ With circular convolution, I guess $\endgroup$ May 7, 2022 at 10:47
  • $\begingroup$ Not to be picky here, but your variable c is NOT all zeros. $\endgroup$
    – Hilmar
    May 7, 2022 at 17:01
  • $\begingroup$ I did say except head and tail conditions, @Hilmar? $\endgroup$
    – Knut Inge
    May 7, 2022 at 17:08
-1
$\begingroup$

We can get exact bounds from cross-domain energy relations. Given a signal $x(t)$ and a kernel $h(t)$ to convolve with, the frequency-domain result is $X(f)H(f)$, and we know from Parseval-Plancherel's theorem that

$$ ||x * h|| = ||XH||. $$

Suppose

$$ A \leq |H(f)|^2 \leq B $$ that is, the energy of any frequency of $h$ is bound between $A$ and $B$. Then, multiplying by $|X(f)|^2$, we get

$$ A |X(f)|^2 \leq |H(f)X(f)|^2 \leq B |X(f)|^2 $$

applying integration,

$$ A \int |X(f)|^2 \leq \int |H(f)X(f)|^2 \leq B \int |X(f)|^2 $$

then the theorem

$$ A \int |x(t)|^2 \leq \int |x * h|^2 \leq B \int |x(t)|^2 \\ \Leftrightarrow \\ A||x||^2 \leq ||x * h||^2 \leq B ||x||^2 \\ $$

which is

$$ \boxed{\text{min}(|H(f)|^2) ||x||^2 \leq ||x * h||^2 \leq \text{max}(|H(f)|^2) ||x||^2} $$

Hence, the energy of convolving with $h$ is bound by the minimum and maximum of energy of any frequency of $h$. Since $x * h = h * x$, one can repeat this argument starting with $X(f)$:

$$ \boxed{\text{min}(|X(f)|^2) ||h||^2 \leq ||x * h||^2 \leq \text{max}(|X(f)|^2) ||h||^2} $$

This holds in both continuous and discrete domains, where the discrete energy relation is

$$ \sum_{n=0}^{N-1} |x[n]|^2 = \frac{1}{N}\sum_{k=0}^{N-1} |X[k]|^2 $$

Without going to frequency domain, working with time-domain energies alone, we can't tell much, as the energy can exceed $||x||^2 \cdot ||h||^2$ or even be zero while neither's energy is.

Example

We can have $||a|| > 0$ and $||b|| > 0$ while $||a * b|| = 0$:

import numpy as np
from numpy.fft import fft, ifft

def E(x):
    return np.sum(np.abs(x)**2)

x = np.random.randn(128)
x -= x.mean()
h = np.ones(128)
conv = ifft(fft(x) * fft(h))

assert np.allclose(conv, 0)
print(E(x), E(h), E(conv))
117.73576304545941 128.0 1.6155871338926322e-27

because $\text{min}(||X[k]||^2) = 0$ (the DC bin, due to x -= x.mean()). Note, this is for circular convolution, but since we can reformulate it as an exact equivalent of linear, one simply needs to account for spectral effects of zero padding to derive a similar relation (and since zeros don't add energy, the upper bound won't change).

Empirical validation of bounds

We trial many examples of a constant convolved with complex white noise, compute distances with upper and lower bounds, and report minimum distances for each:

def E(x):
    return np.sum(np.abs(x)**2)

np.random.seed(0)
dists_min, dists_max = [], []
N = 1024
for _ in range(1000):
    x = np.ones(N)
    h = np.random.randn(N) + np.random.randn(N)*1j
    xf, hf = fft(x), fft(h)
    
    mn, mx = np.min(np.abs(hf)**2), np.max(np.abs(hf)**2)
    Ex = E(x)
    
    cconv = ifft(xf * hf)
    dists_min.append(E(cconv) - mn*Ex)
    dists_max.append(mx*Ex - E(cconv))

print(np.min(dists_min), np.min(dists_max))
-9.094947017729282e-13 3.725290298461914e-09

The upper bound is always strictly met, while the lower bound fails only within float precision. If both signals are noise, we're much more within bounds.

$\endgroup$
3
  • $\begingroup$ I see where you're going with $E(a * b) = \frac{1}{N}E(AB)$, but if you're using $E(\cdot)$ to denote the energy of something, then I'd go with $E(x) = E\left (\mathcal F \{x\}\right)$ by definition, and, hence, $E\left( \mathcal F \{x\} \right) = \frac{1}{N} \left \| \mathcal F \{ x \} \right \|$ -- even if it's a bit more confusing on the surface. $\endgroup$
    – TimWescott
    May 7, 2022 at 13:59
  • $\begingroup$ @TimWescott Is it by definition for DFT? For CFT, we get $1/2\pi$ with $\omega$, though DFT does $2\pi k$ analogous to CFT's $2\pi f$. Question is, is energy defined as $\sum |\text{stuff}|^2$, or it only happens to work out in time domain (if so, what's the actual definition)? I could open a question $\endgroup$ May 7, 2022 at 14:35
  • 1
    $\begingroup$ I think it's worth a question. It does get a bit philosophical, but I think that for signal processing you want the time domain energy to be $\sum | \text{stuff} |^2$ or $\int |\text{stuff}|^2 dt$, and you want the frequency domain energy for a given signal to calculate out to the same number as the time-domain signal. $\endgroup$
    – TimWescott
    May 7, 2022 at 16:14

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.