3
$\begingroup$

Is there a practical accelerated algorithm or a theoretical discrete (Fourier) transform based method to convolve discrete-time signals sampled on a logarithmic grid? What I mean is representing a discrete-time signal by the sequence:

$$[1, 1, 1],$$

as a shorthand notation for samples:

$$\big[\big(\log(1), 1\big), \big(\log(2), 1\big), \big(\log(3), 1\big)\big],$$

with autoconvolution:

$$[1, 1, 1]*[1, 1, 1]$$

$$=\big[\big(\log(1)+\log(1), 1\big), \big(\log(1)+\log(2), 1\big), \big(\log(1)+\log(3), 1\big)\big]+\\ \big[\big(\log(2)+\log(1), 1\big), \big(\log(2)+\log(2), 1\big), \big(\log(2)+\log(3), 1\big)\big]+\\ \big[\big(\log(3)+\log(1), 1\big), \big(\log(3)+\log(2), 1\big), \big(\log(3)+\log(3), 1\big)\big]$$

$$\begin{align}=&\big[\big(\log(1\times1), 1\big), \big(\log(1\times2), 1\big), \big(\log(1\times3), 1\big)\big]\\ +&\big[\big(\log(2\times1), 1\big), \big(\log(2\times2), 1\big), \big(\log(2\times3), 1\big)\big]\\ +&\big[\big(\log(3\times1), 1\big), \big(\log(3\times2), 1\big), \big(\log(3\times3), 1\big)\big]\end{align}$$

$$\begin{align}=&\big[\big(\log(1), 1\big), \big(\log(2), 1\big), \big(\log(3), 1\big)\big]\\ +&\big[\big(\log(2), 1\big), \big(\log(4), 1\big), \big(\log(6), 1\big)\big]\\ +&\big[\big(\log(3), 1\big), \big(\log(6), 1\big), \big(\log(9), 1\big)\big]\end{align}$$

$$\begin{align}=&[1, 1, 1, 0, 0, 0, 0, 0, 0]\\ +&[0, 1, 0, 1, 0, 1, 0, 0, 0]\\ +&[0, 0, 1, 0, 0, 1, 0, 0, 1]\\ \rule{0pt}{4ex}=&[1, 2, 2, 1, 0, 2, 0, 0, 1]\end{align}$$

The sequence notation is not affected by the choice of base of the logarithm. In an alternative representation, a sample $(\log(0),1) $ $=$ $(-\infty,1)$ could be added to the signal (appended to the beginning of the sequence), giving the pleasures of zero-based indexing without affecting the rest of the convolution result:

$$[1,1,1,1]*[1,1,1,1]$$ $$\begin{align}=&[4, 0, 0, 0, 0, 0, 0, 0, 0, 0]\\ +&[1, 1, 1, 1, 0, 0, 0, 0, 0, 0]\\ +&[1, 0, 1, 0, 1, 0, 1, 0, 0, 0]\\ +&[1, 0, 0, 1, 0, 0, 1, 0, 0, 1]\\ \rule{0pt}{4ex}=&[7, 1, 2, 2, 1, 0, 2, 0, 0, 1]\end{align}$$

I don't have a real application mind, but encountered such a convolution in the context of multiplication of discrete random variables. It is also interesting that if an infinite sequence of 1's would be log-sampling-convolved by itself, then the result would be the sequence OEIS A000005, the number of divisors of positive integers.

Improve this question
$\endgroup$
1
  • $\begingroup$ If I am getting it correctly, the tuple describes $(t, x(t))$. If that is the case, then a $\log(t)$ would imply an increasing $Ts$ and consequently a decreasing $Fs$. Unless $x(t)$'s bandwidth decreases slower than that with time, then maybe you can adapt an existing method. Otherwise, you very quickly run into aliasing territory. That is not to say that this is not interesting. Just pointing out that it might be approachable from a different route than DSP. $\endgroup$
    – A_A
    Commented Jan 13, 2019 at 10:41

0

Reset to default

Your Answer

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