3
$\begingroup$

I'd like to minimize the objective

$ \operatorname{tr}[ (Y-XR^{-1})^T (Y-XR^{-1}) ] + \lambda \sum_{ij} |R_{ij}|$

wrt to $R$ (which is $P \times P$ but non-symmetric) where $Y$ and $X$ are both $N \times P$. For my application it would make sense to have the diagonal of $R$ constrained to 1 (and possibly that $\det{(I-R)} \leq 1$ also). Obviously $R$ needs to be invertible.

I'm pretty sure this is non-convex in $R$, but can it be converted into a convex problem? e.g. optimize over $W=R^{-1}$. (I realize if I put the L1 penalty on $W$ rather than $R$ I get a lasso-like problem, but I want the sparsity on $R$ not $W$). I think the issue is $W=R^{-1}$ is a non-convex constraint.

Could I use an ADMM approach? e.g. minimize

$ \operatorname{tr}[ (Y-XW)^T (Y-XW) ] + \lambda \sum_{ij} |R_{ij}| + \gamma (\operatorname{tr}(RW) - \log \det R - \log \det W)$

This is biconvex in $R$ and $W$, and increasing $\gamma$ will force $W$ closer to $R^{-1}$ (inspired by the graphical lasso).

$\endgroup$

1 Answer 1

2
$\begingroup$

In the end I used ADMM (see Boyd et al.). Minimize

$ \frac12 \operatorname{tr}[ (Y-XW)^T (Y-XW) ] + \lambda ||R||_1$

s.t. $RW = I$. The augmented Lagrangian is

$ L(R,W,\theta)=\frac12\operatorname{tr}[ (Y-XW)^T (Y-XW) ] + \operatorname{tr}( \theta' (RW-I) ) + \frac12\rho \operatorname{tr}[ (RW-I)^T (RW-I) ] + \lambda ||R||_1$

where $\theta$ is an $P \times P$ matrix of Lagrange multipliers. Iterate over optimizing $W$ (easy because $L$ is quadratic in $W$), $R$ (can be converted into a standard lasso regression) and updating

$\theta \leftarrow \theta + \rho(RW-I)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.