# Rank 1 Approximation of Elementwise Inverse Matrix

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.

• 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? – Nathaniel Johnston May 31 '14 at 23:12
• 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. – Federico Poloni Jun 1 '14 at 6:49
• Yes, the difference in the error measures is exactly what makes the headache right now. – Sebastian Schlecht Jun 1 '14 at 7:54
• What is the connection to inverses? – Felix Goldberg Jun 1 '14 at 11:39
• @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? – Sebastian Schlecht Jun 1 '14 at 13:06

## 1 Answer

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 ?