1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – www3 Mar 6 '17 at 21:35
  • $\begingroup$ @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. $\endgroup$ – whuber Mar 6 '17 at 22:02
  • $\begingroup$ $x_{i}$ and $y_{i}$ are both positive. I just took second derivatives in my head. I could have made a mistake. $\endgroup$ – www3 Mar 6 '17 at 22:07
  • 1
    $\begingroup$ 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. $\endgroup$ – www3 Mar 6 '17 at 22:45

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.