Özet

We address two problems related to selecting an optimal subset of columns from a matrix. In one of these problems, we are given a matrix A∈ R m× n and a positive integer k, and we want to select a sub-matrix C of k columns to minimize‖ A− Π C A‖ F, where Π C= C C+ denotes the matrix of projection onto the space spanned by C. In the other problem, we are given A∈ R m× n, positive integers c and r, and we want to select sub-matrices C and R of c columns and r rows of A, respectively, to minimize‖ A− C U R‖ F, where U∈ R c× r is the pseudo-inverse of the intersection between C and R. Although there is a plethora of algorithmic results, the complexity of these problems has not been investigated thus far. We show that these two problems are NP-hard assuming UGC.

Anahtar Kelimeler

Hardness | Matrices | Subset selection | Unique Games Conjecture

Science Direct

Atıf Sayıları
Web of Science	30
Scopus	32
Google Scholar	50

Column Subset Selection Problem is UG-hard

Paylaş