论文标题
通过词典学习的结构化张量的可证明的在线CP/PARAFAC分解
Provable Online CP/PARAFAC Decomposition of a Structured Tensor via Dictionary Learning
论文作者
论文摘要
我们考虑将结构化的3向张量分配到其组成典型多核（CP）因子的问题。这种分解可以看作是张量的奇异值分解（SVD）的概括，它揭示了张量尺寸（特征）如何相互作用。但是，由于这些因素是先验未知的，因此相应的优化问题本质上是非凸。现有的保证算法处理该非跨性别性误差（偏差），仅适用于所有因素具有相同结构的情况。为此，我们开发了一种可证明的算法，用于在线结构张量分解，其中其中一个因素遵守某些不一致的条件，而其他因素却很少。具体而言，我们表明，在初始化的一些相对温和的条件下，等级和稀疏性，我们的算法以线性速率准确地恢复了这些因素（直至缩放和排列）。与我们的合成和现实数据评估相比，我们的合成和现实数据评估与相关技术相比，我们的合成和现实数据评估互补。此外，它的可扩展性和直通学习的能力使其适用于现实世界任务。
We consider the problem of factorizing a structured 3-way tensor into its constituent Canonical Polyadic (CP) factors. This decomposition, which can be viewed as a generalization of singular value decomposition (SVD) for tensors, reveals how the tensor dimensions (features) interact with each other. However, since the factors are a priori unknown, the corresponding optimization problems are inherently non-convex. The existing guaranteed algorithms which handle this non-convexity incur an irreducible error (bias), and only apply to cases where all factors have the same structure. To this end, we develop a provable algorithm for online structured tensor factorization, wherein one of the factors obeys some incoherence conditions, and the others are sparse. Specifically we show that, under some relatively mild conditions on initialization, rank, and sparsity, our algorithm recovers the factors exactly (up to scaling and permutation) at a linear rate. Complementary to our theoretical results, our synthetic and real-world data evaluations showcase superior performance compared to related techniques. Moreover, its scalability and ability to learn on-the-fly makes it suitable for real-world tasks.
