Rank-One Boolean Tensor Factorization and the Multilinear Polytope

• 成果类型: Article
• 署名作者: Del Pia, Alberto; Khajavirad, Aida
• 署名单位: University of Wisconsin System; University of Wisconsin Madison; University of Wisconsin System; University of Wisconsin Madison; Lehigh University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2022.0201
• 发表日期: 2025
• 关键词: convex

摘要

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 rankone 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 semirandom 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.