Solving Generalized Column Subset Selection with Heuristic Search

Swair Shah, Baokun He, Ke Xu, Crystal Maung, Haim Schweitzer

AAAI 2018 pp. 8153-8154

doi:10.1609/AAAI.V32I1.12197 /aaai/2018/shah2018aaai-solving/

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.

PDF AAAI Semantic Scholar

Cite

Text

Shah et al. "Solving Generalized Column Subset Selection with Heuristic Search." AAAI Conference on Artificial Intelligence, 2018. doi:10.1609/AAAI.V32I1.12197

Markdown

[Shah et al. "Solving Generalized Column Subset Selection with Heuristic Search." AAAI Conference on Artificial Intelligence, 2018.](https://mlanthology.org/aaai/2018/shah2018aaai-solving/) doi:10.1609/AAAI.V32I1.12197

BibTeX

@inproceedings{shah2018aaai-solving,
  title     = {{Solving Generalized Column Subset Selection with Heuristic Search}},
  author    = {Shah, Swair and He, Baokun and Xu, Ke and Maung, Crystal and Schweitzer, Haim},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2018},
  pages     = {8153-8154},
  doi       = {10.1609/AAAI.V32I1.12197},
  url       = {https://mlanthology.org/aaai/2018/shah2018aaai-solving/}
}