Low rank matrix approximation is an important tool in machine learning. Given a data matrix, low rank approximation helps to find factors, patterns and provides concise representations for the data. Research on low rank approximation usually focus on real matrices. However, in many applications data are binary (categorical) rather than continuous. This leads to the problem of low rank approximation of binary matrix. Here we are given a @math binary matrix @math and a small integer @math . The goal is to find two binary matrices @math and @math of sizes @math and @math respectively, so that the Frobenius norm of @math is minimized. There are two models of this problem, depending on the definition of the dot product of binary vectors: The @math model and the Boolean semiring model. Unlike low rank approximation of real matrix which can be efficiently solved by Singular Value Decomposition, approximation of binary matrix is @math -hard even for @math . In this paper, we consider the problem of Column Subset Selection (CSS), in which one low rank matrix must be formed by @math columns of the data matrix. We characterize the approximation ratio of CSS for binary matrices. For @math model, we show the approximation ratio of CSS is bounded by @math and this bound is asymptotically tight. For Boolean model, it turns out that CSS is no longer sufficient to obtain a bound. We then develop a Generalized CSS (GCSS) procedure in which the columns of one low rank matrix are generated from Boolean formulas operating bitwise on columns of the data matrix. We show the approximation ratio of GCSS is bounded by @math , and the exponential dependency on @math is inherent.
We have surveyed one approach to understanding complexity issues for certain easily computable natural functions. Shifting graphs have been seen to account accurately and in a unified way for the superlinear complexity of several problems for various restricted models of computation. To attack "unrestricted" models (in the present context combinational circuits or straight-line arithmetic programs,) a first attempt, through superconcentrators, fails to provide any lower bounds although it does give counter-examples to alternative approaches. The notion of rigidity, however, does offer for the first time a reduction of relevant computational questions to noncomputional properties. The "reduction" consists of the conjunction of Corollary 6.3 and Theorem 6.4 which show that "for most sets of linear forms over the reals the stated algebraic and combinatorial reasons account for the fact that they cannot be computed in linear time and depth O(log n) simultaneously." We have outlined some problem areas which our preliminary results raise, and feel that further progress on most of these is humanly feasible. We would be interested in alternative approaches also.