Lemma 3.1.
Let
$\left({\xi}_{i}\right)$
be a finite sequence of bounded i.i.d. random variables, and
$\left({\xi}_{i}^{\prime}\right)$
be its independent copy. Then for any sequence of vectors
$\left({x}_{ij}\right)$
in a Banach space with
${x}_{ii}=0$
,
$$\mathbb{E}\parallel {\sum}_{i,j}{\xi}_{i}{\xi}_{j}{x}_{ij}\parallel \le 20\mathbb{E}\parallel {\sum}_{i,j}{\xi}_{i}{\xi}_{j}^{\prime}{x}_{ij}\parallel .$$
Let
${\delta}_{1}\dots {\delta}_{n}$
be independent Bernoulli random variables taking value 1 with probability
$\delta :=q/n$
. For
$\Delta =({\delta}_{1}\dots {\delta}_{n})$
denote by
${P}_{\Delta}$
the coordinate projection on the random set of coordinates
$\left\{j\right{\delta}_{j}=1\}$
.
Let
$D\left(A\right)$
be the diagonal part of
$A$
. Write
$${P}_{\Delta}A{P}_{\Delta}={P}_{\delta}(AD(A\left)\right){P}_{\Delta}+{P}_{\Delta}D\left(A\right){P}_{\Delta}={\sum}_{i\ne j}{\delta}_{i}{\delta}_{j}{A}_{ij}{e}_{i}\otimes {e}_{j}+{\sum}_{i}{\delta}_{i}{A}_{ii}{e}_{i}\otimes {e}_{i}.$$
We apply the Lemma 3.1 to estimate the first summand, taking
${x}_{ij}={A}_{ij}{e}_{i}\otimes {e}_{j}$
if
$i\ne j$
and
${x}_{ij}=0$
if
$i=j$
. Then by the triangle inequality
$$\mathbb{E}\parallel {P}_{\Delta}A{P}_{\Delta}{\parallel}_{\infty \to 1}\le 20\mathbb{E}\parallel {P}_{\Delta}(AD(A\left)\right){P}_{{\Delta}^{\prime}}{\parallel}_{\infty \to 1}+\delta {\sum}_{i}\left{A}_{ii}\right,$$
where
${\Delta}^{\prime}=\left({\delta}_{i}^{\prime}\right)$
is an independent copy of the sequence
$\left({\delta}_{i}\right)$
. 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
$\mathbb{E}\parallel {P}_{\Delta}A{P}_{{\Delta}^{\prime}}{\parallel}_{\infty \to 1}$
.
Denoting the unit ball of
${l}_{\infty}^{n}$
by
${B}_{\infty}^{n}$
, we write
$$\begin{array}{cc}\mathbb{E}\parallel {P}_{\Delta}A{P}_{{\Delta}^{\prime}}{\parallel}_{\infty \to 1}& =\mathbb{E}{sup}_{x\in {B}_{\infty}^{n}}{\sum}_{i}{\delta}_{i}\langle A{P}_{{\Delta}^{\prime}}x,{e}_{i}\rangle \end{array}$$  
$$\begin{array}{cc}& =\mathbb{E}{sup}_{x\in {B}_{\infty}^{n}}{\sum}_{i}({\delta}_{i}\delta )\langle A{P}_{{\Delta}^{\prime}}x,{e}_{i}\rangle +\delta \cdot \mathbb{E}\parallel A{P}_{{\Delta}^{\prime}}{\parallel}_{\infty \to 1}\end{array}$$  
$$\begin{array}{}\end{array}$$  
Since
${\delta}_{i}\delta $
are mean zero, one can replace
$\delta $
by
${\delta}_{i}^{\prime \prime}$
, an independent copy of
${\delta}_{i}$
. More precisely, the first term does not exceed
$$\mathbb{E}{sup}_{x\in {B}_{\infty}^{n}}{\sum}_{i}({\delta}_{i}{\delta}^{\prime \prime})\langle A{P}_{{\Delta}^{\prime}}x,{e}_{i}\rangle $$
The random variable
${\delta}_{i}{\delta}_{i}^{\prime \prime}$
is symmetric, hence it is distributed identically with
${\varepsilon}_{i}({\delta}_{i}{\delta}_{i}^{\prime \prime})$
, where
${\varepsilon}_{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\mathbb{E}{sup}_{x\in {B}_{\infty}^{n}}{\sum}_{i}{\varepsilon}_{i}{\delta}_{i}\langle A{P}_{{\Delta}^{\prime}}x,{e}_{i}\rangle .$$
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 GineZinn argument. Namely, for any
${y}_{1},\dots ,{y}_{n}\in {\mathbb{R}}^{n}$
,
$$\mathbb{E}{sup}_{x\in {B}_{\infty}^{n}}{\sum}_{i}{\varepsilon}_{i}\langle x,{y}_{i}\rangle \le \mathbb{E}{sup}_{x\in {B}_{\infty}^{n}}{\sum}_{i}{\varepsilon}_{i}\langle x,{y}_{i}\rangle =\mathbb{E}\parallel {\sum}_{i}{\varepsilon}_{i}{y}_{i}{\parallel}_{1}.$$
So,
$$\begin{array}{cc}\mathbb{E}{sup}_{x\in {B}_{\infty}^{n}}{\sum}_{i}{\varepsilon}_{i}{\delta}_{i}\langle A{P}_{{\Delta}^{\prime}}x,{e}_{i}\rangle & \le \mathbb{E}\parallel {P}_{{\Delta}^{\prime}}{A}^{*}\left({\sum}_{i}{\varepsilon}_{i}{\delta}_{i}{e}_{i}\right){\parallel}_{1}\end{array}$$  
$$\begin{array}{cc}& =\mathbb{E}{\sum}_{j}{\delta}_{j}^{\prime}\langle {A}^{*}({\sum}_{i}{\varepsilon}_{i}{\delta}_{i}{e}_{i}),{e}_{j}\rangle \end{array}$$  
$$\begin{array}{cc}& =\delta \cdot \mathbb{E}{\sum}_{j}\left{\sum}_{i}{\varepsilon}_{i}{\delta}_{i}{A}_{ji}\right\end{array}$$  
$$\begin{array}{cc}& \le \delta \cdot {\mathbb{E}}_{\delta}{max}_{\varepsilon \in \{1,1{\}}^{n}}{\sum}_{j}\left{\sum}_{i}{\varepsilon}_{i}{\delta}_{i}{A}_{ji}\right\end{array}$$  
$$\begin{array}{cc}& =\delta \cdot \mathbb{E}\parallel {P}_{\Delta}A{\parallel}_{\infty \to 1}.\end{array}$$  
$$\begin{array}{}\end{array}$$  
Hence we proved that
$$\begin{array}{c}\mathbb{E}\parallel {P}_{\Delta}A{P}_{{\Delta}^{\prime}}{\parallel}_{\infty \to 1}\le \delta \left(\mathbb{E}\parallel {P}_{\Delta}A{\parallel}_{\infty \to 1}+\mathbb{E}\parallel A{P}_{\Delta}{\parallel}_{\infty \to 1}\right).\end{array}$$ 
(7)

By essentially repeating the above argument, we obtain
$$\begin{array}{cc}\mathbb{E}\parallel {P}_{\Delta}A{\parallel}_{\infty \to 1}& \lesssim \mathbb{E}\parallel {A}^{*}\left({\sum}_{i}{\varepsilon}_{i}{\delta}_{i}{e}_{i}\right){\parallel}_{1}+\delta \cdot \mathbb{E}\parallel A{\parallel}_{\infty \to 1}\end{array}$$  
$$\begin{array}{cc}& =\mathbb{E}{\sum}_{j}\left{\sum}_{i}{\varepsilon}_{i}{\delta}_{i}{A}_{ji}\right+\delta \cdot \mathbb{E}\parallel A{\parallel}_{\infty \to 1}\end{array}$$  
$$\begin{array}{}\end{array}$$  
and interchanging the expectation and the sum, we then apply CauchySchwartz inequality:
$$\begin{array}{cc}& \le 2{\sum}_{j}{\mathbb{E}}_{\delta}{\left({\sum}_{i}{\delta}_{i}{A}_{ji}{}^{2}\right)}^{1/2}+\delta \cdot \mathbb{E}\parallel A{\parallel}_{\infty \to 1}\end{array}$$  
$$\begin{array}{cc}& \le 2{\sum}_{j}{\left({\mathbb{E}}_{\delta}{\sum}_{i}{\delta}_{i}{A}_{ji}{}^{2}\right)}^{1/2}+\delta \cdot \mathbb{E}\parallel A{\parallel}_{\infty \to 1}\end{array}$$  
$$\begin{array}{cc}& =2{\delta}^{1/2}{\sum}_{j}{\left({\sum}_{i}{A}_{ji}{}^{2}\right)}^{1/2}+\delta \cdot \mathbb{E}\parallel A{\parallel}_{\infty \to 1}.\end{array}$$  
$$\begin{array}{}\end{array}$$  
Also,
$$\mathbb{E}\parallel A{P}_{\Delta}{\parallel}_{\infty \to 1}=\mathbb{E}\parallel {P}_{\Delta}{A}^{*}{\parallel}_{\infty \to 1}\le 2{\delta}^{1/2}{\sum}_{j}{\left({\sum}_{i}{A}_{ij}{}^{2}\right)}^{1/2}+\delta \cdot \mathbb{E}\parallel A{\parallel}_{\infty \to 1}.$$
Putting this into 7 , we complete the proof.
3.2 Approximation of MAX2CSP
Let us briefly indicate how Theorem 1.2 on approximating MAX2CSP 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}^{\left(z\right)}$
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
$Max\left(F\right)$
can be computed as the maximum of the polynomial
$$P\left(x\right)={\sum}_{i,j}{A}_{ij}^{(0,0)}(1{x}_{i})(1{x}_{j})+{A}_{ij}^{(0,1)}(1{x}_{i}){x}_{j}+{A}_{ij}^{(1,0)}{x}_{i}(1{x}_{j})+{A}_{ij}^{(1,1)}{x}_{i}{x}_{j}$$
over the Boolean cube
$\{0,1{\}}^{n}$
. Similarly, the solution
$Max\left(F{}_{Q}\right)$
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 nontrivially, see (34) in [
3]
) in the case when
${A}^{\left(z\right)}$
are “cutmatrices” (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\left(x\right)$
is stable with respect to small variations of
${A}^{\left(z\right)}$
in the cut norm. But it is a nontrivial question if small variations of
${A}^{\left(z\right)}$
will result in small variations in the induced problem, that is of the random submatrix
${A}^{\left(z\right)}{}_{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}^{\left(z\right)}$
, the algorithmic version of Szemeredi's Regularity Lemma [
15]
states that there exists at most
$4/{\varepsilon}^{2}$
cutmatrices whose sum, denoted by
$B$
, satisfies
$$\begin{array}{c}\parallel AB{\parallel}_{C}\le \varepsilon n\parallel A{\parallel}_{F},\parallel AB{\parallel}_{F}\le \parallel A{\parallel}_{F},\parallel AB{\parallel}_{\infty}\le \frac{2}{\varepsilon n}\parallel A{\parallel}_{F},\end{array}$$ 
(8)

where
$\parallel \cdot {\parallel}_{\infty}$
denotes the maximal absolute value of the entries. Note that
$$\begin{array}{c}\parallel A{\parallel}_{F}\le n\parallel A{\parallel}_{\infty}\le {2}^{{2}^{2}}n\end{array}$$ 
(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,
$\parallel AB{\parallel}_{C}=O\left(\varepsilon {n}^{2}\right)$
.
To prove
4 , it remains to show that this error will decrease to
$\parallel (AB){}_{Q\times Q}{\parallel}_{C}=O\left(\varepsilon {q}^{2}\right)$
for the induced problem. This is done by using Theorem 1.3 (see remark below it) along with 8 and 9 :
$$\begin{array}{cc}\mathbb{E}\parallel (AB){}_{Q\times Q}{\parallel}_{C}& \le C{\left(\frac{q}{n}\right)}^{2}\parallel AB{\parallel}_{C}+C\left(\frac{q}{n}\right)n\parallel AB{\parallel}_{\infty}+C\frac{{q}^{3/2}}{n}\parallel AB{\parallel}_{F}\end{array}$$  
$$\begin{array}{cc}& \le C\varepsilon {q}^{2}+\frac{C}{\varepsilon}q+C{q}^{3/2}=O\left(\varepsilon {q}^{2}\right)\text{if}q\sim {\varepsilon}^{2}\text{.}\end{array}$$  
$$\begin{array}{}\end{array}$$  
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
$\parallel A\parallel =1$
. The matrix
$A$
with columns
${x}_{1}\dots {x}_{n}$
can be written as
$$A={\sum}_{j\le n}{e}_{j}\otimes {x}_{j}.$$
We have to compute
$$E:=\mathbb{E}\parallel A{}_{Q}\parallel =\mathbb{E}\Vert {\sum}_{j\le n}{\delta}_{j}{e}_{j}\otimes {x}_{j}\Vert =\mathbb{E}{\Vert {\sum}_{j\le n}{\delta}_{j}{x}_{j}\otimes {x}_{j}\Vert}^{1/2},$$
where
${\delta}_{j}$
are
$\{0,1\}$
valued independent random variables with
$\mathbb{E}{\delta}_{j}=\delta =\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{array}{cc}E& \le \mathbb{E}{\Vert {\sum}_{j\le n}({\delta}_{j}\delta ){x}_{j}\otimes {x}_{j}\Vert}^{1/2}+\sqrt{\delta}{\parallel A\parallel}^{1/2}\end{array}$$  
$$\begin{array}{cc}& \le 2{\mathbb{E}}_{\delta}{\left({\mathbb{E}}_{\varepsilon}\Vert {\sum}_{j\le n}{\varepsilon}_{j}{\delta}_{j}{x}_{j}\otimes {x}_{j}\Vert \right)}^{1/2}+\sqrt{\delta}.\end{array}$$  
$$\begin{array}{}\end{array}$$  
Denote
$J\left(\delta \right)=\left\{j\right{\delta}_{j}=1\}$
. We apply Lemma 2.3 to bound
${\mathbb{E}}_{\varepsilon}\Vert {\sum}_{j\in J\left(\delta \right)}{\varepsilon}_{j}{x}_{j}\otimes {x}_{j}\Vert $
.
By Remark
2.4 , we can assume
$l$
in this Lemma equal
$$n\left(\delta \right):=e+{\sum}_{j\le n}{\delta}_{j}.$$
Then using the CauchySchwartz inequality we obtain
$$\begin{array}{cc}E\le & {\mathbb{E}}_{\delta}{\left(C\sqrt{logn\left(\delta \right)}\cdot {max}_{j\in J\left(\delta \right)}\parallel {x}_{j}\parallel \cdot {\Vert {\sum}_{j\in J\left(\delta \right)}{x}_{j}\otimes {x}_{j}\Vert}^{1/2}\right)}^{1/2}+\sqrt{\delta}\end{array}$$  
$$\begin{array}{cc}\le & C{\left({\mathbb{E}}_{\delta}\left(logn\left(\delta \right)\cdot {max}_{j=1\dots n}{\delta}_{j}{\parallel {x}_{j}\parallel}^{2}\right)\right)}^{1/2}{\left({\mathbb{E}}_{\delta}{\Vert {\sum}_{j=1}^{n}{\delta}_{j}{x}_{j}\otimes {x}_{j}\Vert}^{1/2}\right)}^{1/2}\end{array}$$  
$$\begin{array}{cc}& +\sqrt{\delta}.\end{array}$$ 
(10)

$$\begin{array}{}\end{array}$$  
To estimate the fist term in the product we use the following
Lemma 4.1.
Let
${a}_{1}\ge {a}_{2}\ge \dots \ge {a}_{n}\ge 0$
and let
${\delta}_{1}\dots {\delta}_{n}$
be independent Bernoulli random variables taking value
$1$
with probability
$\delta >2/n$
. Then
$$\frac{\delta}{4e}\sqrt{log\delta n}\cdot {\sum}_{j=1}^{1/\delta}{a}_{j}\le \mathbb{E}\left(\sqrt{logn\left(\delta \right)}\cdot {max}_{j=1\dots n}{\delta}_{j}{a}_{j}\right)\le 4\delta \sqrt{log\delta n}\cdot {\sum}_{j=1}^{1/\delta}{a}_{j}.$$

Proof.
To prove the upper estimate note that
$${max}_{j=1\dots n}{\delta}_{j}{a}_{j}\le {\sum}_{j=1}^{1/\delta}{\delta}_{j}{a}_{j}+{a}_{1/\delta}.$$
Hence,
$$\begin{array}{c}\mathbb{E}\left(\sqrt{logn\left(\delta \right)}\cdot {max}_{j=1\dots n}{\delta}_{j}{a}_{j}\right)\le \mathbb{E}\left(\sqrt{logn\left(\delta \right)}\cdot {\sum}_{j=1}^{1/\delta}{\delta}_{j}{a}_{j}\right)+{a}_{1/\delta}\cdot \mathbb{E}\sqrt{logn\left(\delta \right)}.\end{array}$$ 
(11)

Jensen's inequality yields
$$\mathbb{E}\sqrt{logn\left(\delta \right)}\le \sqrt{log(\mathbb{E}{\sum}_{i=1}^{n}{\delta}_{i}+e)}\le 2\sqrt{log\delta n}.$$
By the linearity of expectation, the first term equals
$${\sum}_{j=1}^{1/\delta}{a}_{j}\mathbb{E}\left({\delta}_{j}\sqrt{logn\left(\delta \right)}\right)\le {\sum}_{j=1}^{1/\delta}{a}_{j}\mathbb{E}\left({\delta}_{j}\sqrt{log({\sum}_{i\ne j}{\delta}_{i}+1+e)}\right)$$
Here we estimated
$n\left(\delta \right)$
replacing
${\delta}_{j}$
by 1. Taking the expectation first with respect to
${\delta}_{j}$
and then with respect to the other
${\delta}_{i}$
, we obtain that the last expression is bounded by
$$\delta {\sum}_{j=1}^{1/\delta}{a}_{j}\cdot \sqrt{log(\delta n+1+e)}\le 2\delta {\sum}_{j=1}^{1/\delta}{a}_{j}\cdot \sqrt{log\delta n}.$$
Finally, substituting this bound into 11 , we obtain
$$\mathbb{E}\left(\sqrt{log{\sum}_{i=1}^{n}{\delta}_{i}}\cdot {max}_{j=1\dots n}{\delta}_{j}{a}_{j}\right)\le \left(2\delta {\sum}_{j=1}^{1/\delta}{a}_{j}+2{a}_{1/\delta}\right)\cdot \sqrt{log\delta n}\le 4\delta {\sum}_{j=1}^{1/\delta}{a}_{j}\cdot \sqrt{log\delta n}.$$
To prove the lower bound, we estimate the product in Lemma 4.1 from below to make the terms independent. We have
$$\begin{array}{cc}\mathbb{E}\left(\sqrt{logn\left(\delta \right)}\cdot {max}_{j=1\dots n}{\delta}_{j}{a}_{j}\right)& \ge \mathbb{E}\left(\sqrt{log({\sum}_{i=1/\delta +1}^{n}{\delta}_{i}+e)}\cdot {max}_{j=1\dots 1/\delta}{\delta}_{j}{a}_{j}\right)\end{array}$$  
$$\begin{array}{cc}& =\mathbb{E}\sqrt{log({\sum}_{i=1/\delta +1}^{n}{\delta}_{i}+e)}\cdot \mathbb{E}{max}_{j=1\dots 1/\delta}{\delta}_{j}{a}_{j}.\end{array}$$ 
(12)

$$\begin{array}{}\end{array}$$  
These terms will be estimated separately. Since
$\mathbb{P}({\sum}_{i=1/\delta +1}^{n}{\delta}_{i}\ge \delta n/2)\ge 1/2$
,
$$\mathbb{E}\sqrt{log({\sum}_{i=1/\delta +1}^{n}{\delta}_{i}+e)}\ge \frac{1}{2}\sqrt{log\frac{\delta n}{2}}.$$
Let
$1\le k\le 1/\delta $
. Denote by
${A}_{k}$
the event
${\delta}_{k}=1,{\delta}_{j}=0$
for
$1\le j\le 1/\delta ,j\ne k$
.
Then
$$\mathbb{P}\left({A}_{k}\right)=\delta \cdot (1\delta {)}^{1/\delta 1}\ge \delta /e.$$
Hence,
$$\mathbb{E}{max}_{j=1\dots 1/\delta}{\delta}_{j}{a}_{j}\ge {\sum}_{k=1}^{1/\delta}{a}_{k}\mathbb{P}\left({A}_{k}\right)\ge \frac{\delta}{e}{\sum}_{j=1}^{1/\delta}{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\le C\sqrt{\delta}{log}^{1/4}\delta n\cdot {\parallel A\parallel}_{(1/\delta )}^{1/2}\cdot {E}^{1/2}+\sqrt{\delta}.$$
Recall that
$\delta =q/n$
. It can be easily checked that
$E\le a{E}^{1/2}+b$
implies
$E\le 4{a}^{2}E+2b$
.
Hence,
$$E\le 4{C}^{2}{log}^{1/2}q\cdot {\parallel A\parallel}_{(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 MAXCSPs, 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 MAXCSPs, Journal of Computer and System Sciences 67 (2003), 212243

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. JohnWiley, 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, KadisonSinger meets BourgainTzafriri, 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 ACMSIAM Symposium on Discrete Algorithms (Baltimore, MD, 2003), 223–232, ACM, New York, 2003

P. Drineas, R. Kannan, M. Mahoney, Fast MonteCarlo Algorithms for Matrices II: Computing a lowrank approximation to a matrix, preprint

P. Drineas, M. Mahoney, R. Kannan, Fast MonteCarlo Algorithms for Matrices III: Computing an Efficient Approximate Decomposition of a Matrix, preprint

W. Fernandez de la Vega, MAXCUT 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 MonteCarlo Algorithms for finding lowrank approximations, Proceedings of the Foundations of Computer Science, 1998, pp. 378–390, journal version in Journal of the ACM 51 (2004), 10251041

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. Email address : rudelson@math.missouri.edu Department of Mathematics, University of California, Davis, CA 95616, U.S.A. Email address : vershynin@math.ucdavis.edu