Proceedings

Heuristic Search for Approximating One Matrix in Terms of Another Matrix

Guihong Wan, Haim Schweitzer

Download BibTeX Cite

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence. Main Track. Pages 1600-1606.

https://doi.org/10.24963/ijcai.2021/221

Keywords

  • Machine Learning: Dimensionality Reduction
  • Heuristic Search and Game Playing: Heuristic Search
  • Data Mining: Feature Extraction, Selection and Dimensionality Reduction
  • Machine Learning: Learning Sparse Models

Abstract

We study the approximation of a target matrix in terms of several selected columns of another matrix, sometimes called "a dictionary".

This approximation problem arises in various domains, such as signal processing, computer vision, and machine learning.

An optimal column selection algorithm for the special case where the target matrix has only one column is known since the 1970's,

but most previously proposed column selection algorithms for the general case are greedy.

We propose the first nontrivial optimal algorithm for the general case, using a heuristic search setting similar to the classical A* algorithm.

We also propose practical sub-optimal algorithms in a setting similar to the classical Weighted A* algorithm.

Experimental results show that our sub-optimal algorithms compare favorably with the current state-of-the-art greedy algorithms.

They also provide bounds on how close their solutions are to the optimal solution.

Guihong Wan, and Haim Schweitzer. 2021. Heuristic Search for Approximating One Matrix in Terms of Another Matrix. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21. IJCAI, 1600–1606. https://doi.org/10.24963/ijcai.2021/221
Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards