Sampling from large matrices

We study random submatrices of a large matrix A . We show how to approximately compute A from its random submatrix of the smallest possible size O ( r log r ) with a small error in the spectral norm, where r = ‖ A ‖ 2 F /‖ A ‖ 2 2 is the numerical rank of A . The numerical rank is always bounded by, and is a stable relaxation of, the rank of A . This yields an asymptotically optimal guarantee in an algorithm for computing low-rank approximations of A . We also prove asymptotically optimal estimates on the spectral norm and the cut-norm of random submatrices of A . The result for the cut-norm yields a slight improvement on the best-known sample complexity for an approximation algorithm for MAX-2CSP problems. We use methods of Probability in Banach spaces, in particular the law of large numbers for operator-valued random variables.