3
$\begingroup$

Suppose $A\in\mathbb{R}_+^{n\times n}$ is symmetric. I would like to factorize $A\approx UU^\top$ by solving $$ \begin{array}{rl} \min_U & \sum_{ij} \left(A_{ij}\ln\frac{A_{ij}}{[UU^\top]_{ij}}+[UU^\top]_{ij} \right)\\ \textrm{s.t.} & U\geq0, \end{array} $$ for a local minimizer.

The objective of this problem is KL divergence $\mathrm{KL}(A|UU^\top)$, similar to the one used in this paper and others on nonnegative matrix factorization. The difference is that I want to optimize as $UU^\top$ rather than $UV^\top$ for matrices $U$ and $V$.

I can't find papers on this variation of nonnegative factorization, except this paper mentions it briefly under eq.(11) without discussion. As I understand it, convergence of nonnegative matrix factorization algorithms is well-understood, and I'm hoping to find something similar.

Any ideas for how to find a local optimizer using a simple iteration? Ideally, I'm hoping some method with nice convergence (e.g. multiplicative updates) from nonnegative matrix factorization will be applicable without much adaptation.

$\endgroup$
3
$\begingroup$

I'm going through some of my old StackExchange posts and came across this one. As it turns out, the answer led to a section in a published paper!

As detailed in that paper (and in its notation), if you wish to minimize $\mathrm{KL}(B|AA^\top)$, the following iterations will decrease the objective---and in practice work well--- $$ \begin{array}{rl} U_k&\gets A_k\otimes[(B\oslash AA^\top)A]\\ A_{k+1}&\gets U\cdot\mathrm{diag}[1\oslash \sqrt{U^\top\mathbf{1}}] \end{array} $$ Here, $\mathbf{1}$ denotes the vector of all ones, $\otimes$ denotes elementwise multiplication, and $\oslash$ denotes elementwise division. $A$ should be initialized using random entries.

$\endgroup$
  • $\begingroup$ That's super cool! $\endgroup$ – Memming Oct 4 '17 at 23:40

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.