The DOI matches its Crossref record.
Efficient Volume Sampling for Row/Column Subset Selection
Abstract
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). This solves an open problem from the monograph on spectral algorithms by Kannan and Vempala (see Section 7.4 of [15], also implicit in [1], [5]). Our first algorithm for volume sampling k-subsets of rows from an m-by-n matrix runs in O(kmnωlog n) arithmetic operations (where ω is the exponent of matrix multiplication) and a second variant of it for (1 + ϵ)-approximate volume sampling runs in O(mn log m · k2/ϵ2+m logωm · k2ω+1/ϵ2ω· log(kϵ-1log 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 ∈ Rm×n, in O(kmnωlog n) arithmetic operations we can find k of its rows such that projecting onto their span gives a √k + 1-approximation to the matrix of rank fc closest to A under the Frobenius norm. This improves the O(k√log k)-approximation of Boutsidis, Drineas and Mahoney [1] and matches the lower bound shown in [5]. The method of conditional expectations gives a deterministic algorithm with the same complexity. The running time can be improved to O(mn log m · k2/e2+ m logωm·k2ω+1ϵ2ω-log(kϵ-1log m)) at the cost of losing an extra (1 + ϵ) in the approximation factor. 2) The same rows and projection as in the previous point give a √(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 √n, even for k = 1.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cited by
Halko, N., Martinsson, P. G., & Tropp, J. A. (2011) · SIAM Review · doi:10.1137/090771806 · Cited by 4,002
Determinantal Point Processes for Machine Learning
Kulesza, A. (2012) · now publishers, Inc. eBooks · doi:10.1561/9781601986290 · Cited by 493
Diversity in Big Data: A Review
Drosou, M., Jagadish, H. V., Pitoura, E., & Stoyanovich, J. (2017) · Big Data · doi:10.1089/big.2016.0054 · Cited by 140
Diversity and Inclusion Metrics in Subset Selection
Mitchell, M., Baker, D., Moorosi, N., Denton, R., Hutchinson, B., Hanna, A., Gebru, T., & Morgenstern, J. (2020) · Proceedings of the AAAI/ACM Conference on AI, Ethics, and Society · doi:10.1145/3375627.3375832 · Cited by 87
Metadata
- Authors
- Deshpande, A., & Rademacher, L.
- Venue
- 2010 IEEE 51st Annual Symposium on Foundations of Computer Science
- Publisher
- IEEE
- Published
- 2010-10
- Pages
- 329-338
- ISSN
- 0272-5428 (ISSN-L)
- OpenAlex
- W2089135543
- Cited by
- 181
- References
- 0
- FWCI
- 8.03
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Efficient Volume Sampling for Row/Column Subset Selection. https://app.cochat.ai/papers/10.1109/focs.2010.38
- The paper
- Deshpande, A., & Rademacher, L. (2010). Efficient Volume Sampling for Row/Column Subset Selection. 2010 IEEE 51st Annual Symposium on Foundations of Computer Science. https://doi.org/10.1109/focs.2010.38
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.