Nonnegative CANDECOMP/PARAFAC decomposition

Given a nonnegative tensor mathcal{M}, the problem seeks nonnegative matrices A_1,cdots,A_N such that A_1circcdotscirc A_N =mathcal{M} or A_1circcdotscirc A_Napprox mathcal{M}, where “circ” denotes outer product.

Specifically, given A_ninmathbb{R}^{I_ntimes r},forall n, we have

 (A_1circcdotscirc A_N)_{i_1,cdots,i_N}=sum_{j=1}^{r}(A_1)_{i_1,j}cdots(A_N)_{i_N,j}.

The decomposition is modeled as the optimization problem

 mathop{mathrm{minimize}}_{A_1ge 0,cdots,A_Nge 0} ~frac{1}{2}|A_1circcdotscirc A_N - mathcal{M}|_F^2,

where the Frobenius norm of a tensor mathcal{X}inmathbb{R}^{I_1timescdotstimes I_N} is defined as

 |mathcal{X}|_F=sqrt{sum_{i_1=1}^{I_1}cdotssum_{i_N=1}^{I_N}x_{i_1,cdots,i_N}^2}.

More information about tensor and its decomposition can be found in this review paper.


The algorithm is described in Algorithm 2 of this report.

Matlab code of BCU with prox-linear update and extrapolation