Minimization of $\log \det$ plus $\| \cdot \|_1$ Given fat matrices ${\bf A} \in \mathbb{R}^{m\times n}$ (where $m < n$) and ${\bf B}\in \mathbb{R}^{p\times n}$ (where $p < n$ and $\mbox{rank}({\bf B}) = p$), and $m \times m$ symmetric positive semidefinite matrix $\bf{W}$, let ${\bf{G}} := {\bf{A}} + {\bf{XB}}$.
$$ \min_{{\bf{X}} \in \mathbb{R}^{m \times p}}\ \log \det \left( \bf{GWG}^\top \right) + \| {\bf{X}} \|_1 $$
where
$$ \| {\bf{X}} \|_1 := \sum_{i,j} | x_{ij} | $$
The first term of the objective function is convex under the given constraints. So this objective function is representing sum of two convex functions.
I am trying to use ADMM to write down the updating steps. However when I take $\bf{GWG}^\top$ as the the first term becomes concave. Is there a better way to formulate this problem?
Update: I tried rewriting the first term $-\log|({\bf GWG})^{-1}|$, but it complicates the update step for $\bf{X}$. Any other insights to solve this problem is greatly appreciated.
Update2: The log determinant term is not convex. So this problem reduces to non-convex optimization problem. Any references for algorithms which have solved similar issues?
 A: $
\def\o{{\tt1}}\def\p{\partial}
\def\L{\left}\def\R{\right}
\def\LR#1{\L(#1\R)}
\def\BR#1{\Big(#1\Big)}
\def\sign#1{\operatorname{sign}\LR{#1}}
\def\diag#1{\operatorname{diag}\LR{#1}}
\def\Diag#1{\operatorname{Diag}\LR{#1}}
\def\trace#1{\operatorname{tr}\LR{#1}}
\def\qiq{\quad\implies\quad}
\def\grad#1#2{\frac{\p #1}{\p #2}}
\def\c#1{\color{red}{#1}}
$Given the matrix variables
$$\eqalign{
G &= A+XB  &\qiq dG = dX\,B \\
M &= M^T=GWG^T &\qiq dM = dX\,BWG^T+GWB^T\,dX^T \\
S &= \sign X &\qiq \|X\|_\o = S:X \\
}$$
where $(:)$ denotes the Frobenius product, which is a concise
notation for the trace
$$\eqalign{
A:B &= \sum_{i=1}^m\sum_{j=1}^n A_{ij}B_{ij} \;=\; \trace{A^TB} \\
A:A &= \big\|A\big\|^2_F \\
}$$
Write the objective function using the above notation.
Then calculate its differential and gradient.
$$\eqalign{
\phi &= S:X \;\,+\; \log\det\!\LR{M} \\
d\phi &= S:dX + d\LR{\trace{\log\!\LR{M}}} \\
 &= S:dX + M^{-\o} : dM \\
 &= S:dX + M^{-\o} : \LR{dX\,BWG^T+GWB^T\,dX^T} \\
 &= S:dX + 2M^{-\o} : \LR{dX\,BWG^T} \\
 &= \LR{S+2M^{-\o}GWB^T} : dX \\
\grad{\phi}{X} &= \;{S+2M^{-\o}GWB^T} \\
}$$
$\|X\|_1$ isn't differentiable, so this is really a subgradient,
but it allows you to employ gradient-based methods to calculate minima with iterations like
$$\eqalign{
X_{k+1} = X_k -\lambda_k\LR{\grad{\phi}{X_k}} \\
}$$
