Nonnegative CANDECOMP/PARAFAC decomposition from partial observations

Given partial observations of a nonnegative tensor mathcal{M} (let Omega index the observed entries), the problem seeks nonnegative matrices A_1, cdots,A_N such that $mathcal{P}_Omega(A_1circcdotscirc A_N) =mathcal{P}_Omega(mathcal{M})$ or $mathcal{P}_Omega(A_1circcdotscirc A_n)approxmathcal{P}_Omega(mathcal{M})$ , where “ circ ” denotes outer product and $mathcal{P}_Omega(cdot)$ denotes a sampling operator.

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}|mathcal{P}_Omega(A_1circcdotscirc A_N) -mathcal{P}_Omega(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

Matlab function which needs tensor toolbox
Synthetic example