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