On selecting a maximum volume sub-matrix of a matrix and related problems
Yazarlar (1)
Prof. Dr. Ali ÇİVRİL Beykoz Üniversitesi, Türkiye
| Makale Türü |
Özgün Makale
(SSCI, AHCI, SCI, SCI-Exp dergilerinde yayınlanan tam makale)
|
||
| Dergi Adı | Theoretical Computer Science (Q2) | ||
| Dergi ISSN | 0304-3975 Dergi Bilgileri (2009) | ||
| Dergi Tarandığı Indeksler | SCI | ||
| Makale Dili | İngilizce | Basım Tarihi | 01-2009 |
| Cilt / Sayı / Sayfa | 410 / 47 / 4801–4811 | DOI | 10.1016/j.tcs.2009.06.018 |
| Makale Linki | https://linkinghub.elsevier.com/retrieve/pii/S0304397509004101 | ||
| UAK Araştırma Alanları |
Algoritmalar ve Hesaplama Kuramı
|
||
| Özet |
| Given a matrix A∈Rm×n (n vectors in m dimensions), we consider the problem of selecting a subset of its columns such that its elements are as linearly independent as possible. This notion turned out to be important in low-rank approximations to matrices and rank revealing QR factorizations which have been investigated in the linear algebra community and can be quantified in a few different ways. In this paper, from a complexity theoretic point of view, we propose four related problems in which we try to find a sub-matrix C∈Rm×k of a given matrix A∈Rm×n such that (i) σmax(C) (the largest singular value of C) is minimum, (ii) σmin(C) (the smallest singular value of C) is maximum, (iii) κ(C)=σmax(C)/σmin(C) (the condition number of C) is minimum, and (iv) the volume of the parallelepiped defined by the column vectors of C is maximum. We establish the NP-hardness of these problems and further show that they do … |
| Anahtar Kelimeler |
| Approximation | Complexity | Condition number | Maximum volume sub-matrix | Subset selection |
Science Direct
On selecting a maximum volume sub-matrix of a matrix and related problems
BM Sürdürülebilir Kalkınma Amaçları
| Atıf Sayıları | |
| Web of Science | 169 |
| Scopus | 188 |
| Google Scholar | 355 |