Solving Generalized Column Subset Selection With Heuristic Search

Authors

  • Swair Shah The University of Texas at Dallas
  • Baokun He The University of Texas at Dallas
  • Ke Xu The University of Texas at Dallas
  • Crystal Maung The University of Texas at Dallas
  • Haim Schweitzer The University of Texas at Dallas

DOI:

https://doi.org/10.1609/aaai.v32i1.12197

Keywords:

Heuristic Search, Column Subset Selection, PCA, A* Search

Abstract

We address the problem of approximating a matrix by the linear combination of a column sparse matrix and a low rank matrix. Two variants of a heuristic search algorithm are described. The first produces an optimal solution but may be slow, as these problems are believed to be NP-hard. The second is much faster, but only guarantees a suboptimal solution. The quality of the approximation and the optimality criterion can be specified in terms of unitarily invariant norms.

AAAI 2018 Proceedings Cover

Downloads

Published

2018-04-29

How to Cite

Shah, S., He, B., Xu, K., Maung, C., & Schweitzer, H. (2018). Solving Generalized Column Subset Selection With Heuristic Search. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1). https://doi.org/10.1609/aaai.v32i1.12197

Issue

Vol. 32 No. 1 (2018): Thirty-Second AAAI Conference on Artificial Intelligence

Section

Student Abstract Track