Abstract
The Column Subset Selection Problem (CSSP) is a fundamental challenge in data science, requiring the selection of a representative subset of features to approximate a large matrix. While heuristic and randomized methods exist, they often lack optimality guarantees. This paper presents the first algorithm capable of finding globally optimal solutions for CSSP in moderate-sized matrices. By framing the problem as a graph search and utilizing the A* algorithm with a novel admissible spectral heuristic, the proposed method achieves optimal results orders of magnitude faster than exhaustive search. We demonstrate its effectiveness on various real-world datasets, showing that it can solve in minutes problems that would traditionally require millions of years.
Introduction
In high-dimensional data analysis, selecting a subset of $k$ columns from a matrix $Y \in \mathbb{R}^{m \times n}$ to minimize the approximation error is a critical task. This problem, known as the Column Subset Selection Problem (CSSP), is NP-hard. Traditional approaches rely on greedy heuristics or randomized algorithms which, while efficient, do not guarantee optimality. Consequently, researchers have lacked a way to measure how far these approximations are from the true mathematical optimum.
Methodology
The authors bridge numerical linear algebra and artificial intelligence by reformulating CSSP as a shortest-path problem in a directed acyclic graph.
Graph Search Formulation
Each node in the search graph represents a subset of columns. An edge exists from a subset of size $i$ to a subset of size $i+1$ if the latter contains all columns of the former plus one additional column. The goal is to find a path from the empty set to a subset of size $k$ that minimizes the Frobenius norm of the approximation error.
A* Search and the Spectral Heuristic
To navigate this massive search space, the authors employ the A algorithm. The efficiency of A depends on an admissible heuristic $h(n)$ that never overestimates the cost to reach the goal. The "secret sauce" of this work is a spectral heuristic: the error of a rank-$k$ approximation (calculated via Singular Value Decomposition) serves as a lower bound for the error of any subset of $k$ columns. Because this heuristic is admissible, A* is guaranteed to find the optimal solution.
Pruning and Computational Efficiency
To further constrain the search, the authors use the Deshpande-Rademacher bound to establish an upper bound on the optimal error. Branches with a lower bound exceeding this upper bound are pruned immediately. To maintain high performance, the algorithm utilizes rank-1 updates and specialized numerical routines to compute heuristics for child nodes rapidly based on their parent's data.
Experimental Results
The algorithm was evaluated on several UCI Machine Learning Repository datasets and large-scale text categorization data (techtc01).
Massive Speedups
The A search demonstrates extraordinary efficiency. For the techtc01 dataset, selecting 4 columns from nearly 30,000, an exhaustive search would take an estimated 30 million years. The A algorithm identifies the optimal solution in approximately one minute. As shown in the results table, the ratio of exhaustive search time to A* runtime reaches as high as $1.5 \times 10^{13}$ for large datasets.
Accuracy and Benchmarking
The A algorithm provides a "gold standard" for evaluating existing methods like the Two-Stage (TS) and GKS algorithms. In several cases, such as the Madelon dataset, standard heuristics produced errors significantly higher than the optimal value found by A. This highlights the value of an optimal solver for benchmarking and for applications where precision is paramount.
Conclusion
This work demonstrates that global optimality in CSSP is achievable for moderate $k$ and large $n$. While the combinatorial complexity still poses challenges as $k$ increases, the A* approach with spectral heuristics offers a powerful tool for exact feature selection and algorithm verification. Future work may involve extending these heuristics to other norms, such as the spectral or $L_1$ norms.
Summary updated