Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userImproved Algorithms for Exact and Approximate Boolean Matrix Decomposition
80
0
0.0
(
0
)
Added by
Tsunehiko Kameda
Publication date
2015
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
An arbitrary $mtimes n$ Boolean matrix $M$ can be decomposed {em exactly} as $M =Ucirc V$, where $U$ (resp. $V$) is an $mtimes k$ (resp. $ktimes n$) Boolean matrix and $circ$ denotes the Boolean matrix multiplication operator. We first prove an exact formula for the Boolean matrix $J$ such that $M =Mcirc J^T$ holds, where $J$ is maximal in the sense that if any 0 element in $J$ is changed to a 1 then this equality no longer holds. Since minimizing $k$ is NP-hard, we propose two heuristic algorithms for finding suboptimal but good decomposition. We measure the performance (in minimizing $k$) of our algorithms on several real datasets in comparison with other representative heuristic algorithms for Boolean matrix decomposition (BMD). The results on some popular benchmark datasets demonstrate that one of our proposed algorithms performs as well or better on most of them. Our algorithms have a number of other advantages: They are based on exact mathematical formula, which can be interpreted intuitively. They can be used for approximation as well with competitive coverage. Last but not least, they also run very fast. Due to interpretability issues in data mining, we impose the condition, called the column use condition, that the columns of the factor matrix $U$ must form a subset of the columns of $M$.
rate research
Read More
We show that Boolean matrix multiplication, computed as a sum of products of column vectors with row vectors, is essentially the same as Warshalls algorithm for computing the transitive closure matrix of a graph from its adjacency matrix. Warshalls algorithm can be generalized to Floyds algorithm for computing the distance matrix of a graph with weighted edges. We will generalize Boolean matrices in the same way, keeping matrix multiplication essentially equivalent to the Floyd-Warshall algorithm. This way, we get matrices over a semiring, which are similar to the so-called funny matrices. We discuss our implementation of operations on Boolean matrices and on their generalization, which make use of vector instructions.
It has been proved that almost all $n$-bit Boolean functions have exact classical query complexity $n$. However, the situation seemed to be very different when we deal with exact quantum query complexity. In this paper, we prove that almost all $n$-bit Boolean functions can be computed by an exact quantum algorithm with less than $n$ queries. More exactly, we prove that ${AND}_n$ is the only $n$-bit Boolean function, up to isomorphism, that requires $n$ queries.
The subject of this textbook is the analysis of Boolean functions. Roughly speaking, this refers to studying Boolean functions $f : {0,1}^n to {0,1}$ via their Fourier expansion and other analytic means. Boolean functions are perhaps the most basic object of study in theoretical computer science, and Fourier analysis has become an indispensable tool in the field. The topic has also played a key role in several other areas of mathematics, from combinatorics, random graph theory, and statistical physics, to Gaussian geometry, metric/Banach spaces, and social choice theory. The intent of this book is both to develop the foundations of the field and to give a wide (though far from exhaustive) overview of its applications. Each chapter ends with a highlight showing the power of analysis of Boolean functions in different subject areas: property testing, social choice, cryptography, circuit complexity, learning theory, pseudorandomness, hardness of approximation, concrete complexity, and random graph theory. The book can be used as a reference for working researchers or as the basis of a one-semester graduate-level course. The author has twice taught such a course at Carnegie Mellon University, attended mainly by graduate students in computer science and mathematics but also by advanced undergraduates, postdocs, and researchers in adjacent fields. In both years most of Chapters 1-5 and 7 were covered, along with parts of Chapters 6, 8, 9, and 11, and some additional material on additive combinatorics. Nearly 500 exercises are provided at the ends of the books chapters.
For a function $gcolon{0,1}^mto{0,1}$, a function $fcolon {0,1}^nto{0,1}$ is called a $g$-polymorphism if their actions commute: $f(g(mathsf{row}_1(Z)),ldots,g(mathsf{row}_n(Z))) = g(f(mathsf{col}_1(Z)),ldots,f(mathsf{col}_m(Z)))$ for all $Zin{0,1}^{ntimes m}$. The function $f$ is called an approximate polymorphism if this equality holds with probability close to $1$, when $Z$ is sampled uniformly. We study the structure of exact polymorphisms as well as approximate polymorphisms. Our results include: - We prove that an approximate polymorphism $f$ must be close to an exact polymorphism; - We give a characterization of exact polymorphisms, showing that besides trivial cases, only the functions $g = mathsf{AND}, mathsf{XOR}, mathsf{OR}, mathsf{NXOR}$ admit non-trivial exact polymorphisms. We also study the approximate polymorphism problem in the list-decoding regime (i.e., when the probability equality holds is not close to $1$, but is bounded away from some value). We show that if $f(x land y) = f(x) land f(y)$ with probability larger than $s_land approx 0.815$ then $f$ correlates with some low-degree character, and $s_land$ is the optimal threshold for this property. Our result generalize the classical linearity testing result of Blum, Luby and Rubinfeld, that in this language showed that the approximate polymorphisms of $g = mathsf{XOR}$ are close to XORs, as well as a recent result of Filmus, Lifshitz, Minzer and Mossel, showing that the approximate polymorphisms of AND can only be close to AND functions.
Boolean network models have gained popularity in computational systems biology over the last dozen years. Many of these networks use canalizing Boolean functions, which has led to increased interest in the study of these functions. The canalizing depth of a function describes how many canalizing variables can be recursively picked off, until a non-canalizing function remains. In this paper, we show how every Boolean function has a unique algebraic form involving extended monomial layers and a well-defined core polynomial. This generalizes recent work on the algebraic structure of nested canalizing functions, and it yields a stratification of all Boolean functions by their canalizing depth. As a result, we obtain closed formulas for the number of n-variable Boolean functions with depth k, which simultaneously generalizes enumeration formulas for canalizing, and nested canalizing functions.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
