Boolean Matrix Factorization via Nonnegative Auxiliary Optimization

• URL: http://arxiv.org/abs/2106.04708v1
• Date: Tue, 8 Jun 2021 21:55:49 GMT
• Title: Boolean Matrix Factorization via Nonnegative Auxiliary Optimization
• Authors: Duc P. Truong, Erik Skau, Derek Desantis, Boian Alexandrov
• Abstract summary: Instead of solving the BMF problem directly, this approach solves a nonnegative optimization problem with the constraint over an auxiliary matrix. We provide the proofs for the equivalencies of the two solution spaces under the existence of an exact solution. Experiments on synthetic and real datasets are conducted to show the effectiveness and complexity of the algorithm.
• Score: 0.5459797813771498
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A novel approach to Boolean matrix factorization (BMF) is presented. Instead of solving the BMF problem directly, this approach solves a nonnegative optimization problem with the constraint over an auxiliary matrix whose Boolean structure is identical to the initial Boolean data. Then the solution of the nonnegative auxiliary optimization problem is thresholded to provide a solution for the BMF problem. We provide the proofs for the equivalencies of the two solution spaces under the existence of an exact solution. Moreover, the nonincreasing property of the algorithm is also proven. Experiments on synthetic and real datasets are conducted to show the effectiveness and complexity of the algorithm compared to other current methods.

Related papers

• Matrix Completion with Convex Optimization and Column Subset Selection [0.0]
  We present two algorithms that implement our Columns Selected Matrix Completion (CSMC) method. To study the influence of the matrix size, rank computation, and the proportion of missing elements on the quality of the solution and the time, we performed experiments on synthetic data. Our thorough analysis shows that CSMC provides solutions of comparable quality to matrix completion algorithms, which are based on convex optimization.
  arXiv  Detail & Related papers  (2024-03-04T10:36:06Z)
• Dynamic Incremental Optimization for Best Subset Selection [15.8362578568708]
  Best subset selection is considered the gold standard for many learning problems. An efficient subset-dual algorithm is developed based on the primal and dual problem structures.
  arXiv  Detail & Related papers  (2024-02-04T02:26:40Z)
• A First-Order Multi-Gradient Algorithm for Multi-Objective Bi-Level Optimization [7.097069899573992]
  We study the Multi-Objective Bi-Level Optimization (MOBLO) problem. Existing gradient-based MOBLO algorithms need to compute the Hessian matrix. We propose an efficient first-order multi-gradient method for MOBLO, called FORUM.
  arXiv  Detail & Related papers  (2024-01-17T15:03:37Z)
• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  This paper studies first-order algorithms for solving fully composite optimization problems convex compact sets. We leverage the structure of the objective by handling differentiable and non-differentiable separately, linearizing only the smooth parts.
  arXiv  Detail & Related papers  (2023-02-24T18:41:48Z)
• On the Global Solution of Soft k-Means [159.23423824953412]
  This paper presents an algorithm to solve the Soft k-Means problem globally. A new model, named Minimal Volume Soft kMeans (MVSkM), is proposed to address solutions non-uniqueness issue.
  arXiv  Detail & Related papers  (2022-12-07T12:06:55Z)
• Log-based Sparse Nonnegative Matrix Factorization for Data Representation [55.72494900138061]
  Nonnegative matrix factorization (NMF) has been widely studied in recent years due to its effectiveness in representing nonnegative data with parts-based representations. We propose a new NMF method with log-norm imposed on the factor matrices to enhance the sparseness. A novel column-wisely sparse norm, named $ell_2,log$-(pseudo) norm, is proposed to enhance the robustness of the proposed method.
  arXiv  Detail & Related papers  (2022-04-22T11:38:10Z)
• Factorization Approach for Low-complexity Matrix Completion Problems: Exponential Number of Spurious Solutions and Failure of Gradient Methods [18.16094563534453]
  It is well-known that the Burer-Monteiro (B-M) factorization approach can efficiently solve low-rank matrix optimization problems under the RIP condition. It is natural to ask whether B-M factorization-based methods can succeed on any low-rank matrix optimization problems with a low information-theoretic complexity.
  arXiv  Detail & Related papers  (2021-10-19T21:52:14Z)
• Hybrid Trilinear and Bilinear Programming for Aligning Partially Overlapping Point Sets [85.71360365315128]
  In many applications, we need algorithms which can align partially overlapping point sets are invariant to the corresponding corresponding RPM algorithm. We first show that the objective is a cubic bound function. We then utilize the convex envelopes of trilinear and bilinear monomial transformations to derive its lower bound. We next develop a branch-and-bound (BnB) algorithm which only branches over the transformation variables and runs efficiently.
  arXiv  Detail & Related papers  (2021-01-19T04:24:23Z)
• Sparse PCA via $l_{2,p}$-Norm Regularization for Unsupervised Feature Selection [138.97647716793333]
  We propose a simple and efficient unsupervised feature selection method, by combining reconstruction error with $l_2,p$-norm regularization. We present an efficient optimization algorithm to solve the proposed unsupervised model, and analyse the convergence and computational complexity of the algorithm theoretically.
  arXiv  Detail & Related papers  (2020-12-29T04:08:38Z)
• Meta-learning based Alternating Minimization Algorithm for Non-convex Optimization [9.774392581946108]
  We propose a novel solution for challenging non-problems of multiple variables. Our proposed approach is able to achieve effective iterations in cases while other methods would typically fail.
  arXiv  Detail & Related papers  (2020-09-09T10:45:00Z)
• Follow the bisector: a simple method for multi-objective optimization [65.83318707752385]
  We consider optimization problems, where multiple differentiable losses have to be minimized. The presented method computes descent direction in every iteration to guarantee equal relative decrease of objective functions.
  arXiv  Detail & Related papers  (2020-07-14T09:50:33Z)

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.