Quick approximation to matrices and applications

We give algorithms to find the following simply described approximation to a given matrix. Given an mxn matrix A with entries between say -1 and 1, and an error parameter epsilon between 0 and 1, we find a matrix D (implicitly) which is the sum of 0(1/epsilon(2)) simple rank 1 matrices so that the sum of entries of any submatrix (among the 2(m+n)) of (A - D) is at most epsilon mn in absolute value. Our algorithm takes time dependent only on epsilon and the allowed probability of failure (not on m,n). We draw on two lines of research to develop the algorithms: one is built around the fundamental Regularity Lemma of Szemeredi in Graph Theory and the constructive version of Alon, Duke, Leffman, Rodl and Yuster. The second one is from the papers of Arora, Karger and Karpinski, Fernandez de la Vega and most directly Goldwasser, Goldreich and Ron who develop approximation algorithms for a set of graph problems, typical of which is the maximum cut problem. From our matrix approximation, the above graph algorithms and the Regularity Lemma and several other results follow in a simple way. We generalize our approximations to multi-dimensional arrays and from that derive approximation algorithms for all dense Max-SNP problems.