为了更好的在舆情项目中应用我们提出的算法ExpCP，近期我们想对算法进行收敛性分析。大多数张量补全算法只是在算法及优化层面进行改进，很少有涉及补全框架的收敛性分析。经过一段时间的文献阅读后，我们将重点放在了Trace Norm Regularized CANDECOMP/PARAFAC Decomposition With Missing Data这篇文章。
本文提出的算法TNCP将trace norm作为正则项加入到张量CP分解的框架中，并且使用ADMM来进行优化。定义张量的n-rank如下，
常见的低秩张量补全问题就可以描述为，
一些研究者提出可以最小化n-rank的weighted求和形式，但rank本身是非凸的函数，所以一种方案是使用trace norm作为rank的凸松弛，结合上噪声项，这一问题可以描述为，
但由于张量X的unfolding矩阵维度较大，所以在迭代过程中进行的SVD分解会带来很大的计算成本。作者在这里提出可以用张量CP分解后factor matrix来代替原始unfolding矩阵，这是由如下定理所保证的，
我们不直接使用U矩阵的rank，同样是利用trace norm作为其凸松弛进行优化，TNCP的目标函数最终可以写成如下形式，
为了找到最优解，采用ADMM算法，优化过程如下（在这里我们省略每一步更新的具体求解），
伪代码如下，
接下来的收敛性分析便是这篇文章最出彩的地方，先给出主要结论，
我将证明分为4个部分来进行总结：
证明变量的有界性：通过M的更新方式来证明拉格朗日乘子Y是有界的，这部分证明中使用了[Z. Lin，2009]这篇文章中的一条引理。进一步，由增广拉格朗日函数中M的表达形式结合Y的有界性来证明M的有界性。最后再利用U与M、Y的关系来说明U也是有界的。
由Y的更新方式来证明M和U最终收敛到同一个值，从而说明随着k的增长，二者趋于feasible solution（即满足问题的限制条件M=U）。
在ADMM更新U矩阵时，通过求导可以具体写出下一步更新的closed form，将式中的M全部替换为U和Y，我们可以证明$||U_n^{k+1}-U_n^k||_F = O((\mu^k)^{-1})$。使用类似的证明同样可以证明M和Y也是Cauchy sequence。
写出原始问题的KKT条件，再分别写出U与M的更新过程，结合两式可以发现U与M最终趋于原始问题的KKT点。这样就完成了整个证明，算法具有不错的收敛性，这部分内容非常值得我们参考。
接下来作者对算法复杂度进行了分析，
并通过一些实验来验证了算法的有效性，这里不再赘述，仅将结果呈现。
