Introduction
Dimensionality reduction is a cornerstone of machine learning, typically approached through either feature selection (choosing a subset of original features) or feature extraction (creating new, transformed features like PCA). While feature selection offers interpretability, feature extraction often yields higher accuracy. Practitioners frequently attempt to combine these by applying them sequentially—for instance, selecting features and then performing PCA.
However, research presented at AAAI-19 demonstrates that such sequential application is fundamentally sub-optimal. There exists a "hidden" optimal combination of selected and extracted features that independent steps cannot reach. This paper introduces the Hybrid Low Rank (HLR) representation, which optimally bridges this gap by framing dimensionality reduction as a combinatorial search problem.
The Hybrid Low Rank (HLR) Problem
The HLR problem aims to find a set of $r_1$ selected columns and $r_2$ extracted vectors from a matrix $X$ to minimize the overall reconstruction error. The core challenge is the massive combinatorial search space: for a dataset with $n$ features, there are $\binom{n}{r_1}$ possible subsets to evaluate.
To navigate this space, the authors treat the problem as a search over a subsets graph. In this graph, each node represents a specific subset of selected features, and edges represent the addition of a new feature.
Heuristic Search Strategy
The authors implement an A*-style "best-first" search using three variants of a heuristic function $f'(n)$:
- Optimal HLR ($f$): A lower-bound heuristic that guarantees finding the globally optimal solution.
- Greedy HLR ($u$): An upper-bound heuristic providing a fast, "best-guess" solution.
- Suboptimal HLR ($f + \epsilon u$): A weighted combination that allows users to trade off computation speed for accuracy, with a provable bound on the solution's distance from the optimum.
A key theoretical contribution is the "Sandwich" Property: the true optimal error is always bounded between the optimistic ($f$) and greedy ($u$) heuristics. This property allows the algorithm to effectively prune the search space, expanding only the most promising nodes.
Experimental Results and Efficiency
The HLR algorithm was evaluated on standard UCI datasets (e.g., vehicle, spectf) and high-dimensional text data (TechTC01).
Performance and Scalability
On the vehicle dataset, the heuristic search proved significantly more efficient than an exhaustive search. As shown in the performance plots, the time required for an exhaustive search grows exponentially with $r_1$, while the heuristic approach remains computationally tractable. Furthermore, the $f + u$ variant (greedy/suboptimal) provides massive speedups over the optimal $f$ heuristic while maintaining near-optimal accuracy.
On the high-dimensional TechTC01 dataset (over 29,000 features), where exhaustive search is impossible ($10^{288}$ combinations), the Greedy HLR provided solutions within 0.1% of the optimum. This demonstrates that the heuristics remain powerful even in extremely large search spaces.
Versatility and Interpretability
Unlike many existing methods limited to the Frobenius norm, this search framework is compatible with any unitarily invariant norm, including Spectral and Nuclear norms. This versatility, combined with the ability to explicitly balance $r_1$ interpretable features with $r_2$ extracted features, makes HLR a flexible tool for real-world data science.
Conclusion
By treating dimensionality reduction as a unified combinatorial problem, the HLR algorithm achieves superior reconstruction accuracy compared to traditional sequential methods. While computational complexity remains a challenge for non-unitarily invariant norms and memory-intensive fringe lists, the framework's provable optimality and error bounds mark a significant advancement in the field. Future work may extend these combinatorial techniques to other matrix factorization problems like Robust PCA.
Summary updated