Heuristic Search for Approximating One Matrix in Terms of Another Matrix

Guihong Wan, Haim SchweitzerIJCAI 2021 · DOI

TL;DR

This paper introduces the first non-trivial optimal heuristic search algorithm for approximating a target matrix using a subset of columns from a dictionary matrix, a problem with broad applications. They also propose practical, faster suboptimal variants that provide provable bounds on their accuracy compared to the optimal solution, outperforming existing greedy methods.

What Problem Does This Paper Address?

The core problem is finding the best $k$ columns from a "dictionary" matrix $X$ to approximate a "target" matrix $Y$ using linear combinations. This is known as column subset selection and has applications in areas like signal processing and machine learning. While optimal algorithms exist for the simpler case where $Y$ has only one column, the general case where $Y$ has multiple columns ($N > 1$) has largely been tackled with greedy, suboptimal approaches. The challenge is that simply applying single-column methods independently doesn't guarantee optimality for the entire matrix $Y$. This paper aims to bridge this gap by developing both optimal and more accurate suboptimal algorithms for the general multi-column case.

Methods

The authors frame the problem as a graph search, inspired by classical A and Weighted A algorithms.

  • Optimal Variant: They propose a heuristic search algorithm where the heuristic function $f_i = l_i$ (a lower bound on the approximation error) guarantees finding the optimal subset of $k$ columns. However, this can be computationally expensive.
  • Suboptimal Variants:
    • Greedy Variant: Using the heuristic $f_i = u_i$ (an upper bound on the error) results in a fast, greedy algorithm.
  • Weighted Variant: Using a combination $f_i = l_i + \gamma u_i$ offers a trade-off between accuracy and speed. They provide theoretical bounds showing that the error of these weighted solutions is bounded by $\gamma$ plus the optimal error.
  • Efficient Heuristics: A key contribution is the development of efficient methods to compute these heuristic values. This involves initial dimensionality reduction and then specialized calculations for parent and child nodes in the search tree, leveraging eigendecompositions and rank-one updates.
  • Sub-optimality Bounds: For non-optimal variants, they provide a method to calculate a bound on how far the obtained solution's error is from the true optimal error, using information from the fringe list of the search.

Datasets

The paper evaluates their algorithms on several publicly available datasets. For the $N=1$ case, they compare against methods like Leaps, Forward, Backward, OMP, FoBa, and POSS. For the general $N>1$ case, they compare against SOMP, SSBR, SOLS, CM, and ISOLS. Specific datasets mentioned include "libras," "spectf," "duke breast cancer," "scm20d," "mediamill," and "oes97." They also use large datasets like "Day1" for runtime comparisons.

Key Insights and Ideas

  • Generalizing A* for Matrix Approximation: The paper successfully adapts the well-established A* search framework to the complex problem of selecting columns to approximate an entire matrix, not just a single vector.
  • Heuristic Design for Trade-offs: The clever use of lower ($l_i$) and upper ($u_i$) bounds on the approximation error as heuristic functions allows for a spectrum of algorithms, from guaranteed optimal but slow, to fast but potentially less accurate, with tunable parameters.
  • Provable Sub-optimality Bounds: A significant contribution is the ability to provide concrete, data-dependent bounds on the sub-optimality of their approximate solutions. This is crucial for understanding the practical performance of non-optimal algorithms.
  • Efficient Eigendecomposition for Heuristics: The paper presents an efficient computational pipeline for calculating heuristic values, making the search-based approach feasible for larger problems.

Key Results

  • The proposed optimal variant ($f=l$) is guaranteed to find the best selection of $k$ columns.
  • The suboptimal variants (especially the weighted ones, $f=l+\gamma u$) achieve accuracy comparable to or better than state-of-the-art greedy algorithms.
  • The weighted variants offer a tunable trade-off: increasing $\gamma$ leads to higher error but faster runtime.
  • The sub-optimality bounds provided are meaningful and, in some cases, indicate that the computed solution is very close to optimal, even for non-optimal heuristic choices.
  • Runtime comparisons on large datasets show that their approach, particularly with efficient heuristic calculations, can be significantly faster than other methods for big problems.

Limitations and Future Work

  • Computational Cost of Optimal Variant: The optimal variant ($f=l$) is noted to be slow and practical only for small $k$ or small dictionary matrices.
  • Data Dependency of Bounds: The paper acknowledges that the quality of the sub-optimality bounds can be data-dependent, sometimes providing little useful information.
  • Future Work: The authors suggest that their approach is a significant step towards solving this problem and that further research could explore more advanced heuristic functions or optimizations. They also highlight that their upper bound calculation might not have a direct parallel in general A* theory, suggesting potential avenues for theoretical exploration.

Summary updated

BibTeX
@inproceedings{wan2021heuristic,
  author = {Guihong Wan and Haim Schweitzer},
  title = {{Heuristic Search for Approximating One Matrix in Terms of Another Matrix}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.24963/ijcai.2021/221},
}
Figure