I need to perform a particular rank 1 decomposition of a sparse matrix $\mathbf{A} \in \mathbb{R}^{n\times n}$.

In particular I am looking for the positive vector $\mathbf{u} \in \mathbb{R}^{+n}$ such that the square of the sum over the non-missing elements in $\mathbf{A}$, denoted by the set $E$ is minimal. In formula this reads

$$\underset{\mathbf{u} \in \mathbb{R}^{n+}}{\textrm{argmin}} \sum_{i,j\in E} \left( A_{ij} - \frac{u_i}{u_j} \right)^2 $$

I have been able to solve this optimization problem by means of L-BFGS with positive bounded solution. However it looks like there are multiple local minima, the sparser the input network. Moreover the method is very slow.

I am wondering how to cast this problem into one of matrix decomposition. Specifically the matrix $\mathbf{X} = \mathbf{x}\cdot (\mathbf{x}^{\circ-1})^T$ is a rank 1 matrix with each element $X_{ij} = \frac{x_i}{x_j}$.

Classical SVD returns a decomposition $\mathbf{A} = \sum_i^{r=n} \sigma_i \mathbf{u}_i \mathbf{v}_i^T$ where $\sigma_i$ are the singular values, and $\mathbf{u}_i$ and $\mathbf{v}_i$ are unitary vectors.

In my case I would like to constraint SVD to stop at $r=1$ elements with the constraint that elements of $u$ and $v$ are inverse to each other, hence approximating $\mathbf{A} \approx \mathbf{u}\cdot (\mathbf{u}^{\circ-1})^T$.

Is there any method to tackle this problem more efficiently?

  • $\begingroup$ have you been able to specify the jacobian to the optimizer? in my experience this becomes an order of magnitude faster. $\endgroup$ – Attack68 Mar 13 '19 at 6:03
  • $\begingroup$ Yes, I specify the exact jacobian computed via automatic differentiation techniques (autograd module in python) and it helps a lot. $\endgroup$ – linello Mar 13 '19 at 12:27

Your Answer

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

Browse other questions tagged or ask your own question.