I have two datasets $X_1$ and $X_2$ in a sparse wavelet basis, and I have two filters $f_1$ and $f_2$. I’d like to compute the inner product of the convolutions $$\langle X_1 \star f_1, X_2 \star f_2\rangle$$ in the sparse wavelet basis. How do I this?

Thanks! James

  • $\begingroup$ Did you find ideas in Efficient computation of dot product of convolutions? $\endgroup$ – Laurent Duval Dec 2 '20 at 9:16
  • $\begingroup$ I don’t believe this answers my question. I have access to the wavelet transform of X1 and X2. So it’s not obvious to me how to compute the inner product of the filtered signals in the sparse domain. In other words I’m asking about the relation between convolution and the wavelet transform and if that destroys the sparsity of the system. Does that make sense? $\endgroup$ – James Pinkerton Dec 2 '20 at 9:32
  • $\begingroup$ Not fully yet: $X_i$ are already computed and are wavelet coefficients of signals $x_i$? How are they arranged in a vector? $\endgroup$ – Laurent Duval Dec 2 '20 at 9:39
  • 1
    $\begingroup$ Sure let’s use your notation. Say $x_i$ is the original signal. I want to compute $<x_1 * f_1, x_2 * f_2>$. Let’s say $X_i$ is a sparse dictionary representing the wavelet transform of $x_i$. The goal is to do the computation in the sparse world to save on compute cost. The computation in the non-sparse world is too expensive (that was the point of sparsifying!). $\endgroup$ – James Pinkerton Dec 2 '20 at 9:45
  • $\begingroup$ So I give you $X_1, X_2$ and the closed form formula for $f_1, f_2$ as inputs. If the answer is start by taking an inverse wavelet transform of $X_1$ and $X_2$ then you’ve already lost since you’re not sparse anymore :D and the computation is too expensive. (The reason it’s too expensive is I actually have a large number of dimensions and I’m computing a covariance matrix, not just a single inner product) $\endgroup$ – James Pinkerton Dec 2 '20 at 9:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.