کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10332786 | 687777 | 2014 | 18 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Column Subset Selection Problem is UG-hard
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
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âRmÃn and a positive integer k, and we want to select a sub-matrix C of k columns to minimize âAâÎ CAâF, where Î C=CC+ denotes the matrix of projection onto the space spanned by C. In the other problem, we are given AâRmÃ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âCURâF, where UâRcÃ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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 80, Issue 4, June 2014, Pages 849-859
Journal: Journal of Computer and System Sciences - Volume 80, Issue 4, June 2014, Pages 849-859
نویسندگان
A. Ãivril,