Quick Approximation to Matrices and Applications

×n matrix A with entries between say −1 and 1, and an error parameter e between 0 and 1, we find a matrix D (implicitly) which is the sum of \(\) simple rank 1 matrices so that the sum of entries of any submatrix (among the \(\)) of (A−D) is at most emn in absolute value. Our algorithm takes time dependent only on e and the allowed probability of failure (not on m, n).