Guaranteed Non-Orthogonal Tensor Decomposition via Alternating Rank-111 Updates
Anima Anandkumar111University of California, Irvine. Email: Rong Ge222Microsoft Research, New England. Email: Majid Janzamin333University of California, Irvine. Email:
Abstract
In this paper, we provide local and global convergence guarantees for recovering CP (Candecomp/Parafac) tensor decomposition. The main step of the proposed algorithm is a simple alternating rank- $1$ update which is the alternating version of the tensor power iteration adapted for asymmetric tensors. Local convergence guarantees are established for third order tensors of rank $k$ in $d$ dimensions, when $k=o\bigl{(}d^{1.5}\bigr{)}$ and the tensor components are incoherent. Thus, we can recover overcomplete tensor decomposition. We also strengthen the results to global convergence guarantees under stricter rank condition $k\leq\beta d$ (for arbitrary constant $\beta>1$ ) through a simple initialization procedure where the algorithm is initialized by top singular vectors of random tensor slices. Furthermore, the approximate local convergence guarantees for $p$ -th order tensors are also provided under rank condition $k=o\bigl{(}d^{p/2}\bigr{)}$ . The guarantees also include tight perturbation analysis given noisy tensor.
中文速览
张量分解（CP decomposition）是无监督学习潜变量模型的核心工具，但现有方法要么依赖数值不稳定的"白化"预处理、要么无法处理分量数远超维度的"过完备"情形。本文提出一种基于交替秩-1更新（alternating rank-1 update）的算法，绕开白化步骤，直接对非正交张量进行分解，并利用张量分量之间的"非相干性"（incoherence，即一种软正交约束）来保证算法收敛。理论上，对三阶、秩为 k、维度为 d 的张量，当 k=o(d^{1.5}) 时可证明线性速率的局部收敛；在更严格的秩条件 k≤βd 下，通过对随机张量切片做奇异向量初始化，还能获得全局收敛保证；同时给出了含噪场景下的紧扰动分析。这项工作首次在温和的非相干条件下为过完备张量分解提供了严格的收敛性保证，算法本身计算高效、易于并行，对主题模型、独立成分分析等大量实际学习任务具有直接意义。
原文 arXiv:1402.5180;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1402.5180v4