1
$\begingroup$

Given matrices $\Gamma_1, C \in \mathbb R^{n \times n}$, find a matrix $\Gamma \in \mathbb R^{n \times n}$ that minimizes the matrix norm of $\Gamma - \Gamma_1$ subject to constraints

$$\begin{array}{ll} \text{minimize} & \| \Gamma - \Gamma_1 \|\\ \text{subject to} & \Gamma 1_n = 1_n\\ & \Gamma^{\top} 1_n = 1_n\\ & C \Gamma = 1_n 1_n^{\top}\end{array}$$

How can I solve it using MATLAB? I find someone uses Iterative Bregman Projections. Or can this be solved by using proximal methods?

Are there any methods to solve it. It's very important for my current research. I hope someone could help me.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ How is the KL divergence defined when the inputs are matrices, rather than distributions? $\endgroup$
    – Rodrigo de Azevedo
    Commented Dec 31, 2016 at 10:34
  • $\begingroup$ @RodrigodeAzevedo KL divergence in matrix can be just replaced by norm($Γ-Γ_1$) $\endgroup$
    – Nolan
    Commented Dec 31, 2016 at 14:59
  • $\begingroup$ l1-norm or frobenius norm are both OK for my problem. $\endgroup$
    – Nolan
    Commented Dec 31, 2016 at 15:06
  • $\begingroup$ Sorry, I have changed it. Constraint 3 means that each term in the matrix is in the value of 1. $\endgroup$
    – Nolan
    Commented Dec 31, 2016 at 15:08
  • $\begingroup$ Small remark that is probably not relevant: if $C$ is invertible, this problem suddenly becomes a lot simpler... $\endgroup$
    – Federico Poloni
    Commented Apr 1, 2017 at 9:08

1 Answer 1

Reset to default
1
$\begingroup$

Given matrices $\mathrm X_0, \mathrm C \in \mathbb R^{n \times n}$,

$$\begin{array}{ll} \text{minimize} & \| \mathrm X - \mathrm X_0 \|_{\text{F}}^2\\ \text{subject to} & \mathrm X 1_n = 1_n\\ & 1_n^{\top} \mathrm X = 1_n^{\top}\\ & \mathrm C \mathrm X = 1_n 1_n^{\top}\end{array}$$

Vectorizing, $\tilde{\mathrm x} := \mbox{vec} (\mathrm X)$, we obtain the following convex quadratic program (QP)

$$\begin{array}{ll} \text{minimize} & \| \tilde{\mathrm x} \|_2^2 - 2 \langle \mbox{vec} (\mathrm X_0), \tilde{\mathrm x} \rangle + \| \mathrm X_0 \|_{\text{F}}^2\\ \text{subject to} & (1_n^{\top} \otimes \mathrm I_n ) \, \tilde{\mathrm x} = 1_n\\ & (\mathrm I_n \otimes 1_n^{\top}) \, \tilde{\mathrm x} = 1_n\\ & (\mathrm I_n \otimes \mathrm C) \, \tilde{\mathrm x} = 1_{n^2}\end{array}$$

In MATLAB, use function quadprog to solve this QP. Then use reshape to un-vectorize the solution.

Improve this answer
$\endgroup$
7
  • $\begingroup$ I think you have helped me to solve it. Thanks very much for your kindness. $\endgroup$
    – Nolan
    Commented Dec 31, 2016 at 15:41
  • $\begingroup$ You need MATLAB's Optimization Toolbox, though. $\endgroup$
    – Rodrigo de Azevedo
    Commented Dec 31, 2016 at 15:44
  • $\begingroup$ I test this, but matlab shows that the dual problem is suspected of being infeasible. May be the constraint 3 violates with the other two constraints. $\endgroup$
    – Nolan
    Commented Jan 1, 2017 at 13:33
  • 1
    $\begingroup$ There are $n^2$ unknowns. The first two (vector) constraints impose $2n$ (scalar) constraints. The third (matrix) constraint imposes $n^2$ (scalar) constraints. The system is overdetermined. Hence, infeasibility should come as no surprise. $\endgroup$
    – Rodrigo de Azevedo
    Commented Jan 1, 2017 at 13:40
  • 1
    $\begingroup$ This is why it is a good idea to provide motivation when asking a question. People can help refine the question before attempting to answer it. $\endgroup$
    – Rodrigo de Azevedo
    Commented Jan 2, 2017 at 13:34

You must log in to answer this question.

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