Student or educator? Sign up with your school email and get 6 months of Pro free.
Cited by 181

The DOI matches its Crossref record.

Efficient Volume Sampling for Row/Column Subset Selection

Deshpande, Amit, Rademacher, Luis·2010·2010 IEEE 51st Annual Symposium on Foundations of Computer Science

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.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1109/focs.2010.38

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.

A few free checks a day · papers already verified open instantly · results are public

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

See all 181

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.