标题： 许多（大多数？）列子集选择准则都是NP难的 显示英文标题

标题： Many (most?) column subset selection criteria are NP hard

摘要： 我们考虑从一个实矩阵A中选择k个代表性列的各种标准，其中rank(A)>=k。 这些标准包括以下优化问题：绝对体积和S最优性最大化；在二范数、Frobenius范数和p范数（p>2）下的范数和条件数最小化；稳定秩最大化；以及相对体积最大化的新标准。 我们证明这些标准是NP难的，并且不适用于多项式时间近似方案（PTAS）。 为了将优化问题表述为决策问题，我们推导了子集选择标准的最优值，以及分块伪逆的表达式。 显示英文摘要

摘要： We consider a variety of criteria for selecting k representative columns from a real matrix A with rank(A)>=k. The criteria include the following optimization problems: absolute volume and S-optimality maximization; norm and condition minimization in the two-norm, Frobenius norm and Schatten p-norms for p>2; stable rank maximization; and the new criterion of relative volume maximization. We show that these criteria are NP hard and do not admit polynomial time approximation schemes (PTAS). To formulate the optimization problems as decision problems, we derive optimal values for the subset selection criteria, as well as expressions for partitioned pseudo-inverses.