Research map / Learning theory and algorithms / Combinatorial and search optimization
Multi-View Unsupervised Column Subset Selection via Combinatorial Search (Student Abstract)
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 a combinatorial search algorithm (A*-like, with epsilon-weighted heuristic) for multi-view unsupervised column subset selection, with an optimal variant and bounded-suboptimal variants.
Problem
Multi-view unsupervised column subset selection: choose k common columns across multiple views that minimize weighted reconstruction error; the problem is NP-hard.
Approach
Extends the single-view combinatorial search for CSS to multiple views using a heuristic h = l_i + eps*u_i, where l_i uses top singular eigenvectors of residuals as a lower bound and u_i ignores future error reduction; eps=0 gives optimal search, eps=infinity gives greedy, and intermediate values give bounded suboptimal solutions.
Key results
- On EPFL stereo faces with k=4, the optimal variant (eps=0) achieved error 13614 versus 41955 for Random and 23421 for K-Medoids, and 68928 for SP.
- With k=8, eps=0 gave error 8736 versus 26250 for Random, 15792 for K-Medoids, and 15341 for SP.
- The optimal variant captured 3 subjects and 3 poses (average recall 0.75), while K-Medoids got 0.675 and SP got 0.675.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use combinatorial search with ϵ=0 instead of K-Medoids | MVCSS · EPFL stereo faces, k=4 | reconstruction error: 23421 -> 13614 | Helped |
| use combinatorial search with ϵ=0 instead of SP | MVCSS · EPFL stereo faces, k=4 | reconstruction error: 68928 -> 13614 | Helped |
| use combinatorial search with ϵ=0 instead of Random | MVCSS · EPFL stereo faces, k=4 | reconstruction error: 41955 -> 13614 | Helped |
| use combinatorial search with ϵ=0 instead of K-Medoids | MVCSS · EPFL stereo faces, k=8 | reconstruction error: 15792 -> 8736 | Helped |
| use combinatorial search with ϵ=0 instead of SP | MVCSS · EPFL stereo faces, k=8 | reconstruction error: 15341 -> 8736 | Helped |
| use combinatorial search with ϵ=0 instead of Random | MVCSS · EPFL stereo faces, k=8 | reconstruction error: 26250 -> 8736 | Helped |
| set ϵ from 0 to 0.1 (ablation) | combinatorial search MVCSS · EPFL stereo faces, k=4 | reconstruction error: 13614 -> 15065 | Hurt |
| set ϵ from 0 to 0.5 (ablation) | combinatorial search MVCSS · EPFL stereo faces, k=4 | reconstruction error: 13614 -> 15065 | Hurt |
| set ϵ from 0 to 0.1 (ablation) | combinatorial search MVCSS · EPFL stereo faces, k=8 | reconstruction error: 8736 -> 10717 | Hurt |
| set ϵ from 0 to 0.5 (ablation) | combinatorial search MVCSS · EPFL stereo faces, k=8 | reconstruction error: 8736 -> 12013 | Hurt |
Surprising findings
- The SP baseline achieved lower error than K-Medoids at k=8 but higher error at k=4 (68928 vs 23421).
Limitations
- Evaluation is limited to a single small dataset (EPFL stereo faces, 2 views) and few baselines.
- Authors note future work is needed to benchmark against additional competitors and explore dynamic weighting.
- Runtime comparisons are not reported.
Experimental setup
Datasets: EPFL stereo face dataset
Benchmarks: EPFL stereo face dataset
Metrics: reconstruction error e error bound b average recall
Baselines: K-Medoids SP (Joneidi et al. 2020) Random
Builds on: column subset selection search (He et al. 2019) A* search weighted A*
Closest papers by meaning
- Linear Time Approximation Algorithm for Column Subset Selection with Local Search (NeurIPS 2024 · similarity 0.87)
- On Socially Fair Low-Rank Approximation and Column Subset Selection (NeurIPS 2024 · similarity 0.84)
- Multinoulli Extension: A Lossless Yet Effective Probabilistic Framework for Subset Selection over Partition Constraints (ICML 2025 · similarity 0.84)
- Equivalence between Graph Spectral Clustering and Column Subset Selection (Student Abstract) (AAAI 2024 · similarity 0.84)
- Graph Clustering Methods Derived from Column Subset Selection (Student Abstract) (AAAI 2024 · similarity 0.84)
- Unsupervised Kernel-based Multi-view Feature Selection with Robust Self-representation and Binary Hashing (AAAI 2025 · similarity 0.83)
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.