Binary Matrix Factorization and Completion via Integer Programming

References

• [1] Barahona F, Goncalves J (2019) Local search algorithms for binary matrix factorization. URL https://github.com/IBM/binary-matrix-factorization/blob/master/code.Google Scholar
• [2] Barnhart C, Johnson EL, Nemhauser GL, Savelsbergh MWP, Vance PH (1998) Branch-and-price: Column generation for solving huge integer programs. Oper. Res. 46(3):316–329.Link, Google Scholar
• [3] Beckerleg M, Thompson A (2020) A divide-and-conquer algorithm for binary matrix completion. Linear Algebra Appl. 601:113–133.Crossref, Google Scholar
• [4] Chalermsook P, Heydrich S, Holm E, Karrenbauer A (2014) Nearly tight approximability results for minimum biclique cover and partition. Schulz AS, Wagner D, eds., Algorithms–ESA 2014 (Springer, Berlin, Heidelberg), 235–246.Crossref, Google Scholar
• [5] Cios KJ, Kurgan LA (2001) UCI machine learning repository: SPECT heart data. Accessed June 11, 2020, https://archive.ics.uci.edu/ml/datasets/spect+heart.Google Scholar
• [6] Cohen JE, Rothblum UG (1993) Nonnegative ranks, decompositions, and factorizations of nonnegative matrices. Linear Algebra Appl. 190:149–168.Crossref, Google Scholar
• [7] Conforti M, Cornuejols G, Zambelli G (2014) Graduate texts in mathematics. Integer Programming (Springer, Cham, Switzerland).Crossref, Google Scholar
• [8] CPLEX Optimization (2018) Using the CPLEX Callable Library, V.12.8 (CPLEX Optimization, Inc., Incline Village, NV).Google Scholar
• [9] Del Pia A, Khajavirad A (2022) Rank-one Boolean tensor factorization and the multilinear polytope. Preprint, submitted February 14, https://arxiv.org/abs/2202.07053.Google Scholar
• [10] Dua D, Graff C (2017) UCI machine learning repository. Accessed June 11, 2020, http://archive.ics.uci.edu/ml.Google Scholar
• [11] Fiorini S, Guo K, Macchia M, Walter M (2019) Lower bound computations for the nonnegative rank. Proc. 17th Cologne-Twente Workshop Graphs Combin. Optim., 41–44. http://wwwhome.math.utwente.nl/∼ctw/.Google Scholar
• [12] Fiorini S, Kaibel V, Pashkovich K, Theis DO (2013) Combinatorial bounds on nonnegative rank and extended formulations. Discrete Math. 313(1):67–83.Crossref, Google Scholar
• [13] Forsyth R (1990) UCI machine learning repository: Zoo data set. Accessed June 11, 2020, http://archive.ics.uci.edu/ml/datasets/Zoo.Google Scholar
• [14] Garey MR, Johnson DS (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness (W. H. Freeman & Co., New York).Google Scholar
• [15] Gillis N, Vavasis SA (2018) On the complexity of robust PCA and l1-norm low-rank matrix approximation. Math. Oper. Res. 43(4):1072–1084.Link, Google Scholar
• [16] Golub GH, Van Loan CF (1996) Matrix Computations, 3rd ed. (Johns Hopkins University Press).Google Scholar
• [17] Gong G (1988) UCI machine learning repository: Hepatitis data set. Accessed June 11, 2020, https://archive.ics.uci.edu/ml/datasets/Hepatitis.Google Scholar
• [18] Gregory DA, Pullman NJ (1983) Semiring rank: Boolean rank and nonnegative rank factorizations. J. Combin. Inform. Systems Sci. 8:223–233.Google Scholar
• [19] Karapetyan D, Punnen AP (2013) Heuristic algorithms for the bipartite unconstrained 0-1 quadratic programming problem. Preprint, submitted October 13, https://arxiv.org/abs/1210.3684.Google Scholar
• [20] Kim J, Tawarmalani M, Richard JPP (2022) Convexification of permutation-invariant sets and an application to sparse principal component analysis. Math. Oper. Res. 47(4):2547–2584.Link, Google Scholar
• [21] Kim K (1982) Boolean Matrix Theory and Applications, Monographs and Textbooks in Pure and Applied Mathematics (Dekker).Google Scholar
• [22] Kononenko I, Cestnik B (1988) UCI machine learning repository: Lymphography data set. Accessed June 11, 2020, https://archive.ics.uci.edu/ml/datasets/Lymphography.Google Scholar
• [23] Kononenko I, Cestnik B (1988) UCI machine learning repository: Primary tumor domain. Accessed June 11, 2020, https://archive.ics.uci.edu/ml/datasets/Primary+Tumor.Google Scholar
• [24] Kovacs RA (2021) Code for binary matrix factorisation and completion via integer programming. URL https://github.com/kovacsrekaagnes/rank_k_Binary_Matrix_Factorisation.Google Scholar
• [25] Kovacs RA, Gunluk O, Hauser RA (2017) Low-rank Boolean matrix approximation by integer programming. NIPS Optim. Machine Learn. Workshop, 1–5.Google Scholar
• [26] Kovacs RA, Gunluk O, Hauser RA (2021) Binary matrix factorisation via column generation. Proc. Conf. AAAI Artificial Intelligence 35(5):3823–3831.Crossref, Google Scholar
• [27] Koyutürk M, Grama A (2003) Proximus: A framework for analyzing very high dimensional discrete-attributed datasets. Proc. Ninth ACM SIGKDD Internat. Conf. Knowledge Discovery Data Mining (Association for Computing Machinery, New York), 147–156.Crossref, Google Scholar
• [28] Koyutürk M, Grama A, Ramakrishnan N (2002) Algebraic techniques for analysis of large discrete-valued datasets. Proc. Sixth Eur. Conf. Principles Data Mining Knowledge Discovery (Springer-Verlag, Berlin, Heidelberg), 311–324.Crossref, Google Scholar
• [29] Krebs V (2008) Amazon political books. Accessed June 11, 2020, http://moreno.ss.uci.edu/data.html#books.Google Scholar
• [30] Lübbecke ME, Desrosiers J (2005) Selected topics in column generation. Oper. Res. 53(6):1007–1023.Link, Google Scholar
• [31] Lee DD, Seung HS (1999) Learning the parts of objects by non-negative matrix factorization. Nature 401(6755):788–791.Crossref, Google Scholar
• [32] Li T (2005) A general model for clustering binary data. Proc. 11th ACM SIGKDD Internat. Conf. Knowledge Discovery Data Mining (Association for Computing Machinery, New York), 188–197.Google Scholar
• [33] Li Y, Ngom A (2012) The non-negative matrix factorization toolbox for biological data mining. Source Code Biol. Medicine 8:10.Crossref, Google Scholar
• [34] Li Y, Ngom A (2013) The non-negative matrix factorization toolbox in Matlab (the NMF Matlab toolbox). Accessed July 16, 2021, https://sites.google.com/site/nmftool/.Google Scholar
• [35] Lu H, Vaidya J, Atluri V (2008) Optimal Boolean matrix decomposition: Application to role engineering. Proc. 2008 IEEE 24th Internat. Conf. Data Engrg. (IEEE Computer Society, Washington, DC), 297–306.Google Scholar
• [36] Lu H, Vaidya J, Atluri V (2014) An optimization framework for role mining. J. Comput. Security 22(1):1–31.Crossref, Google Scholar
• [37] McCormick GP (1976) Computability of global solutions to factorable nonconvex programs: Part I—Convex underestimating problems. Math. Programming 10(1):147–175.Crossref, Google Scholar
• [38] Miettinen P, Mielikäinen T, Gionis A, Das G, Mannila H (2006) The discrete basis problem. Fürnkranz J, Scheffer T, Spiliopoulou M, eds., Knowledge Discovery Databases: PKDD 2006 (Springer, Berlin, Heidelberg), 335–346.Crossref, Google Scholar
• [39] Miettinen P, Mielikäinen T, Gionis A, Das G, Mannila H (2008) The discrete basis problem. IEEE Trans. Knowledge Data Engrg. 20(10):1348–1362.Crossref, Google Scholar
• [40] Monson SD, Pullman NJ, Rees R (1995) A survey of clique and biclique coverings and factorizations of (0,1)–matrices. Bull. Inst. Combin. Appl. 14:17–86.Google Scholar
• [41] Oelze M, Vandaele A, Weltge S (2014) Computing the extension complexities of all 4-dimensional 0/1-polytopes. Preprint, submitted June 18, https://arxiv.org/abs/1406.4895.Google Scholar
• [42] Orlin J (1977) Contentment in graph theory: Covering graphs with cliques. Indagationes Mathematicae (Proc.) 80(5):406–424.Crossref, Google Scholar
• [43] Padberg M (1989) The Boolean quadric polytope: Some characteristics, facets and relatives. Math. Programming 45(1):139–172.Crossref, Google Scholar
• [44] Peeters R (2003) The maximum edge biclique problem is NP-complete. Discrete Appl. Math. 131(3):651–654.Crossref, Google Scholar
• [45] Quinlan R (1992) UCI machine learning repository: Audiology (standardized) data set. Accessed June 11, 2020, http://archive.ics.uci.edu/ml/datasets/audiology+(standardized).Google Scholar
• [46] Schinnerl C (2017) Pymf—Python matrix factorization module. URL https://github.com/ChrisSchinnerl/pymf3.Google Scholar
• [47] Schlimmer J (1987) UCI machine learning repository: 1984 US Congress Voting Records Database. Accessed June 11, 2020, https://archive.ics.uci.edu/ml/datasets/Congressional+Voting+Records.Google Scholar
• [48] Shen BH, Ji S, Ye J (2009) Mining discrete patterns via binary matrix factorization. Proc. 15th ACM SIGKDD Internat. Conf. Knowledge Discovery Data Mining (Association for Computing Machinery, New York), 757–766. Google Scholar
• [49] Shi Z, Wang L, Shi L (2014) Approximation method to rank-one binary matrix factorization. 2014 IEEE Internat. Conf. Automation Sci. Engrg., 800–805.Google Scholar
• [50] Simon HU (1990) On approximate solutions for combinatorial optimization problems. SIAM J. Discrete Math. 3(2):294–310.Crossref, Google Scholar
• [51] Sripratak P, Punnen AP, Stephen T (2022) The bipartite Boolean quadric polytope. Discrete Optim. 44:100657.Crossref, Google Scholar
• [52] Zhang Z, Li T, Ding C, Zhang X (2007) Binary matrix factorization with applications. Proc. 2007 Seventh IEEE Internat. Conf. Data Mining (IEEE Computer Society), 391–400.Google Scholar