Estimation of low-rank tensors via convex optimization
Ryota Tomioka Department of Mathematical Informatics, The University of Tokyo, 7-3-1 Hongo, Bunkyo-ku, Tokyo, 113-8656, Japan Kohei Hayashi Graduate School of Information Science, Nara Institute of Science and Technology, 8916-5 Takayama, Ikoma, Nara, 630-0192, Japan Hisashi Kashima†
Abstract
In this paper, we propose three approaches for the estimation of the Tucker decomposition of multi-way arrays (tensors) from partial observations. All approaches are formulated as convex minimization problems. Therefore, the minimum is guaranteed to be unique. The proposed approaches can automatically estimate the number of factors (rank) through the optimization. Thus, there is no need to specify the rank beforehand. The key technique we employ is the trace norm regularization, which is a popular approach for the estimation of low-rank matrices. In addition, we propose a simple heuristic to improve the interpretability of the obtained factorization. The advantages and disadvantages of three proposed approaches are demonstrated through numerical experiments on both synthetic and real world datasets. We show that the proposed convex optimization based approaches are more accurate in predictive performance, faster, and more reliable in recovering a known multilinear structure than conventional approaches.
中文速览
多维数组（张量）Tucker分解的传统方法（如HOOI）是非凸优化问题，不仅无法保证找到全局最优解，还需要提前人工指定秩（因子数量），使用起来十分麻烦。作者提出了三种基于迹范数（trace norm）正则化的凸优化方法来估计部分观测张量的Tucker分解：第一种把张量展开成矩阵直接处理，第二种同时对所有展开模式施加低秩约束，第三种用多个张量的混合来放宽"所有模式同时低秩"这一严格假设。由于问题是凸的，全局最优解唯一且有保证，秩也可在优化过程中自动确定而无需预先设定；在合成数据和真实数据集上的实验表明，所提方法在预测精度、运行速度和多线性结构恢复可靠性方面均优于传统的基于EM的Tucker分解算法。这项工作将矩阵补全领域成熟的凸优化理论有效推广到了高阶张量，为缺失数据下的多维数据分析提供了更稳健、实用的工具。
原文 arXiv:1010.0789;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1010.0789v2