2
$\begingroup$

Given a non-negative matrix $T$, how to find a orthogonal matrix $O$ minimising $$ \left\lVert \, |O| - T \right\lVert_F,$$ where $\lVert \cdot \lVert_F$ denotes the Frobenius norm, and $| \cdot |$ denotes the entry wise absolute value. If $|O|$ is replaced with $O$, then this is the classic Orthogonal Procrustes Problem. I don't expect a closed form solution, but rather a way to reduce the dimensionality of the problem and tackle the problem numerically.

$\endgroup$
0
2
$\begingroup$

Here are alternate encodings based on Sebastian's comments on my previous answer.

Comment: If you want to constrain the solutions found to a particular sign pattern matrix then an additional $mn$ linear inequalities added to the above formulation can do the job.

Encoding 1: Here is another encoding of the problem that reifies the absolute value matrix. This one is efficient.

Let $ |O| = \tilde{O}$

  1. The objective becomes $||\tilde{O} - T||_F$, a order 2 polynomial in $\tilde{O}$.
  2. $O$ is orthogonal, i.e. $O^TO$ is diagonal. Quadratic constraints again.
  3. $\tilde{O} = |O|$ which means either $\tilde{O}_{ij} = O_{ij} \text{ if } O_{ij} > 0$, or $\tilde{O}_{ij} = -O_{ij} \text{ if } O_{ij} \le 0$. This can be coded as $\tilde{O}_{ij} \ge 0$ and $\tilde{O}_{ij}^2 = O_{ij}^2$, which is a linear and a quadratic constraint.

Encoding 2: Here is another encoding of the problem that uses sign pattern matrices. But its really inefficient.

We can use the kronecker product to express $ |O| = O \odot sign(O) $, So let $O, \tilde{O}$ be the orthogonal matrix and its signed counterpart respectively. Now,

  1. The objective becomes $||O \odot \tilde{O} - T||_F$, a order 4 polynomial in $\tilde{O}, O$.
  2. $O$ is orthogonal, i.e. $O^TO$ is diagonal,
  3. $\tilde{O} = sign(O)$ which means $\tilde{O}_{ij} O_{ij} > 0\ \forall i,j$, and $\tilde{O}_{ij} \in \{0, 1\}$

This encoding of the problem is not practical because it's now an IP with a fourth order polynomial. There might be ways to improve this encoding but that's future work :)

$\endgroup$
2
$\begingroup$

Let $A, B \in \mathbb{R}^{n \times m}$ be positive matrices. Consider the problem,

$ \underset{A, B}{\arg\min} || A + B - T ||_F $ subject to $A > 0, B > 0$, and $(A - B) = O$ is orthogonal and $A_{ij}B_{ij} = 0\ \forall i \in n, j \in m$

It is obvious that a solution to this would lead to a solution of the original problem.

Now, the objective is quadratic in terms of $A, B$ and $A > 0, B > 0$ are linear constraints so those are easy. The first tricky part is ensuring that $A-B$ is orthogonal. Depending on whether we need only the columns to be orthogonal or both the rows and columns to be orthogonal we can add constraints. Let's say we only want the columns of $O = A-B$ to be orthogonal. We can add the constraints that off-diagonals entries of $(A - B)^T(A-B)$ are zero. There are going to be $m(m-1)$ such equalities where $m$ is the number of columns. Each of these equalities is again a quadratic constraint.

The constraints that $A_{ij}B_{ij} = 0 \forall i \in n, j \in m$ can also be encoded as a quadratic equality constraint by considering an indicator matrix $M \in \mathbb{R}^{2mn}$ with a single unit entry at the appropriate location such that the quadratic form results in $A_{ij}B_{ij}$. By adding $2mn$ such inequalities we can encode all these equality constraints as well.

So at least a QCQP solver can solve this problem.

$\endgroup$
4
  • $\begingroup$ You're saying that $A+B = |O|$ and $A-B = O$, but don't you need an extra constraint like $A_{ij} B_{ij} = 0$ for all $i$ and $j$? $\endgroup$ – Sebastian Schlecht Dec 29 '15 at 12:12
  • $\begingroup$ @SebastianSchlecht : Ah, yes . otherwise $A + B \ne |O|$. Thanks for catching that. I think the technique can still be applied though. $\endgroup$ – Pushpendre Dec 29 '15 at 12:34
  • $\begingroup$ fixed the solution. $\endgroup$ – Pushpendre Dec 29 '15 at 13:05
  • 1
    $\begingroup$ Thanks for the fix. However, I was hoping that there would be somehow a way to exploit more the structure of orthogonal matrices and separate the magnitude matrix and sign pattern matrix. Namely, orthogonal matrices can't be purely positive, and certain sign pattern matrices may be associated with orthogonal matrices. Although, I've got to admit that this is pure speculation. $\endgroup$ – Sebastian Schlecht Dec 29 '15 at 17:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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