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||_F^2 / ||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.

In the paper "Isoperimetry of waists and local versus global asymptotic convex geometries", it was proved that the existence of nicely bounded sections of two symmetric convex bodies K and L implies that the intersection of randomly rotated K and L is nicely bounded. In this appendix, we achieve a polynomial bound on the diameter of that intersection (in the ratio of the dimensions of the sections).

We prove that an n by n random matrix G with independent entries is completely delocalized. Suppose the entries of G have zero means, variances uniformly bounded below, and a uniform tail decay of exponential type. Then with high probability all unit eigenvectors of G have all coordinates of magnitude O(n^{-1/2}), modulo logarithmic corrections. This comes a consequence of a new, geometric, approach to delocalization for random matrices.

We prove two basic conjectures on the distribution of the smallest singular value of random n times n matrices with independent entries. Under minimal moment assumptions, we show that the smallest singular value is of order n^{-1/2}, which is optimal for Gaussian matrices. Moreover, we give a optimal estimate on the tail probability. This comes as a consequence of a new and essentially sharp estimate in the Littlewood-Offord problem: for i.i.d. random variables X_k and real numbers a_k, determine the probability P that the sum of a_k X_k lies near some number v. For arbitrary coefficients a_k of the same order of magnitude, we show that they essentially lie in an arithmetic progression of length 1/p.

We develop an approach through geometric functional analysis to error correcting codes and to reconstruction of signals from few linear measurements. An error correcting code encodes an n-letter word x into an m-letter word y in such a way that x can be decoded correctly when any r letters of y are corrupted. We prove that most linear orthogonal transformations Q from R^n into R^m form efficient and robust robust error correcting codes over reals. The decoder (which corrects the corrupted components of y) is the metric projection onto the range of Q in the L_1 norm. An equivalent problem arises in signal processing: how to reconstruct a signal that belongs to a small class from few linear measurements? We prove that for most sets of Gaussian measurements, all signals of small support can be exactly reconstructed by the L_1 norm minimization. This is a substantial improvement of recent results of Donoho and of Candes and Tao. An equivalent problem in combinatorial geometry is the existence of a polytope with fixed number of facets and maximal number of lower-dimensional facets. We prove that most sections of the cube form such polytopes.

We prove that with high probability, every eigenvector of a random matrix is delocalized in the sense that any subset of its coordinates carries a non-negligible portion of its $\ell_2$ norm. Our results pertain to a wide class of random matrices, including matrices with independent entries, symmetric and skew-symmetric matrices, as well as some other naturally arising ensembles. The matrices can be real and complex; in the latter case we assume that the real and imaginary parts of the entries are independent.

We want to exactly reconstruct a sparse signal f (a vector in R^n of small support) from few linear measurements of f (inner products with some fixed vectors). A nice and intuitive reconstruction by Linear Programming has been advocated since 80-ies by Dave Donoho and his collaborators. Namely, one can relax the reconstruction problem, which is highly nonconvex, to a convex problem -- and, moreover, to a linear program. However, when is exactly the reconstruction problem equivalent to its convex relaxation is an open question. Recent work of many authors shows that the number of measurements k(r,n) needed to exactly reconstruct any r-sparse signal f of length n (a vector in R^n of support r) from its linear measurements with the convex relaxation method is usually O(r polylog(n)). However, known estimates of the number of measurements k(r,n) involve huge constants, in spite of very good performance of the algorithms in practice. In this paper, we consider random Gaussian measurements and random Fourier measurements (a frequency sample of f). For Gaussian measurements, we prove the first guarantees with reasonable constants: k(r,n) < 12 r (2 + log(n/r)), which is optimal up to constants. For Fourier measurements, we prove the best known bound k(r,n) = O(r log(n) . log^2(r) log(r log n)), which is optimal within the log log n and log^3 r factors. Our arguments are based on the technique of Geometric Functional Analysis and Probability in Banach spaces.

Let A be a matrix whose entries are real i.i.d. centered random variables with unit variance and suitable moment assumptions. Then the smallest singular value of A is of order n^{-1/2} with high probability. The lower estimate of this type was proved recently by the authors; in this note we establish the matching upper estimate.

We study concentration properties of random vectors of the form $AX$, where $X = (X_1, ..., X_n)$ has independent coordinates and $A$ is a given matrix. We show that the distribution of $AX$ is well spread in space whenever the distributions of $X_i$ are well spread on the line. Specifically, assume that the probability that $X_i$ falls in any given interval of length $T$ is at most $p$. Then the probability that $AX$ falls in any given ball of radius $T \|A\|_{HS}$ is at most $(Cp)^{0.9 r(A)}$, where $r(A)$ denotes the stable rank of $A$ and $C$ is an absolute constant.

We find a sharp combinatorial bound for the metric entropy of sets in R^n and general classes of functions. This solves two basic combinatorial conjectures on the empirical processes. 1. A class of functions satisfies the uniform Central Limit Theorem if the square root of its combinatorial dimension is integrable. 2. The uniform entropy is equivalent to the combinatorial dimension under minimal regularity. Our method also constructs a nicely bounded coordinate section of a symmetric convex body in R^n. In the operator theory, this essentially proves for all normed spaces the restricted invertibility principle of Bourgain and Tzafriri.