Boolean and $\mathbb{F}_p$-Matrix Factorization: From Theory to Practice

• URL: http://arxiv.org/abs/2207.11917v1
• Date: Mon, 25 Jul 2022 06:05:12 GMT
• Title: Boolean and $\mathbb{F}_p$-Matrix Factorization: From Theory to Practice
• Authors: Fedor Fomin, Fahad Panolan, Anurag Patil, Adil Tanveer
• Abstract summary: We develop new algorithms for $mathbbF_p$-Matrix Factorization. EPTAS for BMF is a purely theoretical advance. We also use this strategy to develop new algorithms for related $mathbbF_p$-Matrix Factorization.
• Score: 3.658952625899939
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Boolean Matrix Factorization (BMF) aims to find an approximation of a given binary matrix as the Boolean product of two low-rank binary matrices. Binary data is ubiquitous in many fields, and representing data by binary matrices is common in medicine, natural language processing, bioinformatics, computer graphics, among many others. Unfortunately, BMF is computationally hard and heuristic algorithms are used to compute Boolean factorizations. Very recently, the theoretical breakthrough was obtained independently by two research groups. Ban et al. (SODA 2019) and Fomin et al. (Trans. Algorithms 2020) show that BMF admits an efficient polynomial-time approximation scheme (EPTAS). However, despite the theoretical importance, the high double-exponential dependence of the running times from the rank makes these algorithms unimplementable in practice. The primary research question motivating our work is whether the theoretical advances on BMF could lead to practical algorithms. The main conceptional contribution of our work is the following. While EPTAS for BMF is a purely theoretical advance, the general approach behind these algorithms could serve as the basis in designing better heuristics. We also use this strategy to develop new algorithms for related $\mathbb{F}_p$-Matrix Factorization. Here, given a matrix $A$ over a finite field GF($p$) where $p$ is a prime, and an integer $r$, our objective is to find a matrix $B$ over the same field with GF($p$)-rank at most $r$ minimizing some norm of $A-B$. Our empirical research on synthetic and real-world data demonstrates the advantage of the new algorithms over previous works on BMF and $\mathbb{F}_p$-Matrix Factorization.

Related papers

• Optimized Inference for 1.58-bit LLMs: A Time and Memory-Efficient Algorithm for Binary and Ternary Matrix Multiplication [8.779871128906787]
  Large Language Models (LLMs) suffer from inference inefficiency while relying on advanced computational infrastructure. We propose algorithms to improve the inference time and memory efficiency of 1.58-bit LLMs with ternary weight matrices. Our results confirm the superiority of the approach both with respect to time and memory, as we observed a reduction in inference time up to 29x and memory usage up to 6x.
  arXiv  Detail & Related papers  (2024-11-10T04:56:14Z)
• Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems [61.85150061213987]
  We study the generalized low-rank matrix bandit problem, proposed in citelu2021low under the Generalized Linear Model (GLM) framework. To overcome the computational infeasibility and theoretical restrain of existing algorithms, we first propose the G-ESTT framework. We show that G-ESTT can achieve the $tildeO(sqrt(d_1+d_2)3/2Mr3/2T)$ bound of regret while G-ESTS can achineve the $tildeO
  arXiv  Detail & Related papers  (2024-01-14T14:14:19Z)
• A Unified Scheme of ResNet and Softmax [8.556540804058203]
  We provide a theoretical analysis of the regression problem: $| langle exp(Ax) + A x, bf 1_n rangle-1 ( exp(Ax) + Ax ) This regression problem is a unified scheme that combines softmax regression and ResNet, which has never been done before.
  arXiv  Detail & Related papers  (2023-09-23T21:41:01Z)
• Algorithms for Boolean Matrix Factorization using Integer Programming [20.13379783488932]
  We propose an alternating optimization (AO) strategy that solves the subproblem in one factor matrix in BMF. We show how several solutions of BMF can be combined optimally using another IP. Experiments show that our algorithms outperform the state of the art on medium-scale problems.
  arXiv  Detail & Related papers  (2023-05-17T13:09:23Z)
• Binary Matrix Factorisation and Completion via Integer Programming [3.4376560669160394]
  We present a compact and two exponential size integer programs (IPs) for the rank-k binary matrix factorisation problem (k-BMF) We show that the compact IP has a weak LP relaxation, while the exponential size LPs have a stronger equivalent LP relaxation.
  arXiv  Detail & Related papers  (2021-06-25T05:17:51Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  We propose a new algorithm for the min-player against smooth algorithms deployed by an adversary. Our algorithm is guaranteed to make monotonic progress having no limit cycles, and to find an appropriate number of gradient ascents.
  arXiv  Detail & Related papers  (2021-06-02T22:03:36Z)
• Self-supervised Symmetric Nonnegative Matrix Factorization [82.59905231819685]
  Symmetric nonnegative factor matrix (SNMF) has demonstrated to be a powerful method for data clustering. Inspired by ensemble clustering that aims to seek better clustering results, we propose self-supervised SNMF (S$3$NMF) We take advantage of the sensitivity to code characteristic of SNMF, without relying on any additional information.
  arXiv  Detail & Related papers  (2021-03-02T12:47:40Z)
• Quantum algorithms for spectral sums [50.045011844765185]
  We propose new quantum algorithms for estimating spectral sums of positive semi-definite (PSD) matrices. We show how the algorithms and techniques used in this work can be applied to three problems in spectral graph theory.
  arXiv  Detail & Related papers  (2020-11-12T16:29:45Z)
• Positive Semidefinite Matrix Factorization: A Connection with Phase Retrieval and Affine Rank Minimization [71.57324258813674]
  We show that PSDMF algorithms can be designed based on phase retrieval (PR) and affine rank minimization (ARM) algorithms. Motivated by this idea, we introduce a new family of PSDMF algorithms based on iterative hard thresholding (IHT)
  arXiv  Detail & Related papers  (2020-07-24T06:10:19Z)
• Constant-Depth and Subcubic-Size Threshold Circuits for Matrix Multiplication [1.9518237361775532]
  Recent advances in large-scale neural computing hardware has made their practical implementation a near-term possibility. We describe a theoretical approach for multiplying two $N$ by $N$ matrices that integrates threshold gate logic. Dense matrix multiplication is a core operation in convolutional neural network training.
  arXiv  Detail & Related papers  (2020-06-25T18:28:10Z)
• Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping [99.59319332864129]
  In this paper, we study reinforcement learning for discounted Decision (MDP) We propose a novel algorithm that makes use of the feature mapping and obtains a $tilde O(dsqrtT/ (1-gamma)2)$ regret. Our upper and lower bound results together suggest that the proposed reinforcement learning algorithm is near-optimal up to a $ (1-gamma)-0.5$ factor.
  arXiv  Detail & Related papers  (2020-06-23T17:08:54Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.