Efficient Volume Sampling for Row/Column Subset Selection

By Amit Deshpande, Luis Rademacher. 2010

215 citations recorded by the source corpus.

We give efficient algorithms for volume sampling, i.e., for picking $k$-subsets of the rows of any given matrix with probabilities proportional to the squared volumes of the simplices defined by them and the origin (or the squared volumes of the parallelepipeds defined by these subsets of rows). %In other words, we can efficiently sample $k$-subsets of $[m]$ with probabilities proportional to the corresponding $k$ by $k$ principal minors of any given $m$ by $m$ positive semi definite matrix. This solves an open problem from the monograph on spectral algorithms by Kannan and Vempala (see Section $7.4$ of \cite{KV}, also implicit in \cite{BDM, DRVW}). Our first algorithm for volume sampling $k$-subsets of rows from an $m$-by-$n$ matrix runs in $O(kmn^\omega \log n)$ arithmetic operations (where $\omega$ is the exponent of matrix multiplication) and a second variant of it for $(1+\eps)$-approximate volume sampling runs in $O(mn \log m \cdot k^{2}/\eps^{2} + m \log^{\omega} m \cdot k^{2\omega+1}/\eps^{2\omega} \cdot \log(k \eps^{-1} \log m))$ arithmetic operations, which is almost linear in the size of the input (i.e., the number of entries) for small $k$. Our efficient volume sampling algorithms imply the following results for low-rank matrix approximation: (1) Given $A \in \reals^{m \times n}$, in $O(kmn^{\omega} \log n)$ arithmetic operations we can find $k$ of its rows such that projecting onto their span gives a $\sqrt{k+1}$-approximation to the matrix of rank $k$ closest to $A$ under the Frobenius norm. This improves the $O(k \sqrt{\log k})$-approximation of Boutsidis, Drineas and Mahoney \cite{BDM} and matches the lower bound shown in \cite{DRVW}. The method of conditional expectations gives a \emph{deterministic} algorithm with the same complexity. The running time can be improved to $O(mn \log m \cdot k^{2}/\eps^{2} + m \log^{\omega} m \cdot k^{2\omega+1}/\eps^{2\omega} \cdot \log(k \eps^{-1} \log m))$ at the cost of losing an extra $(1+\eps)$ in the approximation factor. (2) The same rows and projection as in the previous point give a $\sqrt{(k+1)(n-k)}$-approximation to the matrix of rank $k$ closest to $A$ under the spectral norm. In this paper, we show an almost matching lower bound of $\sqrt{n}$, even for $k=1$.

Subfields: Computational Theory and Mathematics, Computer Networks and Communications, Statistics and Probability

How researchers see this paper

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

In Computational Theory and Mathematics

In Computer Networks and Communications

In Statistics and Probability

Citations in the corpus

Determinantal Point Processes for Machine Learning (2012, background): “Deshpande and Rademacher [2010] recently proposed a (1 − )-approximate algorithm for sampling that runs in time O(N 2 log N k 2 2 + N log ω N k 2ω+1 2ω log( k log N )) when L is already decomposed as a Gram matrix, L = B B.”
Memory Replay with Data Compression for Continual Learning (2022, positive): “(11), similar to Geometric Interpretation of standard DPPs above, the probability P kL ( Y = S ) is further deﬁned with volume sampling (Deshpande & Rademacher, 2010), i.e., , D mbq , M ∗ q and M cq . θ is ﬁxed in this stage.”
Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions (2009, background): “Very recently, Deshpande and Rademacher improved the running time of volume-based sampling methods [36].”
Optimal approximation for submodular and supermodular optimization with bounded curvature (2013, methodology): “The best known algorithm for the problem as stated is a ( k + 1)-approximation algorithm given by Deshpande and Rademacher [10].”
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.”
Diversity and Inclusion Metrics in Subset Selection (2020, background): “Geometric or distance-based measures of diversity have also been explored within the sciences, measuring the diversity of a dataset by the dataset’s volume [1, 8, 11, 17, 20, 22, 37], variance as in PCA [30], or other measures of spread.”
Diversity in Big Data: A Review (2017, unknown): “known as determinantal point processes, for which efficient sampling methods were developed in recent literature.(23,24) A recent approach has been proposed to combine volume-based diversity with so-called com-”