Subset Selection Algorithms: Randomized vs. Deterministic
Open accessAbstract
Subset selection is a method for selecting a subset of columns from a real matrix, so that the subset represents the entire matrix well and is far from being rank deficient.We begin by extending a deterministic subset selection algorithm to matrices that have more columns than rows.Then we investigate a two-stage subset selection algorithm that utilizes a randomized stage to pick a smaller number of candidate columns, which are forwarded for to the deterministic stage for subset selection.We perform extensive numerical experiments to compare the accuracy of this algorithm with the best known deterministic algorithm.We also introduce an iterative algorithm that systematically determines the number of candidate columns picked in the randomized stage, and we provide a recommendation for a specific value.Motivated by our experimental results, we propose a new two stage deterministic algorithm for subset selection.In our numerical experiments, this new algorithm appears to be as accurate as the best deterministic algorithm, but it is faster, and it is also easier to implement than the randomized algorithm.
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
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.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The bounds of Theorem 2 tend to be loose on real-world datasets.
“Such a phenomenon is not a new observation, and much prior work has shown that the bounds tend to be loose on real-world datasets (Broadbent et al., 2010; Paschou et al., 2007; Jolliffe, 1972).”
From Compactor: Calibrated Query-Agnostic KV Cache Compression with Approximate Leverage Scores (2025) · cites this paper as Broadbent et al., 2010
Section 4.1 says the experiments used constructed test matrices, not real-world datasets. Sections 4.5 and 4.6 discuss theoretical bounds and a counterexample, but neither establishes that the bounds of the citing paper’s Theorem 2 tend to be loose on real-world data. Searches for that theorem and for loose bounds on real-world datasets found no passage addressing the claim. (LLM, conf=0.78)
Experimental — accuracy not yet measured
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
Golub, G. (2012) · doi:10.56021/9781421407944 · Cited by 34,505 · see citing works
Halko, N., Martinsson, P., & Tropp, J. A. (2011) · SIAM Review · doi:10.1137/090771806 · Cited by 4,038 · see citing works
Numerical methods for solving linear least squares problems
Golub, G. H. (1965) · Numerische Mathematik · doi:10.1007/bf01436075 · Cited by 852 · see citing works
Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
Gu, M., & Eisenstat, S. C. (1996) · SIAM Journal on Scientific Computing · doi:10.1137/0917055 · Cited by 700 · see citing works
Randomized algorithms for the low-rank approximation of matrices
Liberty, E., Woolfe, F., Martinsson, P.-G., Rokhlin, V., & Tygert, M. (2007) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0709640104 · Cited by 559 · see citing works
Linear least squares solutions by householder transformations
Businger, P. A., & Golub, G. H. (1965) · Numerische Mathematik · doi:10.1007/bf01436084 · Cited by 511 · see citing works
Fast monte-carlo algorithms for finding low-rank approximations
FRIEZE, A. M., Kannan, R., & Vempala, S. (2004) · Journal of the ACM · doi:10.1145/1039488.1039494 · Cited by 508 · see citing works
Relative-Error $CUR$ Matrix Decompositions
Drineas, P., Mahoney, M. W., & Muthukrishnan, S. (2008) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/07070471x · Cited by 469 · see citing works
An improved approximation algorithm for the column subset selection problem
Boutsidis, C., Mahoney, M. W., & Drineas, P. (2009) · doi:10.5555/1496770.1496875 · Cited by 297 · see citing works
Rank degeneracy and least squares problems
Golub, G. H., Klema, V. C., & Stewart, G. W. (1976) · Cited by 175 · see citing works
On the existence and computation of rank-revealing LU factorizations
Pan, C.-T. (2000) · Linear Algebra and its Applications · doi:10.1016/s0024-3795(00)00120-8 · Cited by 156 · see citing works
On Rank-Revealing Factorisations
Chandrasekaran, S., & Ipsen, I. C. F. (1994) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/s0895479891223781 · Cited by 150 · see citing works
Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate
Decompositions, M., Halko, N., Martinsson, P., & Tropp, J. A. (2011) · Cited by 30 · see citing works
Butler, J. M., Bishop, D. T., & Barrett, J. H. (2005) · BMC Genetics · doi:10.1186/1471-2156-6-s1-s72 · Cited by 12 · see citing works
Wilzeck, A., & Kaiser, T. (2008) · EURASIP Journal on Advances in Signal Processing · doi:10.1155/2008/716826 · Cited by 9 · see citing works
Flagged first, then by citations
3 of the 18 references couldn’t be matched to a known paper.
Research works printed but not linked: 2
- S. Chandrasekaran and I. C. F. Ipsen, On rank-revealing factorizations, SIAM J. Matrix Anal. Appl., 15 (1994), pp. 592-622.
- H. P. Hong and C.-T. Pan, The rank-revealing QR decomposition and SVD, Math. Comp., 58 (1992), pp. 213- 32.
Cited by
Sorted by citations
Randomized Algorithms for Matrices and Data
Mahoney, M. W. (2012) · Chapman & Hall/CRC data mining and knowledge discovery series · doi:10.1201/b11822-37 · Cited by 535 · see citing works
Randomized algorithms for matrices and dataPreprint
Mahoney, M. W. (2011) · arXiv (Cornell University) · doi:10.48550/arxiv.1104.5557 · Cited by 184 · see citing works
Faster Subset Selection for Matrices and Applications
Avron, H., & Boutsidis, C. (2013) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/120867287 · Cited by 81 · see citing works
Provable deterministic leverage score sampling
Papailiopoulos, D., Kyrillidis, A., & Boutsidis, C. (2014) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/2623330.2623698 · Cited by 65 · see citing works
Drmač, Z., & Saibaba, A. K. (2018) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/17m1129635 · Cited by 48 · see citing works
Effectively Subsampled Quadratures for Least Squares Polynomial Approximations
Seshadri, P., Narayan, A., & Mahadevan, S. (2017) · SIAM/ASA Journal on Uncertainty Quantification · doi:10.1137/16m1057668 · Cited by 43 · see citing works
Sensor Scheduling With Time, Energy, and Communication Constraints
Rusu, C., Thompson, J., & Robertson, N. M. (2017) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2017.2773429 · Cited by 39 · see citing works
Randomized Discrete Empirical Interpolation Method for Nonlinear Model Reduction
Saibaba, A. K. (2020) · SIAM Journal on Scientific Computing · doi:10.1137/19m1243270 · Cited by 38 · see citing works
HOID: Higher Order Interpolatory Decomposition for Tensors Based on Tucker Representation
Saibaba, A. K. (2016) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/15m1048628 · Cited by 36 · see citing works
Literature survey on low rank approximation of matrices
Kumar, N. K., & Schneider, J. (2016) · Linear and Multilinear Algebra · doi:10.1080/03081087.2016.1267104 · Cited by 195 · see citing works
Ebadi, S. E., Ones, V. G., & Ebroul Izquierdo, M. (2016) · Proceedings - International Conference on Image Processing · doi:10.1109/icip.2016.7533105 · Cited by 14 · see citing works
Ryser, M., Neuhauser, F. M., Hein, C., Hora, P., & Bambach, M. (2021) · The International Journal of Advanced Manufacturing Technology · doi:10.1007/s00170-021-07642-x · Cited by 12 · see citing works
A Training Set Subsampling Strategy for the Reduced Basis Method
Chellappa, S., Feng, L., & Benner, P. (2021) · Journal of Scientific Computing · doi:10.1007/s10915-021-01665-y · Cited by 11 · see citing works
Topics in matrix sampling algorithmsPreprint
Petros Drineas, B., & Boutsidis, C. (2011) · arXiv (Cornell University) · Cited by 10 · see citing works
Robust Spectral Inference for Joint Stochastic Matrix FactorizationPreprint
Lee, M., Bindel, D., & Mimno, D. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1611.00175 · Cited by 8 · see citing works
Efficient CUR decomposition for interpretable low-rank approximations and imaging applications
Abdelgawad, M. A. A., Cheung, R. C. C., & Yan, H. (2025) · Neurocomputing · doi:10.1016/j.neucom.2025.130401 · Cited by 4 · see citing works
Hierarchical Energy Efficient Hybrid Precoding for Configurable Sub-Connected MIMO Systems
Li, X., Huang, Y., Heng, W., & Wu, J. (2021) · IEEE Access · doi:10.1109/access.2021.3078434 · Cited by 4 · see citing works
Neuhauser, F. M., Struck, R., Mautz, H., Manopulo, N., & Hora, P. (2019) · Procedia Manufacturing · doi:10.1016/j.promfg.2018.12.051 · Cited by 3 · see citing works
Heuristic optimization methods for three matrix problems
Chang, C.-T. (2012) · DIAL (Catholic University of Leuven) · Cited by 3 · see citing works
Faster Subset Selection for Matrices and ApplicationsPreprint
Avron, H., & Boutsidis, C. (2011) · arXiv (Cornell University) · doi:10.48550/arxiv.1201.0127 · Cited by 3 · see citing works
Bayesian D-Optimal Experimental Designs via Column Subset Selection
Eswar, S., Rao, V., & Saibaba, A. K. (2026) · SIAM Journal on Scientific Computing · doi:10.1137/24m1649861 · Cited by 2 · see citing works
Aldeghlawi, M., & Vélez-Reyes, M. (2018) · IEEE Southwest Symposium on Image Analysis and Interpretation (SSIAI) · doi:10.1109/ssiai.2018.8470360 · Cited by 2 · see citing works
Alkhatib, M. Q., & Vélez-Reyes, M. (2020) · Proceedings - International Conference on Image Processing · doi:10.1109/icip40778.2020.9190710 · Cited by 2 · see citing works
Sensor Placements for Damage Localization with the SDLV Approach
Bernal, D. P., Ma, Q., Castro‐Triguero, R., & Gallego, R. (2014) · Conference proceedings of the Society for Experimental Mechanics · doi:10.1007/978-3-319-04729-4_30 · Cited by 2 · see citing works
Compactor: Calibrated Query-Agnostic KV Cache Compression with Approximate Leverage Scores
Chari, V., & Van Durme, B. (2025) · arXiv · doi:10.48550/arxiv.2507.08143 · Cited by 1 · see citing works
“Then, with probability 1 − δ , we have [5, 30, 21], even deterministically choosing rows corresponding to the top-k leverage scores provides a good spectral sparsification of K .”
Evaluation of Conceptual Sketches on Stylus-Based Devices
Kumar, A. V., & Priya, S. (2016) · Cited by 1 · see citing works
Selection of questions for VAAs and the VAA-based elections
Tangian, A. S. (2017) · Repository KITopen (Karlsruhe Institute of Technology) · doi:10.5445/ir/1000068508
Combining the third vote with traditional elections
Tangian, A. S. (2019) · Repository KITopen (Karlsruhe Institute of Technology) · doi:10.5445/ir/1000095488
Deshpande, A., & Pratap, R. (2023) · Algorithmica · doi:10.1007/s00453-023-01124-0
Compression properties for large Toeplitz-like matrices
Beckermann, B., Kreßner, D., & Wilber, H. (2025) · Numerical Algorithms · doi:10.1007/s11075-025-02185-8
Improved Error Bounds for the DEIM and Related Masked Projection Techniques
Tripathi, B. N., & Shekhawat, H. S. (2025) · IEEE Control Systems Letters · doi:10.1109/lcsys.2025.3623245
Testing Hypotheses of Covariate Effects on Topics of Discourse
Phelan, G., & Campbell, D. A. (2026) · Statistical Analysis and Data Mining The ASA Data Science Journal · doi:10.1002/sam.70066
- Authors
- Broadbent, M., Brown, M., & Penner, K.
- Affiliations
- Amherst College (US)
- University of California, Berkeley (US)
- University of Pittsburgh (US)
- Venue
- SIAM Undergraduate Research Online
- Published
- 2010
- Volume
- 3
- Pages
- 50-71
- ISSN
- 2327-7807 (ISSN-L)
- OpenAlex
- W2326096805
- Cited by
- 32
- References
- 18
- Citations by year
- 2026: 2 · 2025: 3 · 2023: 1 · 2021: 3 · 2020: 2 · 2019: 2 · 2018: 2 · 2017: 4 · 2016: 5 · 2014: 2 · 2013: 1 · 2012: 2
- FWCI
- 1.97
- Type
- journal article
- Language
- en
- Open access
- bronze
- doi.org
- Locations
- SIAM Undergraduate Research Online (publishedVersion)
- Funders
- National Science Foundation
- Yale University
- North Carolina State University
- Ipsen
- Topics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Matrix Theory and Algorithms
- Physical Sciences › Engineering › Computational Mechanics › Sparse and Compressive Sensing Techniques
- Physical Sciences › Mathematics › Statistics and Probability › Statistical Methods and Inference
- Keywords
- subset selection, column selection, randomized algorithms, deterministic algorithms, two-stage algorithm, rank deficiency, iterative methods, matrix approximation
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
