, , , November 27, 2006

This paper studies random submatrices of a large matrix

A

. The study of random submatrices spans several decades and is related to diverse areas of mathematics and computer science. Two main reasons for the interest in random submatrices are:

(1) one can learn a matrix $A$ from its random submatrices;
(2) properties of a matrix $A$ may improve by passing to its random submatrices.

We address both aspects of random submatrices in this paper. We show how to approximate

A

by its random submatrix in the spectral norm, and we compute the asymptotics of the spectral and the cut norms of random submatrices. We look for a dimension-free picture, which is only controlled by the norms of the matrix

A

and not by its size (or rank). This yields improvements upon known algorithms for computing low rank approximations, Singular Value Decompositions, and approximations to MAX-2CSP problems.

1.1 The spectral norm: low rank approximations and SVD

Can one approximate

A

by only knowing a random submatrix of

A

of a fixed size?

One is especially interested in the sample complexity of this problem, the minimal size of a submatrix which yields a good approximation with a small error in some natural norm, and with high probability.

This problem belongs to a class of problems the Statistical Learning Theory is concerned with. These problems inevitably bear the assumption that the the object to be learned belongs to a relatively small “target” class. To be able to learn

A

from a matrix of small size thus of small rank, we have to assume that

A

itself has small rank–or can be approximated by an (unknown) matrix of a small rank. We thus strive to find a low rank approximation to a matrix

A

, whenever such an approximation exists, from only knowing a small random submatrix of

A

Solving this problem is essential for development of fast Monte-Carlo algorithms for computations on large matrices. An extremely large matrix

A

– say, of the order of

10^{5} \times 10^{5}

– is impossible to upload into the Random Access Memory (RAM) of a computer; it is instead stored in an external memory. On the other hand, sampling a small submatrix of

A

, storing it in RAM and computing its small rank approximation is feasible.

The crucial assumption that

A

is essentially a low rank matrix holds in many applications. For example, this is a model hypothesis in the Latent Semantic Indexing (see [6, 21, 4, 9, 5, 2] ). There

A

is the “document-term matrix”, which is formed of the frequencies of occurrence of various terms in the documents of a large collection. The hypothesis that the documents are related to a small number of (unknown) topics translates into the assumption that

A

can be approximated by an (unknown) low rank matrix. Finding such an approximation would determine the “best” topics the collection is really about. Other examples where this problem arises include clustering of graphs [10] , DNA microarray data, facial recognition, web search (see [12] ), lossy data compression and cryptography (see [5] ).

The best fixed rank approximation to

A

is obviously given by the partial sums of the Singular Value Decomposition (SVD)

A = \sum_{j} σ_{j} (A) u_{j} \otimes v_{j}

where

σ_{j} (A)

is the nonincreasing and nonnegative sequence of the singular values of

A

, and

u_{j}

and

v_{j}

are left and right singular vectors of

A

respectively. The best rank

k

approximation to

A

in both the spectral and Frobenius norms¹ is thus

A P_{k}

, where

P_{k}

is the orthogonal projection onto the top

k

left singular vectors of

A

. In particular, for the spectral norm we have

\begin{matrix} {min}_{B, r a n k B \leq k} ∥ A - B ∥ = ∥ A - A P_{k} ∥ = σ_{k + 1} (A) . \end{matrix}

(1)

However, computing

P_{k}

, which gives the first elements of the SVD of a

m \times n

matrix

A

, is often impossible in practice because (1) it would take many passes through

A

, which is prohibitively slow for a matrix stored in an external memory; (2) this would take superlinear time in

m + n

. Instead, it was proposed in [16, 11, 12, 13] to use the Monte-Carlo methodology: namely, approximate the

k

-th partial sum of the SVD of

A

by the

k

-th partial sum of the SVD of a random submatrix of

A

. In this paper, we show that this can be done:

(1) with sample complexity $O (r log r)$ , that is by sampling only $O (r log r)$ random rows of $A$ , if $A$ is is approximable by a rank $r$ matrix;
(2) in one pass through $A$ if the matrix is stored row-by-row, and in two passes if its entries are stored in arbitrary order;
(3) using RAM space and time $O (n + m)$ (and polynomial in $r$ and $k$ ).

Theorem 1.1. Let

A

be an

m \times n

matrix, and

k > 0

be an integer. For

ɛ \in (0, 1)

, and let

\begin{matrix} d \geq C (\frac{r}{ɛ^{4}}) log (\frac{r}{ɛ^{4}}), where r = {∥ A ∥}_{F}^{2} / {∥ A ∥}^{2} . \end{matrix}

(2)

Let

\tilde{A}

be a

d \times n

matrix consisting of

d

normalized rows of

A

, picked independently with replacement, with probabilities proportional to the squares of their Euclidean lengths. Let

P_{k}

be the orthogonal projection onto the top

k

left singular vectors of

\tilde{A}

. Then with high probability

\begin{matrix} ∥ A - A P_{k} ∥ \leq σ_{k + 1} (A) + ɛ ∥ A ∥ . \end{matrix}

(3)

Here and in the sequel,

C, c, C_{1}, \dots

denote positive absolute constants.

Comparing 3 with the best approximation 1 given by the SVD, we see an additional error

ɛ ∥ A ∥

which can be made small by increasing the size

d

of the sample.

¹ the spectral norm is the operator norm $l_{2} \to l_{2}$ , that is $∥ A ∥ = {sup}_{| x | = 1} | A x | = σ_{1} (A)$ ; the Frobenius (Hilbert-Schmidt) norm is defined as $∥ A ∥_{F}^{2} = \sum_{i, j} | A_{i j} |^{2} = \sum_{j} σ_{j}^{2}$ .

1.1.1 Sample complexity.

The approximation scheme in Theorem 1.1 is not new; it was developed in [16, 11, 12, 13] .

However, the sample complexity

d

in Theorem 1.1 improves significantly upon the previously known estimates. The sample complexity is essentially linear in the “average sparsity”

r

of the matrix;

r

is obviously bounded by the rank of

A

. We can view

r

as a relaxation of the rank, which is stable under small perturbations of

A

(unlike the rank itself !) Thus for matrices

A

which are essentially low-rank matrices,

r

is also small.

This complexity is optimal in many natural cases. For example, if

A

is a matrix of an orthogonal projection, then one must have

r a n k (A P_{k}) \geq r a n k (A)

for a meaningful approximation of

A

A P_{k}

. But

r a n k (A P_{k}) \leq r a n k P_{k} \leq d

, thus

d \geq r a n k (A)

. One can also show that the logarithm is needed in 2 .

1.1.2 Law of large numbers for operator-valued random variables

The new feature in our proof of Theorem 1.1 is a use of the first author's argument about random vectors in the isotropic position [22] . It yields a law of large numbers for operator-valued random variables. We apply it for independent copies of a rank one random operator, which is given by a random row of the matrix

A^{T} A

1.2 The cut-norm: decay, approximation to MAX-CSP problems

Alon, Fernandez de la Vega, Kannan and Karpinski [1, 3] reduced the question of finding additive approximations to the MAX-CSP problems (which are NP-hard) to computing the cut-norm of random submatrices.

The input of a MAX-2CSP problem is a set

F

m

distinct Boolean functions

f_{i}

n

Boolean variables

x_{j}

, where each function

f_{i}

depends on only two variables. The output

M a x (F)

is the maximal number of functions that can be simultaneously set to

1

by a truth assignment to the variables. This class of problems includes many graph problems, in particular the MAX-CUT problem, in which one wants to maximize, for a given graph, the number of edges that join a subset of vertices with its complement.

The exact problem is NP-hard. To approximately solve MAX-2CSP, it was proposed in [1, 3] to use the Monte-Carlo methodology, that is to approximate the problem by the induced problem on a small random sample of variables. For a subset

Q

of the variables

{x_{1}, \dots, x_{n}}

, then induced problem

F |_{Q}

consists of the functions from

F

that depend on the variables from

Q

. Our goal is to find the minimal

q

(the sample complexity) such that for random subset

Q

q

variables,

\begin{matrix} | M a x (F) - \frac{n^{2}}{q^{2}} M a x (F |_{Q}) | < ɛ n^{2} . \end{matrix}

(4)

(note that the maximal number of formulas in

F

and

F |_{Q}

is of order of

n^{2}

and

q^{2}

respectively).

Goldreich, Goldwasser and Ron [17] were first to find a polynomial time algorithm for approximating MAX-2CSP within the additive error

ɛ n^{2}

. The sample complexity in [17] was

q = O (ɛ^{- 5})

. Independently, Fernandez de la Vega [14] developed a different polynomial time algorithm for MAX-CUT. Alon, Fernandez de la Vega, Kannan and Karpinski [1, 3] improved the sample complexity in 4 to

q = O (ɛ^{- 4} log (1 / ɛ))

, which has remained best known up to now. Actually, the same sample complexity of this order was shown in [3] to be sufficient for all MAX-rCSP problems (in which the functions dpend on

r \geq 2

variables). By improving the central part of the argument of [3] , which is an estimate of the cut-norm of random submatrices, we shall reduce the sample complexity for MAX-2CSP to

q = O (ɛ^{- 2})

We shall call the random subset of expected cardinality

q

a subset of an

n

-element set formed by including each element independently with probability

q / n

Theorem 1.2. For any

ɛ > 0

, there exists a positive integer

q = O (ɛ^{- 2})

which satisfies the following. Let

F

be a collection of Boolean functions on

n

variables

x_{1}, \dots, x_{n}

, each function depending on two variables. Let

Q

be a random subset of the variables

{x_{1}, \dots, x_{n}}

of expected cardinality

q

Then 4 holds with high probability.

This result follows, by the argument of [3] , from an estimate of the cut-norm of random submatrices. The cut norm of an

n \times n

matrix

A

is the maximum sum of the entries of its sumbatrix,

∥ A ∥_{C} = {max}_{I, J} | \sum_{i \in I, j \in J} A_{i j} |

and it is equivalent to the

l_{\infty} \to l_{1}

operator norm. We want to see how the cut norm of

A

decreases when we pass to its random submatrix

A |_{Q \times Q} = (A_{i j})_{i, j \in Q}

, where

Q

is a random subset of

{1, \dots, n}

of expected cardinality

q

. Intuitively,

A |_{Q \times Q}

(q / n)^{2}

times smaller thatn

A

A

is diagonal-free, but only

(q / n)

times smaller than

A

A

is a diagonal matrix. The general case combines both types of decay:

Theorem 1.3. Let

A

be an

n \times n

matrix. Let

Q

be a random subset of

{1, \dots, n}

of expected cardinality

q

. Then

E ∥ A |_{Q \times Q} ∥_{C} \leq C {(\frac{q}{n})}^{2} ∥ A ∥_{C} + C (\frac{q}{n}) ∥ d i a g (A) ∥_{C} + C {(\frac{q}{n})}^{3 / 2} (∥ A ∥_{Col} + ∥ A^{T} ∥_{Col})

where

∥ A ∥_{Col}

is the sum of the Euclidean lengths of the columns of

A

, and

d i a g (A)

is the diagonal part of

A

Remark 1.4. Note that by Cauchy-Schwartz inequality

{∥ A ∥}_{Col} \leq \sqrt{n} {∥ A ∥}_{F}

This result improves in several ways the estimate from [3] . The argument of [3] is combinatorial, while our proof uses the technique of probability in normed spaces, and includes decoupling, symmetrization, and application of a version of Slepian's lemma for Bernoulli random variables due to Talagrand.

1.3 The spectral norm: decay

Perhaps the most important matrix norm is the spectral norm (the

l_{2} \to l_{2}

operator norm). Nevertheless, its decay under passing to submatrices has not been sufficiently understood. Given an

n \times n

matrix

A

, its submatrix

A |_{Q} = (A_{i j})_{i \in Q, j \leq n}

consists of the rows of

A

indexed by a subset

Q

. If

Q

is a random subset of epected cardinality

q

(as above), the length of any vector

x \in R^{n}

reduces by the factor of

\sqrt{\frac{q}{n}}

when one orthogonally projects

x

onto

R^{Q}

. One should then expect similar type of decay of the spectral norm–something like

E ∥ A |_{Q} ∥ \leq \sqrt{\frac{q}{n}} ∥ A ∥

. However, similarly to the previous section, the decay for diagonal matrices is different–for example, there is no decay at all for the identity matrix. The correct asymptotics in this case is given by

∥ A ∥_{(k)} = the average of k biggest Euclidean lengths of the columns of A,

with

k = n / q

. For diagonal matrices, it is the average of

k

biggest absolute values of the entries. General matrices again combines both types of decay:

Theorem 1.5. Let

A

be an

n \times n

matrix. Let

Q

be a random subset of

{1, \dots, n}

of expected cardinality

q

. Then the random submatrix

A |_{Q}

formed by the columns of

A

indexed by

Q

satisfies

E ∥ A |_{Q} ∥ \leq C \sqrt{\frac{q}{n}} ∥ A ∥ + C \sqrt{log q} ∥ A ∥_{(n / q)} .

Remark 1.6. The example considered in Remark 2.2 below shows that the coefficient

\sqrt{log q}

is necessary here. The same example implies that the logarithmic term is required in Theorem 1.1 as well.

Generalizing an earlier result of Lunin [20] , Kashin and Tzafriri [18] (see [25] ) essentially proved the existence of a subset

Q

of cardinality

δ n

and such that

∥ A |_{Q} ∥ \leq C \sqrt{\frac{q}{n}} ∥ A ∥ + C \frac{∥ A ∥_{F}}{\sqrt{n}} .

Note that

\frac{∥ A ∥_{F}}{\sqrt{n}} = {(\frac{1}{n} \sum_{i = 1}^{n} | A_{i} |^{2})}^{1 / 2}

is the average of the lengths of all columns of

A

As the example of diagonal operators shows, for random subsets

Q

this term has to be replaced by the average of the few biggest columns. Talagrand [23] proved deep results on the more general operator norms

l_{2} \to X

, where

X

is a

2

-smooth Banach space.

However, the decay on

\frac{q}{n}

in his results is logarithmic.

1.4 Dimension-free approach

Many problems on random submatrices, of both theoretical and practical importance, have functional-analytic rather than linear-algebraic nature. These problems, like those this paper considers, are about estimating operator norms. We thus see a matrix

A

as a linear operator

A

between finite dimensional normed spaces – say, between

l_{2}^{n}

and

l_{2}^{n}

for the spectral norm, and between

l_{\infty}^{n}

and

l_{1}^{n}

for the cut norm.

From this perspective, the dimension

n

of the underlying normed space should play a minor role, while the real control of the picture should be held by (hopefully few) quantities tied to the operator rather than the space. As a trivial example, if

A

is not of full rank then the dimension

n

of the range space is useless comparing to the rank of

A

. Further, we are looking for stable results, those not ruined by small perturbations of the linear operators – this is a natural demand in applications, and this differs our analytic perspective from the linear algebraic one. It would thus be natural to look for stable quantities tied to linear operators, which govern the picture. For example, operator norms are stable quantities, while the rank is not.

This paper advances a dimension free approach to matrices. The low rank approximations in Theorem 1.1 are only controlled by the average sparsity

r

of the matrix, which is a stable relaxation of the rank. The norms of random matrices in Theorems 1.3 and 1.5 are essentially controlled by the norms of the original matrix (and naturally by the sampling factor, the ratio of the size of the submatrix to the size of the original matrix). The size

n

of the matrix, which is the dimension of the space, does not play a separate role in these results.

Another part of this picture which we omitted in this paper is the invertibility of submatrices. Dimension-free versions of the invertibility results due to Bourgain and Tzafriri can be found in [25] , se also [8] for random submatrices.

Acknowledgement. This project started when the authors participated in the PIMS Thematic Programme on Asymptotic Geometric Analysis at the University of British Columbia in Summer 2002. The first author was a PIMS postdoctoral fellow at that time. We are grateful to PIMS for its hospitality. The final part of this research was done when the first authour visited University of California, Davis. We are also grateful for R. Kannan for his comments on the initial version of this manuscript.

2 Low rank approximations

In this section, we prove Theorem 1.1 and discuss the algorithm for finding low rank approximations. Our argument is based on the law of large numbers for operator-valued random variables.

2.1 Law of large numbers for operator-valued random variables

Theorem 1.1 is about random independent sampling the rows of the matrix

A

. The result of such sampling can be viewed as an empirical process taking values in the set of rows. If we sample enough rows, then the matrix constructed from them would nicely approximate the original matrix

A

in the spectral norm. For the scalar random variables, this effect is the classical Law of Large Numbers. For example, let

X

be a bounded random variable and let

X_{1} \dots X_{d}

be independent copies of

X

. Then Markov inequality implies

E | \frac{1}{d} \sum_{j = 1}^{d} X_{j} - E X | \leq \frac{C}{\sqrt{d}} .

The operator-valued analog of this inequality is harder to prove. In this case instead of estimating the absolute value of the difference between the sample mean and the expectation, we have to estimate the norm. Thus instead the large deviation estimate for a single random variable, we have to deal with estimating the supremum of a random process. This requires deeper probabilistic techniques. The following Theorem generalizes the main result of [22] .

Theorem 2.1. Let

y

be a random vector in

R^{n}

. Assume for normalization that

∥ E y \otimes y ∥ = 1

. Let

d

be a natural number and let

y_{1} \dots y_{d}

be independent copies of

y

. Then

E ‖ \frac{1}{d} \sum_{i = 1}^{d} y_{i} \otimes y_{i} - E y \otimes y ‖ \leq C \cdot \frac{\sqrt{log d}}{\sqrt{d}} \cdot {(E {∥ y ∥}^{log d})}^{1 / log d},

provided that the last expression is smaller than

1

Remark 2.2. This estimate is in general optimal. A simplest example is

A = I

, the identity matrix in

R^{n}

. Let us sample random rows of

A

(scaled by

\sqrt{n}

for normalization); this amounts to the random vector

X

taking values

\sqrt{n} e_{1}, \dots, \sqrt{n} e_{n}

each with probability

1 / n

, where

(e_{i})

is the canonical basis of

R^{n}

Then

E X \otimes X = I

. Here and in the sequel, by

u \otimes v

we denote the linear operator whose matrix is

u^{T} v

. We wish to replace this mean by the sample mean

\frac{1}{d} \sum_{j = 1}^{d} X_{j} \otimes X_{j}

, where

X_{1} \dots X_{d}

are independent copies of

X

. Then

E ‖ \frac{1}{d} \sum_{j = 1}^{d} X_{j} \otimes X_{j} - I ‖ = E {max}_{i = 1 \dots n} | \frac{n}{d} | {j | X_{j} = \sqrt{n} e_{i}} | - 1 | .

If we want this quantity to be

O (1)

, then it is not hard to check that

d

should be of order at least

n log n

. Therefore, the coefficient

\sqrt{log d} / \sqrt{d}

in Theorem 2.1 is optimal.

2.2 Proof of Theorem 2.1 .

The proof consists of two steps. First we introduce a Rademacher series that majorizes the expectation of the norm. Then we use the main Lemma of [22] to obtain a bound for it.

The first step is relatively standard. Let

ɛ_{1} \dots ɛ_{d}

be independent Bernoulli variables taking values

1, - 1

with probability

1 / 2

and let

y_{1} \dots y_{d}, {\bar{y}}_{1} \dots {\bar{y}}_{d}

be independent copies of

y

. Denote

E_{y}, E_{ɛ}

the expectation according to

y

and

ɛ

respectively. Since

y_{i} \otimes y_{i} - {\bar{y}}_{i} \otimes {\bar{y}}_{i}

is a symmetric random variable, we have

\begin{matrix} E_{y} ‖ \frac{1}{d} \sum d i = 1 y_{i} \otimes y_{i} - E y \otimes y ‖ \leq E_{y} E_{\bar{y}} ‖ \frac{1}{d} \sum d i = 1 y_{i} \otimes y_{i} - \frac{1}{d} \sum d i = 1 {\bar{y}}_{i} \otimes {\bar{y}}_{i} ‖ = \end{matrix}

\begin{matrix} E_{ɛ} E_{y} E_{\bar{y}} ‖ \frac{1}{d} \sum d i = 1 ɛ_{i} (y_{i} \otimes y_{i} - {\bar{y}}_{i} \otimes {\bar{y}}_{i}) ‖ \leq 2 E_{y} E_{ɛ} ‖ \frac{1}{d} \sum d i = 1 ɛ_{i} y_{i} \otimes y_{i} ‖ . \end{matrix}

\begin{matrix}  \end{matrix}

To estimate the last expectation, we need the following Lemma [22] .

Lemma 2.3. Let

y_{1} \dots y_{N}

be vectors in

R^{l}

and let

ɛ_{1} \dots ɛ_{N}

be independent Bernoulli variables taking values

1, - 1

with probability

1 / 2

. Then

E ‖ \sum_{i = 1}^{N} ɛ_{i} y_{i} \otimes y_{i} ‖ \leq C \sqrt{log l} \cdot {max}_{i = 1 \dots N} ∥ y_{i} ∥ \cdot {‖ \sum_{i = 1}^{N} y_{i} \otimes y_{i} ‖}^{1 / 2} .

Remark 2.4. We can consider the vectors

y_{1} \dots y_{N}

as vectors in their linear span, so the dimension of the ambient space may be always assumed less or equal to

N

Applying the Lemma, we get

\begin{matrix} E ‖ \frac{1}{d} \sum d i = 1 y_{i} \otimes y_{i} - E y \otimes y ‖ \leq \end{matrix}

\begin{matrix} C \cdot \frac{\sqrt{log d}}{d} \cdot & {(E {max}_{i = 1 \dots d} {∥ y_{i} ∥}^{2})}^{1 / 2} \cdot {(E ‖ \sum d i = 1 y_{i} \otimes y_{i} ‖)}^{1 / 2} . \end{matrix}

(5)

\begin{matrix}  \end{matrix}

We have

\begin{matrix} {(E {max}_{i = 1 \dots d} {∥ y_{i} ∥}^{2})}^{1 / 2} & \leq {(E {(\sum d i = 1 {∥ y_{i} ∥}^{log d})}^{2 / log d})}^{1 / 2} \end{matrix}

\begin{matrix} \leq d^{1 / log d} \cdot {(E {∥ y ∥}^{log d})}^{1 / log d} . \end{matrix}

\begin{matrix}  \end{matrix}

Thus, denoting

D = E ‖ \frac{1}{d} \sum d i = 1 y_{i} \otimes y_{i} - E y \otimes y ‖,

we obtain by 5

\begin{matrix} D & \leq C \cdot \frac{\sqrt{log d}}{\sqrt{d}} \cdot {(E {∥ y ∥}^{log d})}^{1 / log d} \cdot (D + 1)^{1 / 2} \end{matrix}

\begin{matrix} \leq C \cdot \frac{\sqrt{log d}}{\sqrt{d}} \cdot {(E {∥ y ∥}^{log d})}^{1 / log d} \cdot (D^{1 / 2} + 1) . \end{matrix}

\begin{matrix}  \end{matrix}

C \cdot \frac{\sqrt{log d}}{\sqrt{d}} \cdot {(E {∥ y ∥}^{log d})}^{1 / log d} \leq 1 / 2,

we get

D \leq 2 C \cdot \frac{\sqrt{log d}}{\sqrt{d}} \cdot {(E {∥ y ∥}^{log d})}^{1 / log d}

which completes the proof of Theorem 1.

2.3 Proof of Theorem 1.1

By the homogeneity, we can assume

∥ A ∥ = 1

The following lemma of Drineas and Kannan [11] (see also [12] ) reduces Theorem 1.1 to a comparison of

A

and a sample

\tilde{A}

in the spectral norm.

Lemma 2.5 (Drineas, Kannan).

\begin{matrix} ∥ A - A P_{k} ∥^{2} \leq σ_{k + 1} (A)^{2} + 2 ∥ A^{T} A - {\tilde{A}}^{T} \tilde{A} ∥ . \end{matrix}

(6)

Proof.

\begin{matrix} ∥ A - A P_{k} ∥^{2} & = {sup}_{x \in ker P_{k}, | x | = 1} ∥ A x ∥^{2} = {sup}_{x \in ker P_{k}, | x | = 1} 〈 A^{T} A x, x 〉 \end{matrix}

\begin{matrix} \leq {sup}_{x \in ker P_{k}, | x | = 1} 〈 (A^{T} A - {\tilde{A}}^{T} \tilde{A}) x, x 〉 + {sup}_{x \in ker P_{k}, | x | = 1} 〈 {\tilde{A}}^{T} \tilde{A} x, x 〉 \end{matrix}

\begin{matrix} = ∥ A^{T} A - {\tilde{A}}^{T} \tilde{A} ∥ + σ_{k + 1} ({\tilde{A}}^{T} \tilde{A}) . \end{matrix}

\begin{matrix}  \end{matrix}

By a result of perturbation theory,

| σ_{k + 1} (A^{T} A) - σ_{k + 1} ({\tilde{A}}^{T} \tilde{A}) | \leq ∥ A^{T} A - {\tilde{A}}^{T} \tilde{A} ∥

. This proves the claim.

For

j = 1 \dots m

let

x_{j}

be the

j

-th row of the matrix

A

. Then

A^{T} A = \sum_{j = 1}^{m} x_{j} \otimes x_{j} .

We shall view the matrix

A^{T} A

as the true mean of a bounded operator valued random variable, whereas

{\tilde{A}}^{T} \tilde{A}

will be its empirical mean; then we shall apply the Law of Large Numbers for operator-valued random variables, that is Theorem 2.1 . To this end, define a random vector

X \in R^{m}

P (X = \frac{{∥ A ∥}_{F}}{∥ x_{j} ∥} x_{j}) = \frac{{∥ x_{j} ∥}^{2}}{{∥ A ∥}_{F}^{2}} .

and let

X_{1} \dots X_{d}

be independent copies of

X

. Let the matrix

\tilde{A}

consist of rows

\frac{1}{\sqrt{d}} X_{1} \dots \frac{1}{\sqrt{d}} X_{d}

. (The normalization of

\tilde{A}

is different than in the statement of Theorem 1.1 : in the proof, it is convenient to multiply

\tilde{A}

by the factor

\frac{1}{\sqrt{d}} ∥ A ∥_{F}

. However note that the singular vectors of

\tilde{A}

and thus

P_{k}

do not change.) Then

A^{T} A = E X \otimes X, {\tilde{A}}^{T} \tilde{A} = \frac{1}{d} \sum d i = 1 X_{j} \otimes X_{j},

and

{(E {∥ X ∥}^{log d})}^{1 / log d} \leq sup ∥ X ∥ = {∥ A ∥}_{F} .

Applying Theorem 2.1 we get

E ‖ {\tilde{A}}^{T} \tilde{A} - A^{T} A ‖ \leq C \sqrt{\frac{log d}{d}} \cdot {∥ A ∥}_{F}

whenever the last quantity is less than 1. Let

δ < 1

be an absolute constant. Choose

d \geq C (r / δ^{2} ɛ^{4}) log (r / δ^{2} ɛ^{4})

, then

C \sqrt{\frac{log d}{d}} \cdot {∥ A ∥}_{F} < δ ɛ^{2} .

Hence, by Chebychev's inequality,

E ‖ {\tilde{A}}^{T} \tilde{A} - A^{T} A ‖ \leq ɛ^{2} / 2

with probability at least

1 - 2 δ

. Finally, by 6

∥ A - A P_{k} ∥ \leq σ_{k + 1} (A) + \sqrt{2} ∥ A^{T} A - {\tilde{A}}^{T} \tilde{A} ∥^{1 / 2} \leq σ_{k + 1} (A) + ɛ .

This proves Theorem 1.1 .

2.4 Algorithmic aspects of Theorem 1.1 .

Finding a good low rank approximation to a matrix

A

amounts, due to Theorem 1.1 , to sampling a random submatrix

\tilde{A}

and computing its SVD (actually, only left singular vectors are needed). The algorithm works well if the “average sparsity”

r = ∥ A ∥^{2} / ∥ A ∥_{F}^{2}

is small. This is the case, in particular, when

A

is essentially a low-rank matrix, because

r \leq r a n k (A)

First, the algorithm samples

d = O (r log r)

random rows of

A

. Namely, it should take

d

independent samples of the random variable

X

whose law is

P (X = \frac{A_{j}}{∥ A_{j} ∥}) = \frac{∥ A_{j} ∥^{2}}{{∥ A ∥}_{F}^{2}}

where

A_{j}

is the

j

-th row of

A

, and

∥ \cdot ∥

is the Euclidean norm. This sampling can be done in one pass through

A

if the matrix is stored row-by-row, and in two passes if its entries are stored in arbitrary order ([10,Section5.1] .

Then the algorithm computes the SVD of the

d \times n

matrix

\tilde{A}

. This can be done in time

O (d n) +

the time needed to compute the SVD of a

d \times d

matrix. The latter can be done by one of the known methods. This takes significantly less time than computing SVD of the original

m \times n

matrix

A

. In particular, the running time of this algorithm is linear in the dimensions of the matrix (and polynomial in

d

3 The cut norm and MAX-CSP problems

We will first prove Theorem 1.3 on the cut norm of random submatrices and then indicate how it, together with the argument of [3] , implies Theorem 1.2 on approximating MAX-2CSP with the sample complexity

O (ɛ^{- 2})

3.1 Decay of the cut-norm

The proof of Theorem 1.3 uses tools of Probability in Banach spaces: decoupling, symmetrization, and Slepian's Lemma (more precisely, its version for the Rademacher random variables due to M.Talagrand). It is easy to show that the cut norm of any operator

U : R^{n} \to R^{n}

is equivalent to

∥ U : ℓ_{\infty}^{n} \to ℓ_{1}^{n} ∥

, which we denote by

{∥ U ∥}_{\infty \to 1}

. We start with a decoupling lemma due to Bourgain and Tzafriri [7] .

Lemma 3.1. Let

(ξ_{i})

be a finite sequence of bounded i.i.d. random variables, and

(ξ_{i}^{'})

be its independent copy. Then for any sequence of vectors

(x_{i j})

in a Banach space with

x_{i i} = 0

E ∥ \sum_{i, j} ξ_{i} ξ_{j} x_{i j} ∥ \leq 20 E ∥ \sum_{i, j} ξ_{i} ξ_{j}^{'} x_{i j} ∥ .

Let

δ_{1} \dots δ_{n}

be independent Bernoulli random variables taking value 1 with probability

δ : = q / n

. For

Δ = (δ_{1} \dots δ_{n})

denote by

P_{Δ}

the coordinate projection on the random set of coordinates

{j | δ_{j} = 1}

Let

D (A)

be the diagonal part of

A

. Write

P_{Δ} A P_{Δ} = P_{δ} (A - D (A)) P_{Δ} + P_{Δ} D (A) P_{Δ} = \sum_{i \neq j} δ_{i} δ_{j} A_{i j} e_{i} \otimes e_{j} + \sum_{i} δ_{i} A_{i i} e_{i} \otimes e_{i} .

We apply the Lemma 3.1 to estimate the first summand, taking

x_{i j} = A_{i j} e_{i} \otimes e_{j}

i \neq j

and

x_{i j} = 0

i = j

. Then by the triangle inequality

E ∥ P_{Δ} A P_{Δ} ∥_{\infty \to 1} \leq 20 E ∥ P_{Δ} (A - D (A)) P_{Δ^{'}} ∥_{\infty \to 1} + δ \sum_{i} | A_{i i} |,

where

Δ^{'} = (δ_{i}^{'})

is an independent copy of the sequence

(δ_{i})

. Then to complete the proof it is enough to assume that the diagonal of

A

is zero and prove the inequality in the stated in the theorem for

E ∥ P_{Δ} A P_{Δ^{'}} ∥_{\infty \to 1}

Denoting the unit ball of

l_{\infty}^{n}

B_{\infty}^{n}

, we write

\begin{matrix} E ∥ P_{Δ} A P_{Δ^{'}} ∥_{\infty \to 1} & = E {sup}_{x \in B_{\infty}^{n}} \sum_{i} δ_{i} | 〈 A P_{Δ^{'}} x, e_{i} 〉 | \end{matrix}

\begin{matrix} = E {sup}_{x \in B_{\infty}^{n}} \sum_{i} (δ_{i} - δ) | 〈 A P_{Δ^{'}} x, e_{i} 〉 | + δ \cdot E ∥ A P_{Δ^{'}} ∥_{\infty \to 1} \end{matrix}

\begin{matrix}  \end{matrix}

Since

δ_{i} - δ

are mean zero, one can replace

δ

δ_{i}^{''}

, an independent copy of

δ_{i}

. More precisely, the first term does not exceed

E {sup}_{x \in B_{\infty}^{n}} \sum_{i} (δ_{i} - δ^{''}) | 〈 A P_{Δ^{'}} x, e_{i} 〉 |

The random variable

δ_{i} - δ_{i}^{''}

is symmetric, hence it is distributed identically with

ɛ_{i} (δ_{i} - δ_{i}^{''})

, where

ɛ_{i}

are Rademacher random variables independent of everything else (i.e.

- 1, 1

valued symmetric r.v.'s). Therefore the expression above is bounded by

2 E {sup}_{x \in B_{\infty}^{n}} \sum_{i} ɛ_{i} δ_{i} | 〈 A P_{Δ^{'}} x, e_{i} 〉 | .

To estimate it, we use Slepian's inequality for Rademacher random variables, proved by Talagrand (see [19] ). This estimate, which allows to remove the absolue values, is known as Gine-Zinn argument. Namely, for any

y_{1}, \dots, y_{n} \in R^{n}

E {sup}_{x \in B_{\infty}^{n}} \sum_{i} ɛ_{i} | 〈 x, y_{i} 〉 | \leq E {sup}_{x \in B_{\infty}^{n}} \sum_{i} ɛ_{i} 〈 x, y_{i} 〉 = E ∥ \sum_{i} ɛ_{i} y_{i} ∥_{1} .

So,

\begin{matrix} E {sup}_{x \in B_{\infty}^{n}} \sum_{i} ɛ_{i} δ_{i} | 〈 A P_{Δ^{'}} x, e_{i} 〉 | & \leq E ∥ P_{Δ^{'}} A^{*} (\sum_{i} ɛ_{i} δ_{i} e_{i}) ∥_{1} \end{matrix}

\begin{matrix} = E \sum_{j} δ_{j}^{'} | 〈 A^{*} (\sum_{i} ɛ_{i} δ_{i} e_{i}), e_{j} 〉 | \end{matrix}

\begin{matrix} = δ \cdot E \sum_{j} | \sum_{i} ɛ_{i} δ_{i} A_{j i} | \end{matrix}

\begin{matrix} \leq δ \cdot E_{δ} {max}_{ɛ \in {- 1, 1}^{n}} \sum_{j} | \sum_{i} ɛ_{i} δ_{i} A_{j i} | \end{matrix}

\begin{matrix} = δ \cdot E ∥ P_{Δ} A ∥_{\infty \to 1} . \end{matrix}

\begin{matrix}  \end{matrix}

Hence we proved that

\begin{matrix} E ∥ P_{Δ} A P_{Δ^{'}} ∥_{\infty \to 1} \leq δ (E ∥ P_{Δ} A ∥_{\infty \to 1} + E ∥ A P_{Δ} ∥_{\infty \to 1}) . \end{matrix}

(7)

By essentially repeating the above argument, we obtain

\begin{matrix} E ∥ P_{Δ} A ∥_{\infty \to 1} & ≲ E ∥ A^{*} (\sum_{i} ɛ_{i} δ_{i} e_{i}) ∥_{1} + δ \cdot E ∥ A ∥_{\infty \to 1} \end{matrix}

\begin{matrix} = E \sum_{j} | \sum_{i} ɛ_{i} δ_{i} A_{j i} | + δ \cdot E ∥ A ∥_{\infty \to 1} \end{matrix}

\begin{matrix}  \end{matrix}

and interchanging the expectation and the sum, we then apply Cauchy-Schwartz inequality:

\begin{matrix} \leq 2 \sum_{j} E_{δ} {(\sum_{i} δ_{i} | A_{j i} |^{2})}^{1 / 2} + δ \cdot E ∥ A ∥_{\infty \to 1} \end{matrix}

\begin{matrix} \leq 2 \sum_{j} {(E_{δ} \sum_{i} δ_{i} | A_{j i} |^{2})}^{1 / 2} + δ \cdot E ∥ A ∥_{\infty \to 1} \end{matrix}

\begin{matrix} = 2 δ^{1 / 2} \sum_{j} {(\sum_{i} | A_{j i} |^{2})}^{1 / 2} + δ \cdot E ∥ A ∥_{\infty \to 1} . \end{matrix}

\begin{matrix}  \end{matrix}

Also,

E ∥ A P_{Δ} ∥_{\infty \to 1} = E ∥ P_{Δ} A^{*} ∥_{\infty \to 1} \leq 2 δ^{1 / 2} \sum_{j} {(\sum_{i} | A_{i j} |^{2})}^{1 / 2} + δ \cdot E ∥ A ∥_{\infty \to 1} .

Putting this into 7 , we complete the proof.

3.2 Approximation of MAX-2CSP

Let us briefly indicate how Theorem 1.2 on approximating MAX-2CSP reduces to Theorem 1.3 on the cut norm of random submatrices. This reduction was done by Alon, Fernandez de la Vega, Kannan and Karpinski [1, 3] .

For a

z \in {0, 1}^{2}

, one sets up the

n \times n

matrix

A = A^{(z)}

whose

(i, j)

-th entry is the number of functions that depend on

x_{i}

and

x_{j}

and that are made true by the truth assignment

x_{i} = z_{1}

x_{j} = z_{2}

. Then the solution

M a x (F)

can be computed as the maximum of the polynomial

P (x) = \sum_{i, j} A_{i j}^{(0, 0)} (1 - x_{i}) (1 - x_{j}) + A_{i j}^{(0, 1)} (1 - x_{i}) x_{j} + A_{i j}^{(1, 0)} x_{i} (1 - x_{j}) + A_{i j}^{(1, 1)} x_{i} x_{j}

over the Boolean cube

{0, 1}^{n}

. Similarly, the solution

M a x (F |_{Q})

to the induced problem is the maximum of the polynomial

P |_{Q}

determined by the submatrix

A |_{Q \times Q}

The problem is then to compare the maxima of the two polynomials,

P

and

P |_{Q}

This can be proved (although still non-trivially, see (34) in [3] ) in the case when

A^{(z)}

are “cut-matrices” (or their scalar multiples). A cut matrix is the indicator function of the cartesian product

I \times J

for some

I, J \subset {1, \dots, n}

. To pass from cut matrices to general matrices, one uses the algorithmic version of Szemeredi's Regularity Lemma [15] , which allows to approximate any matrix in the cut norm by a linear combination of a small number of cut matrices. It is easy to check that the maximum of

P (x)

is stable with respect to small variations of

A^{(z)}

in the cut norm. But it is a nontrivial question if small variations of

A^{(z)}

will result in small variations in the induced problem, that is of the random submatrix

A^{(z)} |_{Q \times Q}

. We thus have to show that the cut norm of a matrix decreases proportinally when one passes to its random submatrix. This is where Theorem 1.3 is used.

Specifically, for a matrix

A = A^{(z)}

, the algorithmic version of Szemeredi's Regularity Lemma [15] states that there exists at most

4 / ɛ^{2}

cut-matrices whose sum, denoted by

B

, satisfies

\begin{matrix} ∥ A - B ∥_{C} \leq ɛ n ∥ A ∥_{F}, ∥ A - B ∥_{F} \leq ∥ A ∥_{F}, ∥ A - B ∥_{\infty} \leq \frac{2}{ɛ n} ∥ A ∥_{F}, \end{matrix}

(8)

where

∥ \cdot ∥_{\infty}

denotes the maximal absolute value of the entries. Note that

\begin{matrix} ∥ A ∥_{F} \leq n ∥ A ∥_{\infty} \leq 2^{2^{2}} n \end{matrix}

(9)

because the number of different Boolean functions that can depend on two fixed variables is

2^{2^{2}}

. Thus the approximation is good in the cut norm,

∥ A - B ∥_{C} = O (ɛ n^{2})

To prove 4 , it remains to show that this error will decrease to

∥ (A - B) |_{Q \times Q} ∥_{C} = O (ɛ q^{2})

for the induced problem. This is done by using Theorem 1.3 (see remark below it) along with 8 and 9 :

\begin{matrix} E ∥ (A - B) |_{Q \times Q} ∥_{C} & \leq C {(\frac{q}{n})}^{2} ∥ A - B ∥_{C} + C (\frac{q}{n}) n ∥ A - B ∥_{\infty} + C \frac{q^{3 / 2}}{n} ∥ A - B ∥_{F} \end{matrix}

\begin{matrix} \leq C ɛ q^{2} + \frac{C}{ɛ} q + C q^{3 / 2} = O (ɛ q^{2}) if q \sim ɛ^{- 2} . \end{matrix}

\begin{matrix}  \end{matrix}

This establishes nice approximations of both the original and the induced problem, which leads to Theorem 1.2 as described in the previous paragraph.

4 The decay of the spectral norm

In this section we prove Theorem 1.5 .

By homogeneity we can assume that

∥ A ∥ = 1

. The matrix

A

with columns

x_{1} \dots x_{n}

can be written as

A = \sum_{j \leq n} e_{j} \otimes x_{j} .

We have to compute

E : = E ∥ A |_{Q} ∥ = E ‖ \sum_{j \leq n} δ_{j} e_{j} \otimes x_{j} ‖ = E {‖ \sum_{j \leq n} δ_{j} x_{j} \otimes x_{j} ‖}^{1 / 2},

where

δ_{j}

are

{0, 1}

-valued independent random variables with

E δ_{j} = δ = \frac{q}{n}

. This will be done by a usual symmetrization and applying Lemma 2.3 .

Now we pass to a detailed proof. The standard symmetrization procedure (see [19] Lemma 6.3) yields

\begin{matrix} E & \leq E {‖ \sum_{j \leq n} (δ_{j} - δ) x_{j} \otimes x_{j} ‖}^{1 / 2} + \sqrt{δ} {∥ A ∥}^{1 / 2} \end{matrix}

\begin{matrix} \leq 2 E_{δ} {(E_{ɛ} ‖ \sum_{j \leq n} ɛ_{j} δ_{j} x_{j} \otimes x_{j} ‖)}^{1 / 2} + \sqrt{δ} . \end{matrix}

\begin{matrix}  \end{matrix}

Denote

J (δ) = {j | δ_{j} = 1}

. We apply Lemma 2.3 to bound

E_{ɛ} ‖ \sum_{j \in J (δ)} ɛ_{j} x_{j} \otimes x_{j} ‖

By Remark 2.4 , we can assume

l

in this Lemma equal

n (δ) : = e + \sum_{j \leq n} δ_{j} .

Then using the Cauchy-Schwartz inequality we obtain

\begin{matrix} E \leq & E_{δ} {(C \sqrt{log n (δ)} \cdot {max}_{j \in J (δ)} ∥ x_{j} ∥ \cdot {‖ \sum_{j \in J (δ)} x_{j} \otimes x_{j} ‖}^{1 / 2})}^{1 / 2} + \sqrt{δ} \end{matrix}

\begin{matrix} \leq & C {(E_{δ} (log n (δ) \cdot {max}_{j = 1 \dots n} δ_{j} {∥ x_{j} ∥}^{2}))}^{1 / 2} {(E_{δ} {‖ \sum_{j = 1}^{n} δ_{j} x_{j} \otimes x_{j} ‖}^{1 / 2})}^{1 / 2} \end{matrix}

\begin{matrix} + \sqrt{δ} . \end{matrix}

(10)

\begin{matrix}  \end{matrix}

To estimate the fist term in the product we use the following

Lemma 4.1. Let

a_{1} \geq a_{2} \geq \dots \geq a_{n} \geq 0

and let

δ_{1} \dots δ_{n}

be independent Bernoulli random variables taking value

1

with probability

δ > 2 / n

. Then

\frac{δ}{4 e} \sqrt{log δ n} \cdot \sum_{j = 1}^{1 / δ} a_{j} \leq E (\sqrt{log n (δ)} \cdot {max}_{j = 1 \dots n} δ_{j} a_{j}) \leq 4 δ \sqrt{log δ n} \cdot \sum_{j = 1}^{1 / δ} a_{j} .

Proof. To prove the upper estimate note that

{max}_{j = 1 \dots n} δ_{j} a_{j} \leq \sum_{j = 1}^{1 / δ} δ_{j} a_{j} + a_{1 / δ} .

Hence,

\begin{matrix} E (\sqrt{log n (δ)} \cdot {max}_{j = 1 \dots n} δ_{j} a_{j}) \leq E (\sqrt{log n (δ)} \cdot \sum_{j = 1}^{1 / δ} δ_{j} a_{j}) + a_{1 / δ} \cdot E \sqrt{log n (δ)} . \end{matrix}

(11)

Jensen's inequality yields

E \sqrt{log n (δ)} \leq \sqrt{log (E \sum_{i = 1}^{n} δ_{i} + e)} \leq 2 \sqrt{log δ n} .

By the linearity of expectation, the first term equals

\sum_{j = 1}^{1 / δ} a_{j} E (δ_{j} \sqrt{log n (δ)}) \leq \sum_{j = 1}^{1 / δ} a_{j} E (δ_{j} \sqrt{log (\sum_{i \neq j} δ_{i} + 1 + e)})

Here we estimated

n (δ)

replacing

δ_{j}

by 1. Taking the expectation first with respect to

δ_{j}

and then with respect to the other

δ_{i}

, we obtain that the last expression is bounded by

δ \sum_{j = 1}^{1 / δ} a_{j} \cdot \sqrt{log (δ n + 1 + e)} \leq 2 δ \sum_{j = 1}^{1 / δ} a_{j} \cdot \sqrt{log δ n} .

Finally, substituting this bound into 11 , we obtain

E (\sqrt{log \sum_{i = 1}^{n} δ_{i}} \cdot {max}_{j = 1 \dots n} δ_{j} a_{j}) \leq (2 δ \sum_{j = 1}^{1 / δ} a_{j} + 2 a_{1 / δ}) \cdot \sqrt{log δ n} \leq 4 δ \sum_{j = 1}^{1 / δ} a_{j} \cdot \sqrt{log δ n} .

To prove the lower bound, we estimate the product in Lemma 4.1 from below to make the terms independent. We have

\begin{matrix} E (\sqrt{log n (δ)} \cdot {max}_{j = 1 \dots n} δ_{j} a_{j}) & \geq E (\sqrt{log (\sum_{i = 1 / δ + 1}^{n} δ_{i} + e)} \cdot {max}_{j = 1 \dots 1 / δ} δ_{j} a_{j}) \end{matrix}

\begin{matrix} = E \sqrt{log (\sum_{i = 1 / δ + 1}^{n} δ_{i} + e)} \cdot E {max}_{j = 1 \dots 1 / δ} δ_{j} a_{j} . \end{matrix}

(12)

\begin{matrix}  \end{matrix}

These terms will be estimated separately. Since

P (\sum_{i = 1 / δ + 1}^{n} δ_{i} \geq δ n / 2) \geq 1 / 2

E \sqrt{log (\sum_{i = 1 / δ + 1}^{n} δ_{i} + e)} \geq \frac{1}{2} \sqrt{log \frac{δ n}{2}} .

Let

1 \leq k \leq 1 / δ

. Denote by

A_{k}

the event

δ_{k} = 1, δ_{j} = 0

for

1 \leq j \leq 1 / δ, j \neq k

Then

P (A_{k}) = δ \cdot (1 - δ)^{1 / δ - 1} \geq δ / e .

Hence,

E {max}_{j = 1 \dots 1 / δ} δ_{j} a_{j} \geq \sum_{k = 1}^{1 / δ} a_{k} P (A_{k}) \geq \frac{δ}{e} \sum_{j = 1}^{1 / δ} a_{j} .

Substituting this estimate into 12 finishes the proof.

Now we can complete the proof of Theorem 1.5 . Combining Lemma 4.1 and 10 , we get

E \leq C \sqrt{δ} {log}^{1 / 4} δ n \cdot {∥ A ∥}_{(1 / δ)}^{1 / 2} \cdot E^{1 / 2} + \sqrt{δ} .

Recall that

δ = q / n

. It can be easily checked that

E \leq a E^{1 / 2} + b

implies

E \leq 4 a^{2} E + 2 b

Hence,

E \leq 4 C^{2} {log}^{1 / 2} q \cdot {∥ A ∥}_{(n / q)} + 2 \sqrt{q / n} .

This completes the proof.

References

N. Alon, W. de la Vega, R. Kannan, M. Karpinski, Random Sampling and approximation of MAX-CSPs, 34'th ACM STOC (2002)
Y. Azar, A. Fiat, A. Karlin, F. McSsherry, J. Saia, Spectral analysis of data, Proceedings of the 33rd ACM Symposium on THeory of Computing, 2001
N. Alon, W. de la Vega, R. Kannan, M. Karpinski, Random Sampling and approximation of MAX-CSPs, Journal of Computer and System Sciences 67 (2003), 212-243
M. W. Berry, S. T. Dumais, G. W. O'Brian, Using linear algebra for intelligent information retrieval, SIAM Review 37 (1995), 573–595
M. W. Berry, Z. Drmac, E. R. Jessup, Matrices, vector spaces and information retrieval, SIAM Review 41 (1999), 335–362
M. J. Berry, G. Linoff, Data mining techniques. John-Wiley, 1997
J. Bourgain and L. Tzafriri: Invertibility of “large” sumatricies with applications to the geometry of Banach spaces and harmonic analysis. Israel J. Math., 57 (1987) 137–223
P. G. Casazza, R. Vershynin, Kadison-Singer meets Bourgain-Tzafriri, submitted
S. T. Deerwester, S. T. Dumais, G. W. Furnas, T. K. Landauer, R. H. Harshman, Indexing by latent semantic analysis, Journal of the American Society for Information Science 41 (1990), 391–407
P. Drineas, A. Frieze, R. Kannan, S. Vempala, V. Vinay, Clustering in large graphs via Singular Value Decomposition, Journal of Machine Learning, to appear (2004)
P. Drineas, R. Kannan, Pass efficient algorithms for approximating large matrices, Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (Baltimore, MD, 2003), 223–232, ACM, New York, 2003
P. Drineas, R. Kannan, M. Mahoney, Fast Monte-Carlo Algorithms for Matrices II: Computing a low-rank approximation to a matrix, preprint
P. Drineas, M. Mahoney, R. Kannan, Fast Monte-Carlo Algorithms for Matrices III: Computing an Efficient Approximate Decomposition of a Matrix, preprint
W. Fernandez de la Vega, MAX-CUT has a randomized approximation scheme in dense graphs, Random Structures and Algorithms 8 (1996), 187–199
A. Frieze and R. Kannan, The Regularity Lemma and approximation schemes for dense problems, Proceedings of the 37th Annual IEEE Symposium on Foundations of Computing (1996), 12–20
A. Frieze, R. Kannan and S. Vempala, Fast Monte-Carlo Algorithms for finding low-rank approximations, Proceedings of the Foundations of Computer Science, 1998, pp. 378–390, journal version in Journal of the ACM 51 (2004), 1025-1041
O. Goldreich, S. Goldwasser, D. Ron, Property testing and its connection to learning and approximation, Proc. 37th IEEE FOCS 96, 339–348; journal version in Journal of the ACM 45 (1998), 653–750
B. Kashin, L. Tzafriri, Some remarks on the restrictions of operators to coordinate subspaces, unpublished notes
M. Ledoux and M. Talagrand, Probability in Banach spaces, Springer, 1991
A. A. Lunin, On operator norms of submatrices, Math. USSR Sbornik 27 (1975), 481–502
C. H. Papadimitriou, P. Raghavan, H. Tamaki, S. Vempala, Latent semantic indexing: A probabilistic analysis, Proceedings of the ACM symposium on principles of database systems, 1998
M. Rudelson, Random vectors in isotropipc position, J. Funct. Anal. 164 (1999), no. 1, 60–72.
M. Talagrand, Sections of smooth convex bodies via majorizing measures, Acta MAth. 175 (1995), 273–300
M. Talagrand, Majorizing measures: the generic chaining, Ann. Probab. 24 (1996), 1049–1103
R. Vershynin, John's decompositions: selecting a large part, Israel Journal of Mathematics 122 (2001), 253–277

Department of Mathematics, University of Missouri, Columbia, MO 65211, U.S.A. E-mail address : rudelson@math.missouri.edu Department of Mathematics, University of California, Davis, CA 95616, U.S.A. E-mail address : vershynin@math.ucdavis.edu

November 27, 2006

Mark Rudelson

Roman Vershynin