  We provide a number of algorithmic results for the following family of
problems: For a given binary m\times n matrix A and integer k, decide whether
there is a "simple" binary matrix B which differs from A in at most k entries.
For an integer r, the "simplicity" of B is characterized as follows.
  - Binary r-Means: Matrix B has at most r different columns. This problem is
known to be NP-complete already for r=2. We show that the problem is solvable
in time 2^{O(k\log k)}\cdot(nm)^{O(1)} and thus is fixed-parameter tractable
parameterized by k. We prove that the problem admits a polynomial kernel when
parameterized by r and k but it has no polynomial kernel when parameterized by
k only unless NP\subseteq coNP/poly. We also complement these result by showing
that when being parameterized by r and k, the problem admits an algorithm of
running time 2^{O(r\cdot \sqrt{k\log{(k+r)}})}(nm)^{O(1)}, which is
subexponential in k for r\in O(k^{1/2 -\epsilon}) for any \epsilon>0.
  - Low GF(2)-Rank Approximation: Matrix B is of GF(2)-rank at most r. This
problem is known to be NP-complete already for r=1. It also known to be
W[1]-hard when parameterized by k. Interestingly, when parameterized by r and
k, the problem is not only fixed-parameter tractable, but it is solvable in
time 2^{O(r^{ 3/2}\cdot \sqrt{k\log{k}})}(nm)^{O(1)}, which is subexponential
in k.
  - Low Boolean-Rank Approximation: Matrix B is of Boolean rank at most r. The
problem is known to be NP-complete for k=0 as well as for r=1. We show that it
is solvable in subexponential in k time 2^{O(r2^r\cdot \sqrt{k\log
k})}(nm)^{O(1)}.
