1
$\begingroup$

I have an energy I'd like to minimize of the form:

$E(G) = \|\underbrace{X - Y G^T L G B}_{f(G)}\|_F^2$

where $X,Y,B$ are dense matrices and $G,L$ are sparse matrices ($G^TLG$ is also sparse), $\|M\|_F^2$ computes the squared Frobenius norm of the matrix $M$.

I'd like to compute quantities such as $\partial f/\partial G$ (or $\partial^2 E/\partial G^2$) to use Gauss-Newton's (or Newton's) method, but I only care about changes to $G$ that maintain its sparsity pattern. That is, suppose $G$ is a function of the non-zero values collected in a vector $g$ via, say, $G = \mathop{sparse}(i,j,g)$ where $i,j$ are lists of subscript indices corresponding to values in $g$. Then I'd really like to compute $\partial f/\partial g$.

Eventually I'm programming this and would like to avoid computing $\partial f/\partial G$ as a dense matrix/tensor.

Is there's a nice (reduced) expression for $\partial f/\partial g$?

If not, what's the best way to use automatic differentiation to conduct this optimization? I'm having trouble formulating this in the right way to use the libraries I found.

$\endgroup$
2
  • $\begingroup$ Are you seeking $\frac{\partial E(G)}{\partial G}$ or $\frac{\partial f(G)}{\partial G}$, where $E(G)$ is a scalar and $f(G)$ is a matrix? If you are looking for $\frac{\partial f(G)}{\partial G}$, then it will be 4th order tensor (and don't think it is really needed for the optimization). I think $\frac{\partial E(G)}{\partial G}$ should suffice your need... $\endgroup$
    – user550103
    Commented Jan 8, 2019 at 5:44
  • $\begingroup$ I'm interested in $d f(G(g))/d g$ $\endgroup$ Commented Jan 8, 2019 at 18:20

1 Answer 1

2
$\begingroup$

Consider the normal vectorization operation applied to the sparse matrix $G$. Now define a projection matrix $P$ which omits the zero elements to recover what you've denoted as the $g$-vector. So we have $$\eqalign{ g_{vec} &= {\rm vec}(G) = P^Tg \cr g &= P\,g_{vec} = PP^Tg \cr I &= PP^T \cr }$$ As a concrete example of the projection matrix consider $$\eqalign{ G &= \pmatrix{1&4\cr 0&0},\quad g_{vec}=\pmatrix{1\cr 0\cr 4\cr 0},\quad g=\pmatrix{1\cr 4} \cr P &= \pmatrix{1&0&0&0\cr0&0&1&0},\quad P^T=\pmatrix{1&0\cr 0&0\cr 0&1\cr 0&0} \cr }$$Define the matrix $$F = (YG^TLGB - X) = -f$$ Write the energy in terms of $F$ and find its differential in terms of the differential $dg$. $$\eqalign{ {\mathcal E} &= \|F\|^2_F = {\rm Tr}(F^TF) = F:F {\quad\rm \Big(Frobenius\,product\Big)} \cr d{\mathcal E} &= 2F:dF \cr &= 2F:\big(Y\,dG^T\,LGB+YG^TL\,dG\,B\big) \cr &= \big(2LGBF^TY + 2L^TGY^TFB^T\big):dG \cr &= 2{\,\rm vec}\big(2LGBF^TY + 2L^TGY^TFB^T\big):{\rm vec}(dG) \cr &= 2\Big((Y^TFB^T\otimes L)\,g_{vec} + (BF^TY\otimes L^T)\,g_{vec}\Big):dg_{vec} \cr &= 2\Big(Y^TFB^T\otimes L + BF^TY\otimes L^T\Big)P^Tg:P^T\,dg \cr &= 2P\Big(Y^TFB^T\otimes L + BF^TY\otimes L^T\Big)P^Tg:dg \cr }$$ So the gradient is $$\eqalign{ \frac{\partial {\mathcal E}}{\partial g} &= 2P\Big(Y^TFB^T\otimes L+BF^TY\otimes L^T\Big)P^Tg \cr }$$ Finding the Hessian is not worth the additional effort. Just use a gradient-based method,
e.g. Polak-Ribiere, Barzilai-Borwein, etc.

$\endgroup$
5
  • $\begingroup$ Thanks. I actually already had the gradient, but your derivation is very nice. I am interested in $df/dg$ in the hopes of doing Gauss-Newton (currently gradient-based methods I've tried are quite slow). $\endgroup$ Commented Jan 9, 2019 at 3:07
  • 1
    $\begingroup$ @AlecJacobson The gradient of a matrix wrt a vector is a 3rd order tensor. But by flattening the matrix into a vector, i.e. $\,f_{vec}={\rm vec}(F),\,$ the gradient can be written as a matrix $$ \frac{\partial f_{vec}}{\partial g} = (B^TG^TL^T\otimes Y)KP^T + (B^T\otimes YG^TL)P^T $$ where $K$ is the Commutation Matrix associated with the Kronecker product. $\endgroup$
    – greg
    Commented Jan 9, 2019 at 6:21
  • $\begingroup$ Thanks, again. Should this expression be multiplied by $g$ on the right? $\endgroup$ Commented Jan 9, 2019 at 7:22
  • 1
    $\begingroup$ @AlecJacobson No, the gradient is a matrix, not a vector. $\endgroup$
    – greg
    Commented Jan 9, 2019 at 8:47
  • $\begingroup$ Right. I confused myself. f is linear in g, thus the $d f /d g$ is a constant matrix. $\endgroup$ Commented Jan 9, 2019 at 15:52

You must log in to answer this question.

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