Rank-One Boolean Tensor Factorization and the Multilinear Polytope

References

• [1] Abbe E, Bandeira AS, Hall G (2016) Exact recovery in the stochastic block model. IEEE Trans. Inform. Theory 62(1):471–487.Crossref, Google Scholar
• [2] Belohlavek R, Glodeanu C, Vychodil V (2013) Optimal factorization of three-way binary data using triadic concepts. Order 30(2):437–454.Crossref, Google Scholar
• [3] Bi X, Qu A, Shen X (2018) Multilayer tensor factorization with applications to recommender systems. Ann. Statist. 46(6B):3308–3333.Crossref, Google Scholar
• [4] Buchheim C, Crama Y, Rodríguez-Heck E (2019) Berge-acyclic multilinear 0−1 optimization problems. Eur. J. Oper. Res. 273(1):102–107.Crossref, Google Scholar
• [5] Crama Y (1993) Concave extensions for non-linear 0−1 maximization problems. Math. Programming 61:53–60.Crossref, Google Scholar
• [6] Crama Y, Rodríguez-Heck E (2017) A class of valid inequalities for multilinear 0−1 optimization problems. Discrete Optim. 25:28–47.Crossref, Google Scholar
• [7] Czyzyk J, Mesnier MP, More JJ (1998) The NEOS server. IEEE J. Comput. Sci. Engrg. 5(3):68–75.Crossref, Google Scholar
• [8] Del Pia A, Di Gregorio S (2021) Chvátal rank in binary polynomial optimization. INFORMS J. Optim. 3(4):315–349.Link, Google Scholar
• [9] Del Pia A, Khajavirad A (2017) A polyhedral study of binary polynomial programs. Math. Oper. Res. 42(2):389–410.Link, Google Scholar
• [10] Del Pia A, Khajavirad A (2018) The multilinear polytope for acyclic hypergraphs. SIAM J. Optim. 28(2):1049–1076.Crossref, Google Scholar
• [11] Del Pia A, Khajavirad A (2018) On decomposability of multilinear sets. Math. Programming 170(2):387–415.Crossref, Google Scholar
• [12] Del Pia A, Khajavirad A (2021) The running intersection relaxation of the multilinear polytope. Math. Oper. Res. 46(3):1008–1037.Link, Google Scholar
• [13] Del Pia A, Khajavirad A (2023) A polynomial-size extended formulation for the multilinear polytope of beta-acyclic hypergraphs. Math. Programming Ser. A.Crossref, Google Scholar
• [14] Del Pia A, Walter M (2022) Simple odd beta-cycle inequalities for binary polynomial optimization. Proc. IPCO 2022 Lecture Notes Comput. Sci. (Springer, Berlin, Heidelberg).Google Scholar
• [15] Del Pia A, Khajavirad A, Kunisky D (2023) Linear programming and community detection. Math. Oper. Res. 48(2):885–913.Link, Google Scholar
• [16] Del Pia A, Khajavirad A, Sahinidis N (2020) On the impact of running intersection inequalities for globally solving polynomial optimization problems. Math. Programming Comput. 12(2):165–191.Crossref, Google Scholar
• [17] De Rosa A, Khajavirad A (2022) The ratio-cut polytope and k-means clustering. SIAM J. Optim. 32(1):173–203.Crossref, Google Scholar
• [18] De Rosa A, Khajavirad A (2023) Efficient joint object matching via linear programming. Math. Programming 202:1–46.Crossref, Google Scholar
• [19] Erdos D, Miettinen P (2013) Walk ‘n’ merge: A scalable algorithm for boolean tensor factorization. IEEE 13th Internat. Conf. Data Mining (IEEE, Piscataway, NJ), 1037–1042.Google Scholar
• [20] Feige U, Kilian J (2001) Heuristics for semirandom graph problems. J. Comput. System Sci. 63(4):639–671.Crossref, Google Scholar
• [21] Gillis N, Vavasis S (2018) On the complexity of robust PCA and ℓ1-norm low-rank matrix approximation. Math. Oper. Res. 43(4):1072–1084.Link, Google Scholar
• [22] Hastad J (1990) Tensor rank is NP-complete. J. Algorithms 11(4):644–654.Crossref, Google Scholar
• [23] Hong D, Kolda TG, Duersch JA (2020) Generalized canonical polyadic tensor decomposition. SIAM Rev. 62(1):133–163.Crossref, Google Scholar
• [24] Hore V, Vinuela A, Buil A, Knight J, McCarthy MI, Small K, Marchini J (2016) Tensor decomposition for multiple-tissue gene expression experiments. Nat. Genetics 48(9):1094–1100.Crossref, Google Scholar
• [25] IBM (2016) CPLEX Optimizer. Accessed May, 2022, http://www-01.ibm.com/software/integration/optimization/cplex-optimizer/.Google Scholar
• [26] Khajavirad A (2023) On the strength of recursive McCormick relaxations for binary polynomial optimization. Oper. Res. Lett. 51(2):146–152.Crossref, Google Scholar
• [27] Kolda TG, Bader BW (2009) Tensor decompositions and applications. SIAM Rev. 51(3):455–500.Crossref, Google Scholar
• [28] Ling S, Strohmer T (2020) Certifying global optimality of graph cuts via semidefinite relaxation: A performance guarantee for spectral clustering. Foundations Comput. Math. 20(3):367–421.Crossref, Google Scholar
• [29] Mangasarian O (1979) Uniqueness of solution in linear programming. Linear Algebra Appl. 25:151–162.Crossref, Google Scholar
• [30] Mazgut J, Tino P, Boden M, Yan H (2014) Dimensionality reduction and topographic mapping of binary tensors. PAA Pattern Anal. Appl. 17(3):497–515.Crossref, Google Scholar
• [31] Miettinen P (2011) Boolean tensor factorizations. IEEE 11th Internat. Conf. Data Mining (IEEE Computer Society, Washington, DC), 447–456.Google Scholar
• [32] Mixon DG, Villar S, Ward R (2017) Clustering subgaussian mixtures by semidefinite programming. Inform. Inference 6(4):389–415.Crossref, Google Scholar
• [33] Moitra A, Perry W, Wein A (2016) How robust are reconstruction thresholds for community detection? Proc. 48th Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 828–841.Google Scholar
• [34] Park N, Oh S, Kang U (2017) Fast and scalable distributed Boolean tensor factorization. IEEE 33rd Internat. Conf. Data Engrg. (IEEE, Piscataway, NJ), 1071–1082.Google Scholar
• [35] Rai P, Hu C, Harding M, Carin L (2015) Scalable probabilistic tensor factorization for binary and count data. Proc. 24th Internat. Joint Conf. Artificial Intelligence, 3770–3776.Google Scholar
• [36] Ricci-Tersenghi F, Javanmard A, Montanari A (2016) Performance of a community detection algorithm based on semidefinite programming. J. Phys. Conf. Ser. 699:012015.Crossref, Google Scholar
• [37] Rukat T, Holmes CCY (2018) Probabilistic Boolean tensor decomposition. Proc. 35th Internat. Conf. Machine Learn., vol. 80 (PMLR, New York), 4413–4422.Google Scholar
• [38] Sherali HD (1997) Convex envelopes of multilinear functions over a unit hypercube and over special discrete sets. Acta Mathematica Vietnamica 22(1):245–270.Google Scholar
• [39] Sherali HD, Adams WP (1990) A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM J. Discrete Math. 3(3):411–430.Crossref, Google Scholar
• [40] Tawarmalani M, Richard JPP, Xiong C (2013) Explicit convex and concave envelopes through polyhedral subdivisions. Math. Programming 138(1–2):531–577.Crossref, Google Scholar
• [41] Wan C, Chang W, Zhao T, Cao S, Zhang C (2020) Geometric all-way Boolean tensor decomposition. Adv. Neural Inform. Processing Systems, vol. 3 (Curran Associates Inc., Red Hook, NY), 2848–2857.Google Scholar
• [42] Wang L, Zhang Z, Dunson D (2019) Common and individual structure of brain networks. Ann. Appl. Statist. 13(1):85–112.Crossref, Google Scholar
• [43] Zhou H, Li L, Zhu H (2013) Tensor regression with applications in neuroimaging data analysis. J. Amer. Statist. Assoc. 108(502):540–552.Crossref, Google Scholar