Approximation Algorithms for 0 -Low Rank Approximation
We study the 0 -Low Rank Approximation Problem, where the goal is, given an m × n matrix A, to output a rank-k matrix A for which A − A 0 is minimized. Here, for a matrix B, B 0 denotes the number of its non-zero entries. This NPhard variant of low rank approximation is natural for problems with no underlying metric, and its goal is to minimize the number of disagreeing data positions. We provide approximation algorithms which significantly improve the running time and approximation factor of previous work. For k > 1, we show how to find, in poly(mn) time for every k, a rank O(k log(n/k)) matrix A for which
To the best of our knowledge, this is the first algorithm with provable guarantees for the 0 -Low Rank Approximation Problem for k > 1, even for bicriteria algorithms. For the well-studied case when k = 1, we give a (2+ )-approximation in sublinear time, which is impossible for other variants of low rank approximation such as for the Frobenius norm. We strengthen this for the well-studied case of binary matrices to obtain a (1 + O(ψ))-approximation in sublinear time, where ψ = OPT / A 0 . For small ψ, our approximation factor is 1 + o(1).
This paper considers the problem of approximating matrices when no clear metric is present on the data and the l_0 norm is used (the number of non-zero elements in the difference between the original data and the approximation).
A low-rank solution is proposed.
The paper doesn't seem to give a practical case where this is useful.
In fact, "low rank" implies some linearity and hence implicitly a metric, which lay not make a lot of sense if we can't interprete the data with a metric to start with.  E.g., for k=1 one can easily make the first row and then one element in each other row of A-A' equal to zero (so 2n-1 elements), but then predicting linearly the values of the other elements seems arbitrarily.
Also, if the elements in A are continuous variables drawn from a distribution with no linear properties, the probability that for any low rank approximation A' more than these minimal number of elements of A-A' can be made equal to *exactly* zero (the requirement of the l_0 norm) is equal to 0.
In that sense, if the data is drawn randomly from a continuous distribution, with very high probability, OPT^{(k)} is something like (n-k)(m-k).  If k is "low", then theorems as Theorem 2 talking about multiples of OPT^{(k)} are rather trivial (because O(k^2) OPT^{(k)} > 2.OPT^{(k)} > mn) for "random" data.
So maybe the problem is to "discover" that by some external cause the data is very close already to low rank, in the sense that a lot of elements happen to match exactly the linear low rank relation to other elements.
In amongst others line 272, the authors too indicate that the work is most interesting if A is already close to low rank.
The mathematical elaboration and randomized algorithms are quite interesting from a theory point of view.
Moving some details to the supplementary material, and making a consistent story connecting the presented algorithms to clear learning problems, could make this a nice paper.
Some details:
* Line 48: supplementary -> supplementary material
* Line 244: having two times "w.h.p." in the same statement is not really necessary (but could be a compact way to present the result).