6
$\begingroup$

Continuous Case

Let $ z \left( t \right) = \left( h \ast x \right) \left( t \right) $. What is the derivative of $ z \left( t \right) $ with respect to $ x \left( t \right) $?


Discrete Case

Given $2$ vectors $ x \in \mathbb{R}^{n} $ and $ h \in \mathbb{R}^{m} $, their convolution given by

$$ z = h \ast x $$

What would be the gradient of $ z $ with respect to $ x $? And what would be the gradient w ith respect to $ x $ of the following quadratic cost function?

$$ \frac{1}{2} {\left\| h \ast x - y \right\|}_{2}^{2} $$

$\endgroup$
8
  • $\begingroup$ The "derivative" is, in your case, taken in the sense of the differential calculus on Banach spaces. Roughly speaking, the map $x\mapsto z$ is a linear operator; I say "roughly" because we ought to specify a Banach space for $x$ and one for $z$. If this operator is continuous, then its derivative is itself. $\endgroup$ Aug 24, 2018 at 12:17
  • $\begingroup$ @GiuseppeNegro, For the Least squares problem you'd use the ad joint operator (Correlation). $\endgroup$
    – Royi
    Aug 24, 2018 at 12:50
  • $\begingroup$ In the discrete-time case, the convolution $h * x$ can be replaced by the matrix-vector product $H x$, where $H$ is a Toeplitz matrix whose diagonals contain the entries of $h$. Therefore, we have a standard least-squares problem. The normal equations $$H^\top H x = H^\top y$$ are interesting because $H^\top H$ is a Toeplitz matrix whose entries are values of the auto-correlation of $h$. Also, $H^\top y$ is the cross-correlation of $h$ and $y$. $\endgroup$ Aug 24, 2018 at 19:58
  • $\begingroup$ @RodrigodeAzevedo, I know the answer to that. But I thought there is a rigorous way, not using the matrix form, to derive the answer. $\endgroup$
    – Royi
    Aug 25, 2018 at 0:29
  • $\begingroup$ @Royi Why aren't the normal equations rigorous? If you want the continuous-time case, then switch the order of integration and eventually you obtain an equation with integrals that is the continuous-time equivalent of the normal equations. These integrals will contain autocorrelation and crosscorrelation functions. $\endgroup$ Aug 25, 2018 at 8:31

3 Answers 3

2
$\begingroup$

Discrete Case

For $ x \in \mathbb{R}^{n} $ and $ h \in \mathbb{R}^{m} $ (Assuming $ n \geq m $ The convolution is defined as:

$$ {y}_{n} = \sum_{i = 1}^{m} {x}_{n - i + 1} {h}_{i} $$

Hence

$$ \frac{ \mathrm{d} {y}_{n} }{ \mathrm{d} {x}_{j} } = \begin{cases} h \left[ m \right] & \text{ if } n - m + 1 = j \\ h \left[ m - 1 \right] & \text{ if } n - m + 2 = j \\ \vdots & \text{ if } \vdots \\ h \left[ 1 \right] & \text{ if } n - m + m = j \\ 0 & \text{ else } \end{cases} $$

As one could see, this flips the Convolution Kernel.
So the derivative is a matrix which in each row has a shifted version of the flipped kernel.

This matches the the Matrix Form of convolution:

$$ y = H x $$

Where $ H \in \mathbb{R}^{\left( n + m - 1 \right) \times n} $ is the convolution matrix with Toeplitz Form which suggests the gradient is given by:

$$ \frac{ \mathrm{d} {y}_{n} }{ \mathrm{d} {x}_{j} } = { \left( {H}^{T} \right) }_{j} \Rightarrow \frac{ \mathrm{d} y }{ \mathrm{d} x } = {H}^{T} $$

Where $ {H}_{j} $ is the $ j $ -th column of $ H $ (Hence $ { \left( {H}^{T} \right) }_{j} $ is the $ j $ row of $ H $).
The above is using the Denominator Layout for Matrix Calculus.

This also easily solve the Least Squares equation:

$$ f \left( x \right) = \frac{1}{2} {\left\| h \ast x - y \right\|}_{2}^{2} = \frac{1}{2} {\left\| H x - y \right\|}_{2}^{2} \Rightarrow \frac{ \mathrm{d} f \left( x \right) }{ \mathrm{d} x } = {H}^{T} \left( H x - y \right) = h \star \left( h \ast x - y \right) $$

Where $ \star $ is the discrete correlation operator (Convolution with the flipped kernel).

Remark
As Rodrigo de Azevedo noted, for $ y = h \ast x $ the function is Vector Function. Hence $ H $ is its Jacobian.

$\endgroup$
1
  • $\begingroup$ Well, the Gradient of vector function is indeed the Jacobian. Though I also derived the Gradient (For the Scalar Function). Anyhow, I added that as a remark. Thank You. $\endgroup$
    – Royi
    Aug 25, 2018 at 15:16
1
$\begingroup$

Given $h : \mathbb R \to \mathbb R$, let

$$z (t) := (h \ast x) (t) = \int_{\mathbb R} h (t - \tau) \, x (\tau) \,\mathrm d \tau$$

Fixing $t$, say, $t = t_0$, we obtain a functional that takes $x : \mathbb R \to \mathbb R$ and returns $z (t_0) \in \mathbb R$

$$z (t_0) = \int_{\mathbb R} h (t_0 - \tau) \, x (\tau) \,\mathrm d \tau = \langle (\mathcal S_{t_0} \circ \mathcal R)(h), x \rangle$$

where $\mathcal R$ is the reversal operator and $\mathcal S_{t_0}$ is the shift-by-$t_0$ operator. Therefore, the functional derivative of functional $z (t_0)$ is $(\mathcal S_{t_0} \circ \mathcal R)(h)$, i.e., the reversed-then-shifted version of $h$.

$\endgroup$
5
  • $\begingroup$ This is some useful information. Actually when I was reading the question, I was thinking about the derivative of the operator itself though (i.e. Jacobian-like). $\endgroup$
    – Vim
    Aug 25, 2018 at 15:49
  • $\begingroup$ @Vim Yes, that would be nice. I chose to keep it simple and close to calculus of variations. $\endgroup$ Aug 25, 2018 at 15:56
  • $\begingroup$ @Vim "Un-fixing" $t$, could one say that the "functional Jacobian" is $(\mathcal S_t \circ \mathcal R)(h)$? $\endgroup$ Aug 25, 2018 at 16:04
  • $\begingroup$ yes I think so. Well it seems we're talking about the same thing then. Your result actually agrees with mine: the functional derivative or functional Jacobian is just the map $x\mapsto h*x$ itself isn't it? $\endgroup$
    – Vim
    Aug 25, 2018 at 16:19
  • $\begingroup$ @Vim I wouldn't say it's the map itself. Convolution is an integral. What I got requires no integral. Using a vector analogy, it's the difference between the inner product $\rm \langle c, x \rangle$ and vector $\rm c$. However, if we think in terms of directional derivatives... $\endgroup$ Aug 25, 2018 at 16:34
0
$\begingroup$

Note that the operation $$f: x\mapsto (t\mapsto z(t):=(h*x)(t))$$ is linear in $x$, so the derivative of $f$ in $x$ is just itself. (For analogy think about finite dimensional spaces and matrices.)

For the discrete case, note that you can easily view the vectors $z,h,x$ just as functions on the domain $\Bbb R$: let's say originally the vector $h=(h_1,\cdots,h_m)^T$, then you can identify $h$ with a function $$\hat h:\Bbb R\to\Bbb R,\quad t\mapsto \sum_{i=1}^m I(t=i)h_i$$ where $I$ is the indicator function. Likewise you can identify $\hat x, \hat z$. You'll then find that, under such identifications, the so-called "discrete case" is trivially compatible with the "continuous" case. So the derivative is the map $x\mapsto h*x$ itself, or just $H$ if you use Toeplitz matrix $H$ to represent the convolution.

$\endgroup$
9
  • $\begingroup$ How does it align in the case of Discrete? Clearly then the Gradient is composed of the flipped kernel. $\endgroup$
    – Royi
    Aug 25, 2018 at 11:08
  • $\begingroup$ @Royi sorry my answer didn't discuss discrete cases. $\endgroup$
    – Vim
    Aug 25, 2018 at 11:21
  • $\begingroup$ I'd assume that if in the Discrete case the Kernel is flipped then it would also be flipped in the Continuous case. $\endgroup$
    – Royi
    Aug 25, 2018 at 11:42
  • $\begingroup$ @Royi it seems there's a misunderstanding. The OP is asking about the derivative in $x$ not in $t$. $\endgroup$
    – Vim
    Aug 25, 2018 at 12:13
  • 1
    $\begingroup$ If you see my answer this is what I answered to. I was totally aware of that. I'm pretty sure that in continuous framework the result should be the flipped version of $ h $. $\endgroup$
    – Royi
    Aug 25, 2018 at 12:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .