Smoothed Analysis of Tensor Decompositions
Aditya Bhaskara Google Research NYC. Email: Work done while the author was at EPFL, Switzerland. Moses Charikar Princeton University. Email: Supported by NSF awards CCF 0832797, AF 1218687 and CCF 1302518 Ankur Moitra Massachusetts Institute of Technology, Department of Mathematics and CSAIL. Email: Part of this work was done while the author was a postdoc at the Institute for Advanced Study and was supported in part by NSF grant No.DMS-0835373 and by an NSF Computing and Innovation Fellowship. Aravindan Vijayaraghavan Carnegie Mellon University. Email: Supported by the Simons Postdoctoral Fellowship.
Abstract
Low rank decomposition of tensors is a powerful tool for learning generative models. The uniqueness of decomposition gives tensors a significant advantage over matrices. However, tensors pose significant algorithmic challenges and tensors analogs of much of the matrix algebra toolkit are unlikely to exist because of hardness results. Efficient decomposition in the overcomplete case (where rank exceeds dimension) is particularly challenging. We introduce a smoothed analysis model for studying these questions and develop an efficient algorithm for tensor decomposition in the highly overcomplete case (rank polynomial in the dimension). In this setting, we show that our algorithm is robust to inverse polynomial error – a crucial property for applications in learning since we are only allowed a polynomial number of samples. While algorithms are known for exact tensor decomposition in some overcomplete settings, our main contribution is in analyzing their stability in the framework of smoothed analysis.
中文速览
张量分解（tensor decomposition）在学习生成模型时非常有用，因为它的分解结果往往是唯一的，但当分量数（rank）超过维度时，现有算法要么不存在、要么极不稳定。本文引入"平滑分析"（smoothed analysis）框架——假设模型参数不是恶意选取的，而是在任意基础上叠加了微小随机扰动——并在此框架下证明了一个关键结论：经过扰动的向量组在做 Khatri-Rao 积后，线性无关性会"稳健地相乘"，从而使得对应矩阵的最小奇异值保持在逆多项式量级以上。基于这一核心结果，作者给出了在高度超完备情形（rank 可达维度的多项式次方）下高效、抗噪的张量分解算法，并将其直接应用于多视角混合模型（multi-view model）和轴对齐高斯混合模型（mixtures of axis-aligned Gaussians）的学习，首次实现了分量数远超维度时的多项式时间算法。这一工作的重要性在于：它突破了张量方法长期受限于"分量数不超过维度"的瓶颈，为现实中维度远小于类别数的场景（如语音识别、图像分类）提供了有理论保证的高效学习方案。
原文 arXiv:1311.3651;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1311.3651v4