# Derivative of vector with vectorization

I have these constraints on a cost function

$$c = A+Bx=A+B\text{vec}\ (q^*q^\top),$$ where $$(c,A)\in\mathbb{R}^{100}$$, $$B\in\mathbb{C}^{100\times 81}$$, $$x\in\mathbb{C}^{81}$$ and $$q\in\mathbb{C}^9$$. So $$x=\text{vec}\ (q^*q^\top)$$, which is the vectorization operator. I want to speed up my optimizer and therefore i require the gradient of the constraints (with respect to $$q$$). This is how far i have come:

\begin{aligned} dc = Bdx &= Bd\text{vec}\ (q^*q^\top)\\ &=B\text{vec}\ (q^*dq^\top+dq^*q^\top) \\ &=B\text{vec}\ (q^H:dq)+B\text{vec}\ (q^\top:dq^*) \end{aligned}

However, i cannot seem to get rid of the $$\text{vec}$$ operator. If i "matricize" the left side to remove the vectorization at the right side, i cannot get to $$\frac{\partial c}{\partial q}$$ anymore. Anyone got some brilliance for me?

Update: The last line of my derivation is incorrect i think. $$q^H\in\mathbb{C}^{12}$$ while $$dq\in\mathbb{C}^{1\times 12}$$, so you cannot use the Frobenius product here.

• As things are written, you apparently have a vector-valued "cost function". With that, it's not clear what "minimizing" the cost would entail nor what its gradient should be Commented Jul 17, 2020 at 12:29
• No, these are constraints on the cost function, not the cost function itself. The cost function is a scalar, i have 100 constraints on the cost function. Each constraint has a gradient with respect to $q$. There was a typo in the question tho, sorry! Commented Jul 17, 2020 at 12:32
• Whoops! My mistake, thanks for clarifying. Commented Jul 17, 2020 at 12:33
• Another point of confusion: what is $\operatorname{vec}(q^H : dq)$? Typically, $A : B$ is a scalar quantity Commented Jul 17, 2020 at 12:36
• Yes that does not seem correct, since they have different dimensions. I have updated my question. Commented Jul 17, 2020 at 12:41

## 2 Answers

So far, you have $$dc = B \operatorname{vec}(q^*\,dq^\top) + B\operatorname{vec}(dq^*\, q^\top).$$ To obtain the components of the gradient, it suffices to plug in $$q = e_j$$ (where $$e_1,\dots,e_9$$ denote the standard basis vectors). So, we have $$\frac{\partial c}{\partial q_j} = B \operatorname{vec}(q^*\,e_j^\top) + B\operatorname{vec}(e_j\, q^\top).$$ We could rewrite this in terms of the Kronecker product to "unvectorize". Note that $$\operatorname{vec}(v w^T) = w \otimes v$$, so that $$\frac{\partial c}{\partial q_j} = B (e_j \otimes q^*) + B(q \otimes e_j).$$

Another option is to go in the opposite direction: instead of vectorizing, unvectorize everything. Suppose that we have $$B = \sum_{j=1}^k P_j \otimes Q_j,$$ with $$P_j,Q_j$$ of size $$10 \times 3$$ (such a decomposition can be computed with reshaping and either SVD or rank factorization). We then have $$B \operatorname{vec}(q^*q^T) = \sum_{j=1}^k P_j \otimes Q_j \operatorname{vec}(q^*q^T) \\ = \sum_{j=1}^k \operatorname{vec}(Q_jq^*q^TP_j^T) \\ = \sum_{j=1}^k \operatorname{vec}(Q_jq^*(P_jq)^T).$$ In other words, if we unvectorize $$c$$ into the $$10 \times 10$$ matrix $$C$$, then we have $$C = [\text{const.}] + \sum_{j=1}^k (Q_jq^*(P_jq)^T).$$

• $e_j$ is simply (0, 1, 0, 0, 0, 0, 0, 0, 0) where $j$ determines the position of the 1, right (so in this case $j=2$? With the latter derivation, to get $\frac{\partial c}{\partial q}$, you need to reshape $\frac{\partial C}{\partial q}$ accordingly, if i am not mistaken? Commented Jul 17, 2020 at 13:04
• Yes, that's all correct. Commented Jul 17, 2020 at 13:11

The outer product of two vectors can be vectorized in several equivalent ways \eqalign{ {\rm vec}(q^*q^T) &= {\rm vec}(q^*q^TI) = {\rm vec}(Iq^*q^T) \\ =q\otimes q^* &= (I\otimes q^*)\,q = (q\otimes I)\,q^* \\ } Use this to rewrite the constraint vector and calculate its gradient(s). \eqalign{ (c-A) &= B(I\otimes q^*)\,q \;=\; B(q\otimes I)\,q^* \\ dc &= B(I\otimes q^*)\,dq + B(q\otimes I)\,dq^* \\ \frac{\partial c}{\partial q} &= B(I\otimes q^*), \quad \frac{\partial c}{\partial q^*} = B(q\otimes I) \\ }