Fast monte-carlo algorithms for finding low-rank approximations.
We consider the problem of approximating a given m  n matrix A by another matrix of specified rank k, which is smaller than m and n. The Singular Value Decomposition (SVD) can be used to find the "best" such approximation. However, it takes time polynomial in m, n which is prohibitive for some modern applications. In this article, we develop an algorithm that is qualitatively faster, provided we may sample the entries of the matrix in accordance with a natural probability distribution. In many applications, such sampling can be done efficiently. Our main result is a randomized algorithm to find the description of a matrix D* of rank at most k so that holds with probability at least 1   (where &verbar;&verbar;F is the Frobenius norm). The algorithm takes time polynomial in k,1/&epsi;, log(1/) only and is independent of m and n. In particular, this implies that in constant time, it can be determined if a given matrix of arbitrary size has a good low-rank approximation.
INTRODUCTION
Real-world data often has a large a number of attributes (features/dimensions). A
natural question is whether in fact it is generated by a small model, i.e., with a
much smaller number of parameters than the number of attributes. One way to
formalize this question is the problem of finding a low-rank approximation: given
an m - n matrix A, find a matrix D of rank at most k so that ||A - D|| F is
as small as possible (for any matrix M, the Frobenius norm, ||.|| F , is defined as
F
Alternatively, if we view the rows of A as points in R n , then
it is the problem of finding a k-dimensional linear subspace that minimizes the sum
of squared distances to the points. This problem arises in many contexts, partly
because some matrix algorithms are more e#cient for low-rank matrices. It is also
interesting to consider other norms, e.g., the 2-norm (see Section 6), but we will
mostly focus on the Frobenius norm.
The traditional Singular Value Decomposition (SVD) can be used to solve the
problem in time O(min{mn 2 , nm 2
}). For many applications motivated by information
retrieval and the web, this is too slow and one needs a linear or sublinear
algorithm. To speed up SVD-based low-rank approximation, [Papadimitriou et al.
2000] suggested random projection as a pre-processing step, i.e., project the rows
of A to an O(log n)-dimensional subspace and then find the SVD in that subspace.
This reduces the worst-case complexity to O(mn log n) for a small loss in approximation
quality. This is still too high.
How fast can the problem be solved? At first sight, it seems
that# mn) is a
lower bound - if A has only a single non-zero entry, one has to examine all its
entries to find a good approximation. But suppose we can sample the entries with
probability proportional to their magnitudes. Then a constant-sized sample would
su#ce in this case!
In this paper, we show that a rank k approximation can be found in time polynomial
in k and 1/# where # is an error parameter, provided we can sample the
entries of A from a natural probability distribution. The sampling assumptions
will be made explicit shortly and also discussed in the context of some applications.
Our main result is the following.
Theorem 1. Given an m-n matrix A, and k, #, there is a randomized algorithm
which finds the description of a matrix D # of rank at most k so that
D,rank(D)#k
F
F
holds with probability at least 1 - #. The algorithm takes time polynomial in
k, 1/#, log(1/#) only, independent of m,n. The most complex computational task
is to find the first k singular values of a randomly chosen s - s submatrix where
}). The matrix D # can be explicitly constructed from its
description in O(kmn) time.
As a consequence, in poly(k, 1
time, we can determine (with high probability) if
A has a rank k approximation with error at most #||A|| F . The error probability #
can be boosted by standard techniques and we will prove the theorem for a fixed
error probability.
The central idea of our approach is described as follows : We pick p rows of A
Fast Low-Rank Approximation - 3
independently at random, each according to a probability distribution satisfying
Assumption A1 (see Section 1.1). Suppose these rows form a p-m matrix S # . The
rows will be scaled to form a matrix S (step 1 of the Algorithm in section 4). It
will be relatively easy (Lemma 2) to show that S T S approximately equals A T A.
The intuition for this is that the (i, j)th entry of A T A is the dot product of the ith
and jth columns of A and indeed, since S has a random sample of rows of A, the
entry (S T S) i,j estimates this; the scaling is done to make this estimate unbiased.
Now from standard Linear Algebra, we can get the SVD of A from the spectral
decomposition (SD) of A T A 1 , and therefore approximately from the SD of S T S.
Repeating this, the SD of S T S can be read o# from the SVD of S which in turn
can be obtained from the SD of SS T . Since SS T is just a p-p matrix, the problem
is reduced to computing the SVD of a constant sized matrix! This still leaves the
computation of SS T . For this, we apply the sampling trick a second time - we
pick a sample of p columns of S, to form a p-p matrix W (step 2 of the algorithm),
then WW T approximates SS T . Now the SD of WW T is all that is needed for
which the SVD of W su#ces. This then is the central computational task of the
algorithm. We present the algorithm in Section 4. Besides Lemma 2, the key step
in the analysis is showing that we can go from approximate left singular vectors of
S to approximate right singular vectors with only a small loss.
A key insight of the paper, and the basis of the algorithm, is the existence of a
good low-rank approximation to A in the subspace spanned by a small sample of
its rows. We state this below formally. The constant c is defined in Assumption
A1.
Theorem 2. Let A be an m - n matrix and S be a sample of s rows of A
from a distribution satisfying Assumption 1. Let V be the vector space spanned by
S. Then with probability at least 9/10, there exist an orthonormal set of vectors
y (1) , y (2) , . y (k) in V such that
D,rank(D)#k
F
cs
F . (1)
It is useful to note that that A # k
is the "restriction" of the linear
transformation A to the subspace spanned by the y (j) , namely for any x in that
subspace,
x
and further, for x orthogonal to this subspace,
A
By elementary linear algebra, the matrix A # k
has its rows in the
span of the vectors y (1) , . , y (k) and therefore its rank is at most k. To describe this
1 The right singular vectors of A are precisely the eigenvectors of A T A
Alan Frieze et al.
approximation, D # , it su#ces to give the vectors y (1) , . , y (k) . In the algorithm,
these vectors are themselves computed by multiplying a submatrix of A with a
set of vectors in R p . Thus the matrix D # can be recovered from a set of k p-dimensional
vectors and a set of p numbers indicating a submatrix of A spanned
by the corresponding rows. It also follows that the first k singular values of A can
be computed to within a cumulative additive error of #||A|| F .
In Section 3, we give the proof of this existence theorem. The theorem directly
gives an O(mnk/#+poly(k/#)) algorithm and suggests an algorithm whose running
time is linear in m and a small polynomial in k and 1/#. Such an algorithm was
developed following this paper in [Drineas et al. 2004a]. This and other subsequent
developments are discussed in Section 6.
Throughout the paper, M (i) denotes the ith row of the matrix M (as a row
vector), M (j)
denotes the jth column (as a column vector) and M i,j is the entry
in the ith row and jth column. Also, for any positive integer r, [r] denotes the set
{1, 2, . , r}.
1.1 Sampling assumptions
We now describe our sampling assumptions in detail.
Assumption 1. We can sample the rows of A so that row i is chosen with probability
F
for some constant c # 1 (independent of m,n). Here |.| denotes Euclidean length.
The are known to us (if then we we don't need to know the P i ).
Assumption 2. From any row i we can sample entry j with probability Q j|i
satisfying
F
The Q j|i are known to us (again if need to know the values).
If the matrix A has a known sparsity structure, then we might be able to set up
the sampling with very little preprocessing. In particular, if the matrix A is dense,
i.e., if for all i, j,
F
for some constant c # , then we we can take
In general, for any matrix, by making one pass through the entire matrix, we
can set up data structures that let us sample the entries fast from then onwards -
time per sample - so as to satisfy Assumptions 1 and 2. During the pass, we
do several things. Suppose M is such that for all i, j
M.
Fast Low-Rank Approximation - 5
We create O(log M) bins; during the pass, we put into the lth bin all the entries
(i, j) such that 2 l-1
. We also keep track of the number of entries in
each bin. After this, we treat all entries in a bin as being of the same value. To
sample, we pick a bin with probability proportional to the total sum of squares in
that bin. Then we pick an entry uniformly from the set of entries in the bin. In
the pass, we also set up similar data structures for each row.
1.2 Applications
In this section we discuss our algorithm in the context of applications that rely
on low-rank approximation. We show that in several situations we can satisfy the
sampling assumptions of our algorithm and thus obtain the SVD approximation
more e#ciently. Applications that we do not discuss include face recognition and
picture compression.
1.2.1 Latent Semantic Indexing. This is a general technique for processing a
collection of "documents". We give a very cursory description of this broad area
here and discuss its relation to our main problem (see [Berry et al. 1995; Deerwester
et al. 1990; Dumais et al. 1988; Dumais 1991] for details and empirical results).
Suppose there are m documents and n "terms" which occur in the documents
(terms may be all the words that occur in the documents or key words that occur
in them). The model hypothesizes that there are a small number (k) of unknown
"topics" which the documents are about. A topic is modelled as a probability
distribution on the n terms, i.e., an n-vector of non-negative reals summing to
1. With this model on hand, it is shown (with additional assumptions) that the
subspace spanned by the k best topics is close to the span of the top k singular
vectors of the so-called "document-term" matrix [Papadimitriou et al. 2000]. The
latter is an m - n matrix A with A ij being the frequency of the jth term in the
ith document. Alternatively, one can define A ij as 0 or 1 depending upon whether
the jth term occurs in the ith document.
Here we argue that, in practice, the assumptions of our algorithm are satisfied
and it can be used in place of the full SVD algorithm. It is easy to see that if
we are allowed one pass through each document, we can set up data structures for
sampling (ideally, the creator of a document could supply a vector of squared term
frequencies). Otherwise, if no frequency is too large (this is not unreasonable since
words that occur too often, so-called "buzz words", are removed from the analysis),
all we need to precompute is the length (L
of each document. This
is typically available (as say "file and we pick a document with probability
proportional to its length. This is easily seen to satisfy Assumption 1, but without
the squares (i.e. we sample the ith entry with probability L i /
The assumption
with the squares is satisfied if all the frequencies are small. Assumption 2 is
similarly implemented - given a document, we pick a word uniformly at random
from it, i.e., Q
1.2.2 Web Search model. Kleinberg [Kleinberg 1999] proposed an algorithm for
the problem of finding the most "important" documents from the set of documents
returned by a web search that works by analyzing the
This matrix A has entries A ij equal to 1 or 0 depending upon whether the i'th
Alan Frieze et al.
document points to the j'th. The algorithm sets out to find two unit-length m-vectors
x, y such that x T Ay is maximized. This is of course the problem of finding
the singular vectors of A. When the keyword has multiple meanings, not only
the top, but some of the other singular vectors (with large singular values) are
interesting. So, it is of interest to find the largest k singular vectors for some small
k.
It is worthwhile to consider our assumptions in this case. For Assumption 1, it is
su#cient to sample the documents (roughly) according to the number of hypertext
links from them. For Assumption 2, it is su#cient to be able to follow a random
link from a document.
1.2.3 Low-Rank Approximations and the Regularity Lemma. The fundamental
Regularity Lemma of Szemer-edi's in graph theory [Szemeredi 1978] gives a partition
of the vertex set of any graph so that "most" pairs of parts are "nearly regular".
(We do not give details here.) This lemma has a host of applications (see [Koml-os
and Simonovits 1996]) in graph theory. The lemma was non-constructive in that it
only asserted the existence of the partition (but did not give an algorithm to find it.)
Alon, Duke, Lefmann, R-odl and Yuster were finally able to give an algorithm to find
such a partition in polynomial time [Alon et al. 1994]. In [Frieze and Kannan 1996;
Frieze and Kannan 1999a], low-rank approximations of the adjacency matrix of the
graph were related to regular partitions. Szemer-edi's Lemma and an algorithm
for constructing the partition were derived from this connection. While this is
not directly relevant to our results, we point it out here as one more case where
low-rank approximations are very useful. A more direct application of eigenvector
computation and Szemer-edi's partition is given in [Frieze and Kannan 1999b].
2. THE SINGULAR VALUE DECOMPOSITION
The matrix A can be expressed
r
and the u (t) form an orthonormal set of column
vectors as do the v (t) . Also u (t) T
and Av
This is called the singular value decomposition of A. Here r is the rank of A.
By a theorem of Eckart and Young [Golub and Van Loan 1989], the matrix D k
that minimizes ||A -D||F among all matrices D of rank k or less is given by
This implies that
F
and ||A -D k || 2
F
r
t .
We use this notation throughout the paper.
Fast Low-Rank Approximation - 7
3. A SMALL SAMPLE INDUCES A GOOD APPROXIMATION
The goal of this section is to prove Theorem 2, namely the subspace spanned by a
sample of rows chosen according to Assumption 1 contains an approximation to A
that is nearly the best possible. If, by chance, v (1) , . v (k) belong to this subspace,
we would be done, since then, # k
would provide the required approximation
to A. What we show is that the vectors w (t) (to be defined shortly) in the
subspace do approximate scaled versions of the respective v (t) .
Let S be a random sample of s rows chosen from a distribution that satisfies
Assumption 1. For we define the vector-valued random variable
A (i) .
Note that S is, in general, a multiset, i.e., rows of A might be picked multiple times.
The vectors w (t) are clearly in the subspace generated by S. We first compute the
expectation of w t . For this, we can view it as the average of s i.i.d. random
variables has the following distribution:
A (i) with probability P i , for
Then, taking expectations, 2
and so,
E(w
Further, since P i # c |A (i)
F
, we have (since |u (t)
E(|w (t)
|A (i)
s
F . (2)
If we had w (t) exactly equal to # t v (t) T
(instead of just in expectation), then
A
and this would be su#cient to prove the theorem. We wish to carry this out
approximately.
To this end, define -
y (2) , . , -
2 The expectation and variance of a vector valued random variable are taken separately for each
component.
Alan Frieze et al.
Let y (1) , y (2) , . , y (n) be an orthonormal basis of R n so that
where l is the dimension of V 1 . Let
l
Ay (t) y (t) T
and -
The matrix F will be our candidate approximation to A in the span of S. We will
bound its error using -
F. Note that for any i # k and j > l, we have -
Thus,
F
|Ay (i)
F)y (i)
F . (3)
Also,
F
-w (i)
Taking expectations and using (2) we get
E(||A -
F
F . (4)
F is of rank at most k and D k is the best rank k approximation to A. So, we have
F
Thus ||A -
F
is a non-negative random variable and (4) implies
From (3) it follows that
F
We next observe that a good low-rank approximation with respect to Frobenius
norm implies a good low-rank approximation with respect to the 2-norm,
Fast Low-Rank Approximation - 9
approximations have since been obtained for the 2-norm (see
Section 6).
Theorem 3. If
||A -A
F .
Then
||A -A
F .
Proof. Let
y (t) y (t) T . Suppose that B has a unit eigenvector x
with eigenvalue # such that
F .
Then we see that
F
F . (5)
The rank of the matrix A # k
Bxx T is at most k + 1, and so
||A -A
F
F ,
since # 2
F
. This contradicts (5). #
4. SAMPLING ALGORITHM
In this section we present the main constant-time algorithm to produce the approximation
of Theorem 1. What we do below is to first pick a set of p rows of A
from a distribution satisfying Assumption 1. We form a matrix S from these rows
after scaling them. We then pick p columns of S from a probability distribution
satisfying Assumption 2 and scale the columns to get a p - p matrix W. We find
the singular vectors of this matrix and from those, show how to get a good low-rank
approximation to A. The reader might want to consult the discussion between the
statements of Theorems 1 and 2 in the introduction for an intuitive idea of how
the algorithm works. In the description below, the parameter c is the one from the
assumptions.
Alan Frieze et al.
Algorithm
Input: Matrix A, integer k > 0 and error parameter # > 0. Set
(1) (Sample rows) Independently choose (rows) according to
distribution Assumption 1, i.e.,
F
Let S be the p - n matrix with rows A (i t
that if 1, the this scaling amounts to normalizing all rows to be of the
same length.
(2) (Sample columns) Independently choose (columns)
according to a distribution P
F
(we show below how to do this using Assumption 2.)
Let W be the p - p matrix with columns S (j t
(3) (Compute SVD) Compute the top k singular vectors u (1) , . , u (k) in
the column space of W.
where
8k .
For
|
Output v (t) for t # T (the low rank approximation to A is
A # t#T
We next discuss the implementation of the above algorithm. In particular, how
do we carry out Step 2? We first pick a row of S, each row with probability
1/p; suppose the chosen row is the ith row of A. Then pick j # {1, 2, . n} with
probabilities Q j|i as in Assumption 2. This defines the probabilities P #
. We then
have (with I (i) is a row of S}),
F
F
F
F
Fast Low-Rank Approximation - 11
where the last step is implied by the next lemma.
Lemma 1. For S and W chosen as in the algorithm, with probability at least
F
and 1
F .
Proof. By a routine calculation,
F
F
Next, observe that for any row i of S,
F
cp
The random variable ||S|| 2
F
is a sum of p independent random variables. Therefore,
F
F
F .
The first part of the lemma now follows using Chebychev's inequality. The proof
of the second part is similar. #
5. ANALYSIS
The next lemma asserts that a sample N of rows of a matrix M provides a good
approximation to M in the sense that N T N is close to M T M. This will be a key
tool in the analysis.
Lemma 2. Let M be an a- b matrix and let a be a probability
distribution on {1, 2, . , a} such that
F
for some 0 < # < 1. Let a sequence of p independent samples
from [a], each chosen according to distribution Q. Let N be the p - b matrix with
Then for all # > 0,
F
Alan Frieze et al.
Proof.
F
E(N T
a
E(|N T
a
F
a
F
a
Thus,
E(||M
F
E(|N T
F
a
F
a
F
The result follows from Markov's inequality. #
We introduce some notation for the rest of the analysis. For a matrix M and
vectors x (i) , i # I we define
x (i) x (i) T
F
When the x (i) are orthogonal unit vectors, this represents the norm of the projection
of M onto the subspace spanned by the x (i) . In this case,
Fast Low-Rank Approximation - 13
Thus, if x (t) , t # [k] are the top k singular vectors of A, then
t .
Lemma 3. Let A,S be matrices with the same number of columns, and
F .
(1 ) For any pair of unit vectors z, z # in the row space of A,
F .
set of unit vectors z (1) , z (2) , . , z (# k in the row space of A,
F .
Proof. The first part of the lemma is easy. For the second, using the fact that
F
matrix N, we see that #(A;x (i) , i # I) equals
Tr(Az (i) z (i) T
z (i) T
A T Az (i)
(|z (i)
A T Az (i)
z (i # ) T
A T Az (i)
z (i) T
A T Az (i)
z (i # ) T
A T Az (i) .
By exactly similar reasoning, we have
z (i) T
z (i # ) T
Now using the first part of the lemma, the second part follows. #
We are now ready to prove the main theorem.
Proof of Theorem 1. We will prove that the conclusion of the theorem holds
with probability at least 3/4. We will apply Lemma 2 twice, once to the row sample
and once to the induced column sample. It follows from the Lemma 2 that with
probability at least 9/10 both of the following events hold:
F
and ||SS T
F
where
cp
500k ,
c# 3/2
Assume from now on that these events occur. Throughout the proof, we will approximate
constants that arise somewhat crudely (by convenient rationals).
It follows from Theorem 2 that with probability at least 9/10 there are unit
vectors x (t) , t # [k] in the row space of S such that
Alan Frieze et al.
Applying the second part of Lemma 3 to A,S and the vectors x (i) , we see that
F
F
(using (7). Now, S and S T have the same singular values and so there exist unit
vectors y (t) , t # [k] in the column space of S such that
F .
Applying Theorem 2 to S T and W T , we see that with probability at least 9/10
there are unit vectors z (t) , t # [k] in the column space of W such that
F .
Applying the second part of Lemma 3 to S T , W T and the vectors z (t) , we see that
F .
Therefore, the vectors u (t) , t # [k] computed by the algorithm satisfy
F .
Note that the highest possible value of #(A;x (t) , t # [k]) is ||D k || 2
F
. All that
remains to show is that in fact #(W T , .) being large implies that #(A, .) is large.
For this, we construct a suitable set of vectors (as in the algorithm).
Since u (t) , t # [k] are orthonormal singular vectors,
F .
Applying Lemma 3 again, this time to S T , W T and the vectors u (t) , t # T , it follows
that
F .
The next and crucial step, is to switch from u (t) in the column space of S to v (t) in
the row space of S. This is achieved by the following claims whose proof we defer
to Section 5.1. For t # T ,
F
2. |v (t)
#It follows from Lemma 3 that
F
(assuming # 16). Thus,
F .
Rearranging terms, we get the conclusion of the theorem:
Fast Low-Rank Approximation - 15
5.1 Proof of Claims 1 and 2
Observe first that
F
F
F
and that for t #= t # T ,
Now consider t
(v (t) T
.
Furthermore,
| #||S|| 2
F . (10)
Similarly, using (8),
| #||S|| 2
Using the bounds (10) and (11) in (9),
F
F
F
F
F
using the bounds from Lemma 1. Next, for any vector u and any matrix S
|SS T u|
|u|
| 4
Observe that the first part of Lemma 3 implies
F .
. (12)
immediately. We then have
SS T u
Alan Frieze et al.
F ,
which completes the proof of Claim 1, since 9k 2 # 2 /# 2 < #/16. The value of p was
chosen to satisfy this and (12).
6. RECENT WORK
There have been several developments on the problem of low-rank approximation
since a preliminary version of this paper [Frieze et al. 1998] appeared. Drineas et
al. [Drineas et al. 2004a] give an algorithm whose running time is O(mr
Although this is theoretically much slower (due to the dependence
on m), in practice, the better dependence on k and 1/# might make it more
practical. An alternative sampling-based algorithm was given in [Achlioptas and
McSherry 2001] with comparable bounds for the Frobenius norm and significantly
better bounds for the 2-norm. There, the main idea is to sparsify the matrix by
randomly sampling its entries, one by one, and then compute the SVD of a sparse
matrix (which is faster). In [Bar-Yossef 2003], a lower bound for low-rank approximation
is given, which essentially matches the bound of [Drineas et al. 2004a]. It is
also shown there that an algorithm with this complexity is not possible using just
uniform sampling. In [Drineas et al. 2004a], (and the current paper), we only get
an implicitly defined low-rank approximation to A. A more explicit approximation
is given in [Drineas and Kannan 2003], which shows that if C is a m- s matrix of
s columns of A picked by sampling and R is a s - n matrix of s rows of A picked
at random, then we have A # CUR, where U is a s - s matrix computed from C.
This thus is a more explicit approximation preserving the sparsity structure of A.
The paper [Drineas and Kannan 2001] applied the sampling idea here to the basic
problem of multiplying two matrices A and B and showed that if we sample a few
columns of A (according to probability distributions similar to this paper) and take
the corresponding rows of B, their product approximates the whole product AB.
Finally, an improvement of our analysis, in terms of the number of rows that need
to be sampled has been obtained in [Drineas et al. 2004b].



--R

"Fast Computation of Low Rank Approximations"
"The algorithmic aspects of the Regularity Lemma,"
"Sampling Lower Bounds via Information Theory"
"Using linear algebra for intelligent information retrieval"
"Indexing by latent semantic analysis,"
"Fast Monte-Carlo Algorithms for approximate Matrix Multiplica- tion"
"Pass E#cient Algorithms for approximating large matrices"
"Clustering Large Graphs via the Singular Value Decomposition,"
"Fast Monte Carlo Algorithms for Matrices II: Computing Low-Rank Approximations to a Matrix,"
"Using latent semantic analysis to improve information retrieval,"
"Improving the retrieval of information from external sources"
"The Regularity Lemma and approximation schemes for dense prob- lems"
"Quick approximations to matrices and applications,"
"A simple algorithm for constructing Szemeredi's Regularity Parti- tion"
"Fast Monte-Carlo algorithms for finding low-rank ap- proximations"
Matrix Computations
"Authoritative sources in a hyperlinked environment,"
"Szemer-edi's Regularity Lemma and its applications in graph the- ory"
Latent Semantic Indexing: A Probabilistic Analysis
"Regular partitions of graphs,"

--TR

--CTR
Petros Drineas , Michael W. Mahoney , S. Muthukrishnan, Sampling algorithms for l2 regression and applications, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1127-1136, January 22-26, 2006, Miami, Florida
Sariel Har-Peled, How to get close to the median shape, Computational Geometry: Theory and Applications, v.36 n.1, p.39-51, January 2007
Sariel Har-Peled, How to get close to the median shape, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA
Dimitris Achlioptas , Frank Mcsherry, Fast computation of low-rank matrix approximations, Journal of the ACM (JACM), v.54 n.2, p.9-es, April 2007
W. Fernandez de la Vega , Marek Karpinski , Ravi Kannan , Santosh Vempala, Tensor decomposition and approximation schemes for constraint satisfaction problems, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
Amit Deshpande , Luis Rademacher , Santosh Vempala , Grant Wang, Matrix approximation and projective clustering via volume sampling, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1117-1126, January 22-26, 2006, Miami, Florida
matrix algorithms;sampling;low-rank approximation