6
$\begingroup$

In the expression:

$${\underset{\Omega}{\min}\left\|\beta A\Omega^{-1}B+C\right\|_{F}^{2}}\, ,$$ $$\text{subject to tr}(\Omega)=1, \Omega \ge 0\, ,$$

where ${\Omega}$ is nonnegative and symmetric matrix.

How to solve for the variable $\Omega$?

$\endgroup$
9
  • 2
    $\begingroup$ Does $\Omega \ge 0$mean that elements of $\Omega$ are nonnegative elementwise, or that $\Omega$ is positive semidefinite? $\endgroup$ Jul 14, 2021 at 17:30
  • $\begingroup$ Are you minimizing that expression? You need to say so (edit the question). $\endgroup$ Jul 14, 2021 at 18:35
  • $\begingroup$ yes, this is a minimization problem, and ${\Omega}$ is a symmetric matrix and any element of Ω is nonnegative. $\endgroup$
    – tjufan
    Jul 14, 2021 at 23:54
  • 2
    $\begingroup$ There are many issues with this post, but if we can fix'em, it is an interesting question. Is $\Omega$ full or is there a fixed sparsity pattern? This looks like a sparse approximate inverse problem, and it is clear that if $\Omega$ is full then this is very expensive to solve. $\endgroup$ Jul 15, 2021 at 0:25
  • $\begingroup$ Yes, in fact, ${\Omega \in R^{c \times c}}$ and ${\Omega}$ has the full rank. $\endgroup$
    – tjufan
    Jul 15, 2021 at 0:43

1 Answer 1

3
$\begingroup$

$ \def\O{\Omega}\def\M{\mho}\def\t{\theta} \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\bR#1{\big(#1\big)} \def\vecc#1{\operatorname{vec}\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\hess#1#2#3{\frac{\p^2 #1}{\p #2\,\p #3}} \def\c#1{\color{red}{#1}} \def\TE{\trace{E}} $The constraints can be eliminated via construction.
Starting with an unconstrained matrix $U$ define an element-wise exponential and re-scale it $$\eqalign{ E &= \exp(U) \qiq E\ge 0 \\ \O &= \frac{E}{\TE} \qiq \trace{\O}=1,\;\O\ge 0 \\ }$$ For typing convenience, define some new variables (and redefine some existing ones) $$\eqalign{ \t &= \TE,\qquad A = \beta A,\quad \M = \O^{-1},\quad M=A\M B+C \\ Q &= \frac{\M^TA^TMB^T\M^T}{\t^2} \\ R &= {\trace{Q^TE}\,I - \t\,Q} \\ }$$ and use a colon to denote the Frobenius product $$\eqalign{ A:B &= \sum_{i=1}^m\sum_{j=1}^n A_{ij}B_{ij} \;\doteq\; \trace{A^TB} \\ A:A &= \big\|A\big\|^2_F \\ }$$ and $\odot$ for the Hadamard product, which (amazingly) commutes with the Frobenius product $$\eqalign{ A:\LR{B\odot C} = \LR{A\odot B}:C \\ }$$ Use the above notation to calculate the differential and gradient of the objective function $$\eqalign{ \phi &= \frac 12M:M \\ d\phi &= M:dM \\ &= M:\LR{A\,d\M\,B} \\ &= M:\LR{-A\M\;d\O\;\M B} \\ &= -\M^TA^TMB^T\M^T:{d\O} \\ &= -\M^TA^TMB^T\M^T:\LR{ \frac{\t\,dE-E\,\c{d\t}}{\t^2} } \\ &= Q:\BR{E\c{\LR{I:dE}}} - Q:\t\,dE \\ &= R:dE \\ &= R:\LR{E\odot dU} \\ &= \LR{R\odot E}:dU \\ \grad{\phi}{U} &= {R\odot E} \\ }$$ Setting the gradient to zero yields a complicated nonlinear equation which is impossible to solve analytically. Instead, use the gradient derived above in your favorite gradient descent algorithm to calculate the optimal $U$. $\;$ Hint: The $k^{th}$ iteration will look like $$\eqalign{ U_{k+1} &= U_k -\lambda_k{R_k\odot E_k} \\ }$$ where the step-length $\lambda_k$ is determined by a line search or some heuristic formula.

After obtaining the optimal $U$ you can then calculate the corresponding $\O$ matrix.

Update

${\rm If}\;\O^T\!=\O\, \big({\rm and\,therefore\;}U^T\!=U,\;E^T\!=E\big)$ the gradient should be symmetrized $$\eqalign{ \grad{\phi}{U} &= \LR{\frac{R+R^T}{2}}\odot E \\ }$$

$\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.