# Algorithm for multiplicative regression with Tikhonov regularization?

I am looking for an algorithm to solve a regularized multiplicative regression. More specifically, for $x_i \in \mathbb{R}^+, y_j \in \mathbb{R}^+, a_{ij} \in \mathbb{R}^+, \gamma \in\mathbb{R}^+$, I am seeking an algorithm to compute the coefficients $(x_i,y_j)$ that minimizes:

$$\sum_{ij} (x_i y_j -a_{ij})^2 + \gamma\left(\sum_i x_i^2 + \sum_j y_j^2\right)$$

The problem can be interpreted as multiplicative regression of $X$ and $Y$, associated to with regularization component similar to the Tikhonov regularization.

With matrix notations, this minimization problem could be rewritten as:

$$\|XY^t-A\|_F^2+\gamma\left(\|X\|^2+\|Y\|^2\right)$$

with $\|.\|_F$ the Frobenius norm.

Is there a known algorithm to (efficiently) solve this problem?

• Am I wrong is this not convex? It looks convex to me. You can always use gradient descent to solve this, but there are likely better convex optimization routines that I don't know or can't think of. – www3 Mar 6 '17 at 21:35
• @www3 Why not plot the objective function in a simple case, such as where there is just one $x_i$ and one $y_j$? It will become clear that it is not convex in a neighborhood of $(0,0)$, for instance, unless $|\gamma|$ is sufficiently large. – whuber Mar 6 '17 at 22:02
• $x_{i}$ and $y_{i}$ are both positive. I just took second derivatives in my head. I could have made a mistake. – www3 Mar 6 '17 at 22:07
• I didn't calculate the hessian and eigenvalues but regardless you can use coordinate descent. Hold $x$ constant and optimize $y$. Then hold $y$ constant and optimize $x$--each one individually is convex. At least intuitively should converge to a global minimum. – www3 Mar 6 '17 at 22:45