4
$\begingroup$

I'm wondering whether there is a good way to solve the following optimisation problem.

Given a strictly positive quadratic matrix $A$, find two diagonal matrices $D_1$ and $D_2$ so that

$$ \| D_1 A D_2 - J \|_2 $$

is minimal. $J$ is a matrix of ones, i.e. $J_{ij} = 1$ for all $i,j$. The norm can be replaced by the Frobenius norm.

It should be related to the rank 1 approximation based on the SVD of A, but because of the inversion this might be not possible directly.

$\endgroup$
8
  • $\begingroup$ As you noted, you can use the best rank-1 approximation via SVD when $D_1$ and $D_2$ are nonsingular (equivalently: when the best rank-$1$ approximation has no $0$ entries). Can't you just use continuity arguments to take care of the case when the best rank-$1$ approximation does have a $0$ entry, and hence conclude that the SVD still gives the best answer? $\endgroup$ – Nathaniel Johnston May 31 '14 at 23:12
  • $\begingroup$ I do not see immediately how one concludes using SVD. SVD minimizes $\|A-D_1^{-1}JD_2^{-1}\|$, but the two error measures are different. $\endgroup$ – Federico Poloni Jun 1 '14 at 6:49
  • $\begingroup$ Yes, the difference in the error measures is exactly what makes the headache right now. $\endgroup$ – Sebastian Schlecht Jun 1 '14 at 7:54
  • $\begingroup$ What is the connection to inverses? $\endgroup$ – Felix Goldberg Jun 1 '14 at 11:39
  • $\begingroup$ @FelixGoldberg As Federico pointed out, the entrywise inverse of $A$ does not solve the problem for the same error norm. Hence, the title is a bit misleading right now. Idea for a better one? $\endgroup$ – Sebastian Schlecht Jun 1 '14 at 13:06
1
$\begingroup$

We seek the minimum of the function $f:(D_1,D_2)\in\Delta^2\rightarrow trace((D_1AD_2-J)(D_2A^TD_1J))$ where $\Delta$ is the space of diagonal matrices (of course, we use the Frobenius norm). $\dfrac{\partial f}{\partial D_1}:H\in \Delta\rightarrow trace((U+U^T)H)$ where $U=AD_2(D_2A^TD_1-J)$ and $\dfrac{\partial f}{\partial D_2}:H\in \Delta\rightarrow trace((V+V^T)H)$ where $V=A^TD_1(D_1AD_2-J)$. Let $D_1=diag(\lambda_i),D_2=diag(\mu_i),A=[a_{i,j}]$. The conditions $\dfrac{\partial f}{\partial D_1}=\dfrac{\partial f}{\partial D_2}=0$ give the $2n$ equations: for every $i$, $U[i,i]=V[i,i]=0$ in the $2n$ unknowns $(\lambda_i)_i,(\mu_i)_i$. In fact there are only $2n-1$ unknowns because we can choose (for example) $\lambda_1=1$. The $2n$ equations have degree $3$ and can be written as follows: for every $i$, $\sum_ja_{i,j}\mu_j(a_{i,j}\mu_j\lambda_i-1)=0,\sum_ja_{j,i}\lambda_j(a_{j,i}\lambda_j\mu_i-1)=0$. If $n=3$ (resp. $4$), using the Grobner basis theory, we must solve a polynomial of degree $39$ (resp. $284$). It may be better to use a numerical method. But how to choose the initial point ?

$\endgroup$

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.