This is an announcement for the paper "Sampling from large matrices: an approach through geometric functional analysis" by Mark Rudelson and Roman Vershynin.

Abstract: We study random submatrices of a large matrix A. We show how to approximately compute A from its random submatrix. This improves known algorithms for computing low-rank approximations of large matrices. We also estimate norms of random submatrices of A. This yields an improved approximation algorithm for all MAX-2CSP problems (which includes MAX-CUT and other graph problems). Our results are essentially dimension-free; the picture is only controlled by the norms of the matrix and not by its size or rank. We use methods of Probability in Banach spaces, in particular the law of large numbers for random operators.

Archive classification: Functional Analysis; Numerical Analysis

Mathematics Subject Classification: 15A60, 68W20, 15A18

The source file(s), rv-random-submatrices.tex: 50699 bytes, is(are) stored in gzipped form as 0503442.gz with size 16kb. The corresponding postcript file has gzipped size 82kb.

Submitted from: vershynin@math.ucdavis.edu

The paper may be downloaded from the archive by web browser from URL

http://front.math.ucdavis.edu/math.FA/0503442

or

http://arXiv.org/abs/math.FA/0503442

or by email in unzipped form by transmitting an empty message with subject line

uget 0503442

or in gzipped form by using subject line

get 0503442

to: math@arXiv.org.