# ReLU gradient descent matrix dimensionality

If I'm backpropagating through a recurrent neural network, say my layer output is $$h_t = \text{ReLU}(U h_{t-1} + V x_t),$$ when calculating the gradient my dimensions don't seem to be coming out properly. I'm looking to take the gradient of h with respect to $h_{t-1}$ which I'm assuming is $$\frac{\partial h_t}{\partial h_{t-1}} = \frac{\partial \text{ReLU}(A)}{\partial A}\frac{\partial A}{\partial h_{t-1}}$$ where $$\frac{\partial A}{\partial h_{t-1}} = \frac{\partial (U h_{t-1} + Vx_t)}{\partial h_{t-1}} = \frac{\partial (U h_{t-1})}{\partial h_{t-1}} = U^T$$ (in denominator notation).

If $h \in \mathbb{R}^n$ I would expect $\partial h_t/\partial h_{t-1}$ to have dimensions $[n \times n]$, however I believe $\frac{\partial \text{ReLU}(A)}{\partial A}$ has dimensions $[n \times 1]$ and I know U^T has dimensions $[n \times n]$, so those two obviously can't be multiplied in any way to get a final dimension $[n \times n]$. Any suggestions?

The derivative of the ReLu in terms of $A$ is actually $n\times n$. This is because $A$ has n dimensions, and so does the output. I think maybe you thought that $A$ is a scaler, but in fact it's a scaler in each of its components. Also don't forget that the derivative of the ReLu in component $ij$ is 0 whenever $A_j<0$.
The derivative of the ReLu function is the Heaviside step function $$\frac{dr(a)}{da} = s(a) =\begin{cases} 1 &\text{if } a \ge 0 \\ 0 &\text{otherwise} \end{cases}$$ Note that I've used $s(a)$ for the step function instead of the more standard $H(x)$ because the symbols $(h,x)$ have other meanings in this problem. I also want to use the convention where uppercase Latin letters represent matrices, lowercase Latin are vectors, and Greek letters are scalars.
When applied element-wise to a vector argument, the differential of the ReLu function can be written using the element-wise (aka Hadamard $\circ$) product as $$dr=s\circ da$$ For this problem, we have \eqalign{ a &= Uh+Vx_+ \cr s &= s(a) \cr h_+ &= r(a) \cr } Now find the differential and then the gradient of the function \eqalign{ dh_+ &= s\circ da = s\circ(U\,dh) \cr &= \Big({\rm Diag}(s)\,U\Big)\,dh \cr \frac{\partial h_+}{\partial h} &= {\rm Diag}(s)\,U \cr }