Many (most?) column subset selection criteria are NP hard for a few columns
This work addresses computational complexity issues in matrix subset selection, which is incremental but important for applications like experimental design and data analysis.
The paper tackles the problem of selecting a small subset of columns from a matrix under various optimization criteria, such as volume maximization and condition number minimization, and shows that these problems are NP-hard and often lack efficient approximation schemes.
We consider a variety of criteria for selecting k representative columns from a real mxn matrix A, when sufficiently few columns are required, i.e., 1<= k<= min{rank(A), m/3}. The criteria include the following optimization problems: absolute volume and S-optimality maximization; norm, pseudo-inverse norm, and condition minimization number in the two-norm, Frobenius norm and Schatten p-norms for p>2; stable rank maximization; and the new criterion of relative volume maximization, which is inversely proportional to a power of the condition number. We show that these criteria are NP hard and many 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. The results for minimization of the pseudo-inverse in the Frobenius norm are applicable to trace optimization in A-optimal design.