# Rank 1 SVD with constraint on U

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?

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