Matrix approximation and projective clustering via volume sampling

By Amit Deshpande, Luis Rademacher, Santosh Srinivas Vempala, Grant J. Wang. ACM-SIAM Symposium on Discrete Algorithms, 2006

386 citations recorded by the source corpus.

Frieze et al. [17] proved that a small sample of rows of a given matrix A contains a low-rank approximation D that minimizes ||A - D||F to within small additive error, and the sampling can be done efficiently using just two passes over the matrix [12]. In this paper, we generalize this result in two ways. First, we prove that the additive error drops exponentially by iterating the sampling in an adaptive manner. Using this result, we give a pass-efficient algorithm for computing low-rank approximation with reduced additive error. Our second result is that using a natural distribution on subsets of rows (called volume sampling), there exists a subset of k rows whose span contains a factor (k + 1) relative approximation and a subset of k + k(k + 1)/ε rows whose span contains a 1+ε relative approximation. The existence of such a small certificate for multiplicative low-rank approximation leads to a PTAS for the following projective clustering problem: Given a set of points P in Rd, and integers k, j, find a set of j subspaces F<inf>1</inf>, . . ., F<inf>j</inf>, each of dimension at most k, that minimize Σ<inf>p∈P</inf>min<inf>i</inf> d(p, F<inf>i</inf>)2.

Subfields: Artificial Intelligence, Computational Mechanics, Computer Vision and Pattern Recognition

View Paper: https://www.semanticscholar.org/paper/0df92684396540f140094ec304871164dc385c9d

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Computer Vision and Pattern Recognition

Citations in the corpus

An improved approximation algorithm for the column subset selection problem (2008, background): “One of the most relevant results for this paper is a bound of [11], which states that there exist exactly k columns in any m × n matrix A such that”
Large-scale manifold learning (2008, background): “1Other sampling schemes have been suggested [ 10][7].”
Optimal principal component analysis in distributed and streaming models (2015, methodology): “In the third sampling stage, we use an adaptive sampling algorithm from [22].”
Low-Rank Approximation and Regression in Input Sparsity Time (2012, methodology): “Many of the latter algorithms were improved independently by Deshpande and Vempala [2006] and Sarl´os [2006], as well as in follow-up work [Drineas et al. 2011; Nguyen et al. 2009; Magen and Zouzias 2011].”
Relative-Error CUR Matrix Decompositions (2007, methodology): “…and an induction on k argument [53] and in the other case an argument which relies on estimating the volume of the simplex formed by each of the k -sized subsets of the columns [17]), they reported the existence of a set of O ( k 2 /ǫ 2 ) columns that provide relative-error CX matrix decomposition.”
Efficient Volume Sampling for Row/Column Subset Selection (2010, methodology): “Usual dimension reduction techniques such as principal component analysis (PCA) or random projection fail to do this as they typically output singular vectors or random vectors which are linear combinations of a large number of feature vectors.”
MACH: Fast Randomized Tensor Decompositions (2009, methodology): “This family of randomized algorithms are generalizations of fast low rank approximation methods [9, 28, 11], adapted appropriately to the multiway case.”
Turning big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering (2013, neutral): “For example, to process a very large data set on a cloud, a distributed system or parallel computer, we can simply assign a part of the data set to each processor, compute the reduced representation, collect it somewhere and do the analysis on the union of the reduced sets.”
High-Dimensional Menger-Type Curvatures - Part I: Geometric Multipoles and Multiscale Inequalities (2008, neutral): “AMS Subject Classification (2000): 49Q15, 42C99, 60D05”
Improved Approximation Algorithms for Large Matrices via Random Projections (2006, methodology): “Extending the work of [30, 35, 20] we show that if we formO(k/ ) random linear combinations from the rows of A ∈ Rm×n, then the best rank-k approximation within the row space generated by the random projection achieves relative-error (1 +”
Principal Component Analysis and Higher Correlations for Distributed Data (2013, methodology): “m. 1.4.) To prove this theorem, we have to achieve better communication eﬃciency for sparse matrices. In this case, we use a result of Boutsidis, Drineas and Mahoney [10] (improving on a line of work [19, 21, 20, 33, 11]) algorithm for row/column-row based relative error low-rank matrix approximatio”
A Randomized Algorithm for Principal Component Analysis (2008, neutral): “However, other algorithms, such as those of [1], [2], [3], [5], [7], [8], [10], [11], [12], [13], [14], [15], [16], [17], [18], [21], [22], [23], [24], [25], [27], [28], [30], [32], [33], [34], [35], and [37], also yield accuracies involving factors of at least √ m when the singular values σk+1, σk+”
Handbook of Big Data (2016, methodology): “The software will be available as an R-package, but the instructions below do not reﬂect this and get the reader going by sourcing the software from the ﬁrst author’s site.”
Sketching as a Tool for Numerical Linear Algebra (2014, background): “f Deshpande, Rademacher, Vempala, and Wang. It is actually more general in the sense that the matrix V in the statement of the theorem need not be a subset of columns of A. Theorem 56 (Theorem 2.1 of [35]) Given A ∈Rm×n and V ∈Rm×c1 (with c1 ≤n,m), deﬁne the residual B = A−VV†A ∈Rm×n. For i = 1,...,”
On selecting a maximum volume sub-matrix of a matrix and related problems (2009, neutral): “Along these lines, in [4], the authors introduce ‘volume sampling’ to find low-rank approximation to a matrix where one picks a subset of columns with probability proportional to their volume squared.”