论文标题
等级一布尔张量分解和多线性多层
Rank-one Boolean tensor factorization and the multilinear polytope
论文作者
论文摘要
我们考虑了找到最接近给定二进制张量的最接近的二进制张量的NP硬性问题，我们称之为排名一的布尔张量分解（BTF）问题。该优化问题可用于从嘈杂的观察结果中恢复种植的一条张量。我们将排名btf提出，作为在高度结构化的多线性集合上最小化线性函数的问题。利用我们有关多线性多面体面部结构的先前结果，我们提出了对等级的BTF的新型线性编程松弛。然后，我们建立了确定性的足够条件，在该条件下，我们提议的线性程序恢复了种植的排名一张量。为了分析这些确定性条件的有效性，我们考虑了嘈杂张量的半随机模型，并为线性程序获得高概率恢复保证金。我们的理论结果以及数值模拟表明，多线性多层的某些方面显着提高了对等级的BTF线性编程松弛的恢复性能。
We consider the NP-hard problem of finding the closest rank-one binary tensor to a given binary tensor, which we refer to as the rank-one Boolean tensor factorization (BTF) problem. This optimization problem can be used to recover a planted rank-one tensor from noisy observations. We formulate rank-one BTF as the problem of minimizing a linear function over a highly structured multilinear set. Leveraging on our prior results regarding the facial structure of multilinear polytopes, we propose novel linear programming relaxations for rank-one BTF. We then establish deterministic sufficient conditions under which our proposed linear programs recover a planted rank-one tensor. To analyze the effectiveness of these deterministic conditions, we consider a semi-random model for the noisy tensor, and obtain high probability recovery guarantees for the linear programs. Our theoretical results as well as numerical simulations indicate that certain facets of the multilinear polytope significantly improve the recovery properties of linear programming relaxations for rank-one BTF.
