University of Wisconsin–Madison, Madison, WI 53706, USA.
IEEE Trans Pattern Anal Mach Intell. 2013 Jan;35(1):208-20. doi: 10.1109/TPAMI.2012.39.
In this paper, we propose an algorithm to estimate missing values in tensors of visual data. The values can be missing due to problems in the acquisition process or because the user manually identified unwanted outliers. Our algorithm works even with a small amount of samples and it can propagate structure to fill larger missing regions. Our methodology is built on recent studies about matrix completion using the matrix trace norm. The contribution of our paper is to extend the matrix case to the tensor case by proposing the first definition of the trace norm for tensors and then by building a working algorithm. First, we propose a definition for the tensor trace norm that generalizes the established definition of the matrix trace norm. Second, similarly to matrix completion, the tensor completion is formulated as a convex optimization problem. Unfortunately, the straightforward problem extension is significantly harder to solve than the matrix case because of the dependency among multiple constraints. To tackle this problem, we developed three algorithms: simple low rank tensor completion (SiLRTC), fast low rank tensor completion (FaLRTC), and high accuracy low rank tensor completion (HaLRTC). The SiLRTC algorithm is simple to implement and employs a relaxation technique to separate the dependent relationships and uses the block coordinate descent (BCD) method to achieve a globally optimal solution; the FaLRTC algorithm utilizes a smoothing scheme to transform the original nonsmooth problem into a smooth one and can be used to solve a general tensor trace norm minimization problem; the HaLRTC algorithm applies the alternating direction method of multipliers (ADMMs) to our problem. Our experiments show potential applications of our algorithms and the quantitative evaluation indicates that our methods are more accurate and robust than heuristic approaches. The efficiency comparison indicates that FaLTRC and HaLRTC are more efficient than SiLRTC and between FaLRTC an- HaLRTC the former is more efficient to obtain a low accuracy solution and the latter is preferred if a high-accuracy solution is desired.
在本文中，我们提出了一种算法来估计视觉数据张量中的缺失值。这些值可能由于采集过程中的问题或由于用户手动识别出不需要的异常值而丢失。我们的算法即使在少量样本的情况下也能正常工作，并且可以传播结构以填充更大的缺失区域。我们的方法基于使用矩阵迹范数进行矩阵补全的最新研究。本文的贡献在于通过提出张量迹范数的第一个定义，并在此基础上构建一个有效的算法，将矩阵情况扩展到张量情况。首先，我们提出了张量迹范数的定义，该定义推广了已建立的矩阵迹范数定义。其次，与矩阵补全类似，张量补全被表述为凸优化问题。不幸的是，由于多个约束之间的依赖关系，直接扩展问题比矩阵情况要困难得多。为了解决这个问题，我们开发了三种算法：简单低秩张量补全（SiLRTC）、快速低秩张量补全（FaLRTC）和高精度低秩张量补全（HaLRTC）。SiLRTC 算法易于实现，采用松弛技术分离相关关系，并使用块坐标下降（BCD）方法实现全局最优解；FaLRTC 算法利用平滑方案将原始非平滑问题转化为平滑问题，可用于解决一般张量迹范数最小化问题；HaLRTC 算法将交替方向乘子法（ADMMs）应用于我们的问题。我们的实验表明了我们的算法的潜在应用，定量评估表明我们的方法比启发式方法更准确和稳健。效率比较表明 FaLRTC 和 HaLRTC 比 SiLRTC 更有效，而在 FaLRTC 和 HaLRTC 之间，前者更有效地获得低精度解，而后者更适合需要高精度解的情况。
