Research map / Learning theory and algorithms / Combinatorial and search optimization
Linear Time Approximation Algorithm for Column Subset Selection with Local Search
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes LSCSS, a linear-time local search algorithm for column subset selection with exactly k columns, using two-step mixed sampling and matched swap-pair analysis to get a 53(k+1)-approximation in O(ndk^4 log k) time.
Problem
Column subset selection (CSS) with exactly k columns minimizing the Frobenius residual error; prior exact-k approximation algorithms have super-linear running time or weak (k+1)! ratio, and local search for CSS lacked theoretical guarantees.
Approach
A two-step mixed sampling method (sample a candidate set of 10k columns by residual-error probability, then pick one uniformly) reduces swap-pair enumeration from O(dk) to k, enabling linear-time single-swap local search; a matched swap-pair analysis bounds the residual reduction per step to yield a provable approximation.
Key results
- Proves a 53(k+1)-approximation for exactly-k CSS in O(ndk^4 log k) time, improving on the (k+1)! linear-time adaptive sampling bound.
- LSCSS is at least 10 times faster than state-of-the-art algorithms across all large-scale datasets and finishes within 5 hours on all datasets.
- LSCSS achieves the best error ratios on almost all datasets, e.g., Epsilon k=100 error ratio 1.0554 vs. ILS 1.0674.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use LSCSS instead of ILS | CSS with exactly k selected columns · CMHS, k=5 | error ratio: 1.2494±0.0492 -> 1.1348±0.0202 | Helped |
| Use LSCSS instead of ILS | CSS with exactly k selected columns · FAds, k=5 | error ratio: 1.0660±0.0165 -> 1.0648±0.0194 | No clear effect |
| Use LSCSS instead of ILS | CSS with exactly k selected columns · ELD, k=5 | error ratio: 1.1626±0.0108 -> 1.1570±0.0347 | No clear effect |
| Use LSCSS instead of ILS | CSS with exactly k selected columns · TGas, k=5 | error ratio: 1.2641±0.0115 -> 1.1657±0.1101 | Helped |
| Use LSCSS instead of ILS | CSS with exactly k selected columns · Gas, k=5 | error ratio: 1.4692±0.0102 -> 1.4721±0.0765 | No clear effect |
| Use LSCSS instead of ILS | CSS with exactly k selected columns · YaleB, k=5 | error ratio: 1.4791±0.0473 -> 1.4253±0.0905 | Helped |
| Use LSCSS instead of ILS | CSS with exactly k selected columns · Mnist8m, k=5 | error ratio: 1.1239±0.0094 -> 1.1277±0.0494 | No clear effect |
| Use LSCSS instead of Greedy | CSS with exactly k selected columns · Epsilon, k=5 | error ratio: 1.0203 -> 1.0190±0.0105 | No clear effect |
| Use LSCSS instead of prior algorithms | CSS on the 8 large datasets · Large datasets | running time: at least 10 times faster | Helped |
Limitations
- Theoretical approximation factor (53(k+1)) is loose and the running time has a k^4 dependence.
- Analysis is for single-swap local search; multi-swap variants are left open.
- Random perturbation D added to make A full-rank is needed for the analysis.
Experimental setup
Datasets: CMHS FAds ELD Gas YaleB TGas Epsilon Mnist8m sonar BinaryAlpha dna arrhythmia
Benchmarks: 22 real-world matrix datasets (14 small, 8 large)
Metrics: error ratio ||A-SS^+A||_F^2/||A-A_k||_F^2 running time (seconds)
Baselines: TwoStage Greedy VolumeSampling ILS QR with column pivoting
Builds on: adaptive sampling (Deshpande and Vempala) ILS local search for CSS (Li et al.) leverage score sampling + QR (Boutsidis et al.) volume sampling (Deshpande and Rademacher)
Closest papers by meaning
- Improved guarantees and a multiple-descent curve for Column Subset Selection and the Nystrom method (NeurIPS 2020 · similarity 0.88)
- Greedy Column Subset Selection: New Bounds and Distributed Algorithms (ICML 2016 · similarity 0.88)
- Multi-View Unsupervised Column Subset Selection via Combinatorial Search (Student Abstract) (AAAI 2025 · similarity 0.87)
- Equivalence between Graph Spectral Clustering and Column Subset Selection (Student Abstract) (AAAI 2024 · similarity 0.86)
- On Socially Fair Low-Rank Approximation and Column Subset Selection (NeurIPS 2024 · similarity 0.85)
- Multinoulli Extension: A Lossless Yet Effective Probabilistic Framework for Subset Selection over Partition Constraints (ICML 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.