The Hadamard decomposition problem. (English) Zbl 07917023
Summary: We introduce the Hadamard decomposition problem in the context of data analysis. The problem is to represent exactly or approximately a given matrix as the Hadamard (or element-wise) product of two or more low-rank matrices. The motivation for this problem comes from situations where the input matrix has a multiplicative structure. The Hadamard decomposition has potential for giving more succint but equally accurate representations of matrices when compared with the gold-standard of singular value decomposition (svd). Namely, the Hadamard product of two rank-\(h\) matrices can have rank as high as \({h}^2\). We study the computational properties of the Hadamard decomposition problem and give gradient-based algorithms for solving it approximately. We also introduce a mixed model that combines svd and Hadamard decomposition. We present extensive empirical results comparing the approximation accuracy of the Hadamard decomposition with that of the svd using the same number of basis vectors. The results demonstrate that the Hadamard decomposition is competitive with the svd and, for some datasets, it yields a clearly higher approximation accuracy, indicating the presence of multiplicative structure in the data.
References:
| [1] | Banerjee, S.; Roy, A., Linear algebra and matrix analysis for statistics, 2014, Boca Raton: CRC Press, Boca Raton · Zbl 1309.15002 |
| [2] | Bernstein, D., Scalar, vector, and matrix mathematics: theory, facts, and formulas-revised and expanded edition, 2018, Princeton: Princeton University Press, Princeton · Zbl 1396.15001 |
| [3] | Breslow, NE; Lubin, J.; Marek, P.; Langholz, B., Multiplicative models and cohort analysis, J Am Stat Assoc, 78, 381, 1-12, 1983 · Zbl 0503.62090 |
| [4] | Bro, R.; Smilde, AK, Principal component analysis, Ana Methods, 6, 9, 2812-2831, 2014 |
| [5] | Brunet, J-P; Tamayo, P.; Golub, TR; Mesirov, JP, Metagenes and molecular pattern discovery using matrix factorization, Proc Natl Acad Sci, 101, 12, 4164-4169, 2004 |
| [6] | Bürgisser, P.; Clausen, M.; Shokrollahi, MA, Algebraic complexity theory, 2013, New York: Springer, New York |
| [7] | De Handschutter, P.; Gillis, N.; Siebert, X., A survey on deep matrix factorizations, Comput Sci Rev, 42, 100423, 2021 · Zbl 1486.68147 |
| [8] | DeSantis, D.; Skau, E.; Truong, DP; Alexandrov, B., Factorization of binary matrices: rank relations, uniqueness and model selection of Boolean decomposition, ACM Trans Knowl Discov Data (TKDD), 16, 6, 1-24, 2022 |
| [9] | Fortelius, M.; Gionis, A.; Mannila, H.; Jernvall, J., Spectral ordering and biochronology of European fossil mammals, Paleobiology, 32, 2, 206-214, 2006 |
| [10] | Gillis, N., Nonnegative matrix factorization, 2020, Philadelphia: SIAM, Philadelphia |
| [11] | Girvan, M.; Newman, ME, Community structure in social and biological networks, Proc Natl Acad Sci, 99, 12, 7821-7826, 2002 · Zbl 1032.91716 |
| [12] | Golub, GH; Van Loan, CF, Matrix computations, 2013, Baltimore: JHU Press, Baltimore |
| [13] | Guan, X.; Li, C-T; Guan, Y., Matrix factorization with rating completion: an enhanced SVD model for collaborative filtering recommender systems, IEEE Access, 5, 27668-27678, 2017 |
| [14] | Hallinan, B.; Striphas, T., Recommended for you: the Netflix prize and the production of algorithmic culture, New Media Soc, 18, 1, 117-137, 2016 |
| [15] | Harper, FM; Konstan, JA, The movielens datasets: history and context, ACM Trans Interact Intell Syst (TIIS), 5, 4, 1-19, 2015 |
| [16] | Hoff, PD, Lasso, fractional norm and structured sparse estimation using a Hadamard product parametrization, Computat Stat Data Anal, 115, 186-198, 2017 · Zbl 1466.62098 |
| [17] | Hoff, P., Additive and multiplicative effects network models, Stat Sci, 36, 1, 34-50, 2021 · Zbl 07368218 |
| [18] | Horn, RA; Yang, Z., Rank of a Hadamard product, Linear Algebra Appl, 591, 87-98, 2020 · Zbl 1439.15007 |
| [19] | Klema, V.; Laub, A., The singular value decomposition: its computation and some applications, IEEE Trans Autom Control, 25, 2, 164-176, 1980 · Zbl 0433.93018 |
| [20] | Knuth, DE, The Stanford GraphBase: a platform for combinatorial computing, 1993, New York: ACM Press, New York |
| [21] | Lee, P., Relation between exposure to asbestos and smoking jointly and the risk of lung cancer, Occup Environ Med, 58, 3, 145-153, 2001 |
| [22] | Lee, C-S; Guo, S-M; Hsu, C-Y, Genetic-based fuzzy image filter and its application to image processing, IEEE Trans Syst Man Cybern Part B (Cybern), 35, 4, 694-711, 2005 |
| [23] | Liu, R.; Li, S.; Liu, J.; Ma, L.; Fan, X.; Luo, Z., Learning Hadamard-product-propagation for image dehazing and beyond, IEEE Trans Circuits Syst Video Technol, 31, 4, 1366-1379, 2020 |
| [24] | Miettinen, P.; Vreeken, J., Mdl4bmf: minimum description length for Boolean matrix factorization, ACM Trans Knowl Discov Data (TKDD), 8, 4, 1-31, 2014 |
| [25] | Miettinen, P.; Mielikäinen, T.; Gionis, A.; Das, G.; Mannila, H., The discrete basis problem, IEEE Trans Knowl Data Eng, 20, 10, 1348-1362, 2008 |
| [26] | Petersen, KB; Pedersen, MS, The matrix cookbook, Tech Univ Den, 7, 15, 510, 2008 |
| [27] | Piziak, R.; Odell, P., Full rank factorization of matrices, Math Mag, 72, 3, 193-201, 1999 · Zbl 1006.15009 |
| [28] | Qi, L.; Cornelis, MC; Zhang, C.; Van Dam, RM; Hu, FB, Genetic predisposition, western dietary pattern, and the risk of type 2 diabetes in men, Am J Clin Nutr, 89, 5, 1453-1458, 2009 |
| [29] | Ramlatchan, A.; Yang, M.; Liu, Q.; Li, M.; Wang, J.; Li, Y., A survey of matrix completion methods for recommendation systems, Big Data Min Anal, 1, 4, 308-323, 2018 |
| [30] | Rao, CR, Estimation of heteroscedastic variances in linear models, J Am Stat Assoc, 65, 329, 161-172, 1970 |
| [31] | Roberto Cruz, M., More about the multiplicative model for the analysis of genotype-environment interaction, Heredity, 68, 2, 135-140, 1992 |
| [32] | Rodriguez-Aragon, LJ; Zhigljavsky, A., Singular spectrum analysis for image processing, Stat Interface, 3, 3, 419-426, 2010 · Zbl 1245.94026 |
| [33] | Schaefer, M.; Štefankovič, D., Fixed points, nash equilibria, and the existential theory of the reals, Theory Comput Syst, 60, 2, 172-193, 2017 · Zbl 1362.68088 |
| [34] | Schönemann, PH, A generalized solution of the orthogonal procrustes problem, Psychometrika, 31, 1, 1-10, 1966 · Zbl 0147.19401 |
| [35] | Singh, DAAG; Leavline, EJ, Dimensionality reduction for classification and clustering, Int J Intell Syst Appl (IJISA), 11, 4, 61-68, 2019 |
| [36] | Slyusar, V., A family of face products of matrices and its properties, Cybern Syst Anal, 35, 3, 379-384, 1999 · Zbl 0984.15015 |
| [37] | Stewart, GW, On the early history of the singular value decomposition, SIAM Rev, 35, 4, 551-566, 1993 · Zbl 0799.01016 |
| [38] | Styan, GP, Hadamard products and multivariate statistical analysis, Linear Algebra Appl, 6, 217-240, 1973 · Zbl 0255.15002 |
| [39] | Thompson, JN, The evolution of species interactions, Science, 284, 5423, 2116-2118, 1999 |
| [40] | Thompson, PL; MacLennan, MM; Vinebrooke, RD, Species interactions cause non-additive effects of multiple environmental stressors on communities, Ecosphere, 9, 11, 02518, 2018 |
| [41] | Tong, T.; Ma, C.; Chi, Y., Accelerating ill-conditioned low-rank matrix estimation via scaled gradient descent, J Mach Learn Res, 22, 1, 6639-6701, 2021 · Zbl 07415093 |
| [42] | Udell, M.; Townsend, A., Why are big data matrices approximately low rank?, SIAM J Math Data Sci, 1, 1, 144-160, 2019 · Zbl 1513.68057 · doi:10.1137/18M1183480 |
| [43] | Ursu, E.; Duchesne, P., On multiplicative seasonal modelling for vector time series, Stat Probab Lett, 79, 19, 2045-2052, 2009 · Zbl 1171.62053 |
| [44] | Van Loan, CF; Pitsianis, N.; Moonen, MS; Golub, GH, Approximation with Kronecker products, Linear algebra for large scale and real time applications, 1993, Dordrecht: Kluwer Publications, Dordrecht |
| [45] | Visick, G., A quantitative version of the observation that the Hadamard product is a principal submatrix of the Kronecker product, Linear Algebra Appl, 304, 1-3, 45-68, 2000 · Zbl 0946.15015 |
| [46] | Wang, S.; Sun, G.; Li, Y., Svd++ recommendation algorithm based on backtracking, Information, 11, 7, 369, 2020 |
| [47] | Yang, Z.; Stoica, P.; Tang, J., Source resolvability of spatial-smoothing-based subspace methods: a Hadamard product perspective, IEEE Trans Signal Process, 67, 10, 2543-2553, 2019 · Zbl 1458.94152 |
| [48] | Ye, T.; Du, SS, Global convergence of gradient descent for asymmetric low-rank matrix factorization, Adv Neural Inf Process Syst, 34, 1429-1439, 2021 |
| [49] | Zhou, X.; He, J.; Huang, G.; Zhang, Y., SVD-based incremental approaches for recommender systems, J Comput Syst Sci, 81, 4, 717-733, 2015 · Zbl 1320.68158 |
| [50] | Alpaydin E, Kaynak C (1998) Optical recognition of handwritten digits. UCI machine learning repository. doi:10.24432/C50P49 |
| [51] | Bennett J, Lanning S et al (2007) The Netflix prize. In: Proceedings of KDD cup and workshop, vol. 2007, p 35 |
| [52] | Center NAR (1988) Low resolution spectrometer. UCI machine learning repository. doi:10.24432/C5B02R |
| [53] | Chung K-C, Kee SC, Kim SR (1999) Face recognition using principal component analysis of Gabor filter responses. In: Proceedings international workshop on recognition, analysis, and tracking of faces and gestures in real-time systems. In conjunction with ICCV’99 (Cat. No. PR00378). IEEE, pp 53-57 |
| [54] | Cox DR (1984) Interaction. International Statistical Review/Revue Internationale de Statistique 1-24 |
| [55] | Ding C, He X, Simon HD (2005) On the equivalence of nonnegative matrix factorization and spectral clustering. In: Proceedings of the 2005 SIAM international conference on data mining. SIAM, pp 606-610 |
| [56] | Dooms S, De Pessemier T, Martens L (2013) Movietweetings: a movie rating dataset collected from twitter. In: Workshop on Crowdsourcing and human computation for recommender systems, vol 2013. CrowdRec at RecSys, p 43 |
| [57] | Fortelius M (2008) Neogene of the old world database of fossil mammals (NOW). http://www.helsinki.fi/science/now/ |
| [58] | Friedenberg N, Oneto A, Williams RL (2017) Minkowski sums and Hadamard products of algebraic varieties. In: Combinatorial algebraic geometry: selected papers from the 2016 Apprenticeship Program, pp 133-157 · Zbl 1390.14157 |
| [59] | Funk S (2006) Netflix update: try this at home |
| [60] | Garriga GC, Junttila E, Mannila H (2008) Banded structure in binary matrices. In: Proceedings of the 14th ACM SIGKDD international conference on knowledge discovery and data mining, pp 292-300 |
| [61] | Guvenir HA, Acar B, Demiroz G, Cekin A (1997) A supervised machine learning algorithm for arrhythmia analysis. In: Computers in cardiology 1997. IEEE, pp 433-436 |
| [62] | Horn RA (1990) The Hadamard product. In: Proc. symp. appl. math., vol 40, pp 87-169 · Zbl 0712.15011 |
| [63] | Hyeon-Woo N, Ye-Bin M, Oh T-H (2021) FedPara: low-rank Hadamard product for communication-efficient federated learning. In: International conference on learning representations |
| [64] | Khatri C, Rao CR (1968) Solutions to some functional equations and their applications to characterization of probability distributions. Sankhyā Indian J Stat Ser A 167-180 · Zbl 0176.49004 |
| [65] | Kim J-H, On K-W, Lim W, Kim J, Ha J-W, Zhang B-T (2016) Hadamard product for low-rank bilinear pooling. In: International conference on learning representations |
| [66] | Lam SK, Pitrou A, Seibert S (2015) Numba: a llvm-based python jit compiler. In: Proceedings of the second workshop on the LLVM compiler infrastructure in HPC, pp 1-6 |
| [67] | Li T, Ding CH (2013) Nonnegative matrix factorizations for clustering: a survey. In: Data clustering: algorithms and applications, pp 149-176 |
| [68] | Li Y, Liang Y (2017) Provable alternating gradient descent for non-negative matrix factorization with strong correlations. In: International conference on machine learning. PMLR, pp 2062-2070 |
| [69] | Mnih A, Salakhutdinov RR (2007) Probabilistic matrix factorization. Adv Neural Inf Process Syst 20 |
| [70] | Montúfar G (2018) Restricted Boltzmann machines: introduction and review. In: Information geometry and its applications: on the occasion of Shun-ichi Amari’s 80th Birthday, IGAIA IV Liblice, Czech Republic, June 2016. Springer, pp 75-115 · Zbl 1414.62257 |
| [71] | Oneto A, Vannieuwenhoven N (2023) Hadamard-Hitchcock decompositions: identifiability and computation. arXiv preprint arXiv:2308.06597 |
| [72] | Ozbulak U (2017) Singular value decomposition on images. GitHub |
| [73] | Paszke A, Gross S, Chintala S, Chanan G, Yang E, DeVito Z, Lin Z, Desmaison A, Antiga L, Lerer A (2017) Automatic differentiation in pytorch. In: NIPS-W |
| [74] | Ruder S (2016) An overview of gradient descent optimization algorithms. arXiv preprint arXiv:1609.04747 |
| [75] | Sajnani H, Saini V, Kumar K, Gabrielova E, Choudary P, Lopes C (2012) Classifying Yelp reviews into relevant categories. Mondego Group, Univ. California Press, Berkeley, CA USA, Tech. Rep |
| [76] | Salakhutdinov R, Mnih A (2008) Bayesian probabilistic matrix factorization using Markov chain Monte Carlo. In: Proceedings of the 25th international conference on machine learning, pp 880-887 |
| [77] | Wu CW (2018) Prodsumnet: reducing model parameters in deep neural networks via product-of-sums matrix decompositions. arXiv preprint arXiv:1809.02209 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
