Approximation Schemes for Low-rank Binary Matrix Approximation Problems

DOI10.1145/3365653MaRDI QIDQ4973060zbMATH OpenOpenAlexWikidataFDO

Authors Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh

Publication date 2 December 2019

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1807.07156

zbMATH Keywords

approximation schemebinary matrix factorizationclusteringrandom sampling

Mathematics Subject Classification ID

Factorization of matrices (15A23) Matrices over special rings (quaternions, finite fields, etc.) (15B33) Randomized algorithms (68W20) Approximation algorithms (68W25) Analysis of algorithms (68W40)

Abstract: We provide a randomized linear time approximation scheme for a generic problem about clustering of binary vectors subject to additional constrains. The new constrained clustering problem encompasses a number of problems and by solving it, we obtain the first linear time-approximation schemes for a number of well-studied fundamental problems concerning clustering of binary vectors and low-rank approximation of binary matrices. Among the problems solvable by our approach are extsc{Low GF(2)-Rank Approximation}, extsc{Low Boolean-Rank Approximation}, and various versions of extsc{Binary Clustering}. For example, for extsc{Low GF(2)-Rank Approximation} problem, where for an $mimesn$ binary matrix $A$ and integer $r>0$, we seek for a binary matrix $B$ of $G{F}_2$ rank at most $r$ such that $el{l}_0$ norm of matrix $A-B$ is minimum, our algorithm, for any $epsilon>0$ in time $f(r,epsilon)cdotncdotm$, where $f$ is some computable function, outputs a $(1+epsilon)$-approximate solution with probability at least $(1-frac1e)$. Our approximation algorithms substantially improve the running times and approximation factors of previous works. We also give (deterministic) PTASes for these problems running in time $n^{f(r)frac1epsilo{n}^{2}logfrac1epsilon}$, where $f$ is some function depending on the problem. Our algorithm for the constrained clustering problem is based on a novel sampling lemma, which is interesting in its own.

Recommendations

• Parameterized low-rank binary matrix approximation
• Parameterized low-rank binary matrix approximation
• Low-Rank Binary Matrix Approximation in Column-Sum Norm.
• Low rank approximation of binary matrices: column subset selection and generalizations
• On low-complexity approximation of matrices
• Lower bounds for the low-rank matrix approximation
• Randomized algorithms for the low-rank approximation of matrices
• Generalized low rank approximations of matrices
• Generalized low rank approximations of matrices
• Low-rank approximation of a matrix: novel insights, new progress, and extensions

Cited in

(10)

• A PTAS for a class of binary non-linear programs with low-rank functions
• Parameterized low-rank binary matrix approximation
• On the parameterized complexity of clustering problems for incomplete data
• A clustering approach to constrained binary matrix factorization
• Parameterized low-rank binary matrix approximation
• Low rank approximation of binary matrices: column subset selection and generalizations
• Linear time approximation schemes for the Gale-Berlekamp game and related minimization problems
• Parameterized complexity of categorical clustering with size constraints
• Parameterized complexity of feature selection for categorical data clustering
• Parameterized complexity of categorical clustering with size constraints

This page was built for publication: Approximation Schemes for Low-rank Binary Matrix Approximation Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4973060)