Many (most?) column subset selection criteria are NP hard Note: The work was funded, in part, by the National Science Foundation through the awards DMS-1745654 and DMS-2411198, and the Department of Energy through the award DE-SC0023188.

Ilse C.F. Ipsen, Arvind K. Saibaba · 2025

Read Many (most?) column subset selection criteria are NP hard Note: The work was funded, in part, by the National Science Foundation through the awards DMS-1745654 and DMS-2411198, and the Department of Energy through the award DE-SC0023188. by Ilse C.F. Ipsen, Arvind K. Saibaba (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-02740.txt.

Introduction

Ilse Ipsen and Arvind Saibaba ask how hard it is to pick a few representative columns from a large matrix. The task, column subset selection, serves data reduction across science and engineering. Their 2025 paper covers many quality criteria, from volume and stable rank to condition number and norms of several kinds.

For small picks, at most a third of the rows, they show these criteria are NP-hard, meaning no fast exact method is expected. Many also resist good approximation schemes that run in polynomial time. To set up the proofs, they derive the best possible values for each criterion and formulas for split pseudo-inverses. One result also feeds trace optimization in A-optimal design, a tool for planning experiments.

Catalog record

CREATORIlse C.F. Ipsen, Arvind K. Saibaba
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE73 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-02740

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Many (most?) column subset selection criteria are NP hard Note: The work was funded, in part, by the National Science Foundation through the awards DMS-1745654 and DMS-2411198, and the Department of Energy through the award DE-SC0023188. Ilse C.F. Ipsen, Arvind K. Saibaba Abstract We consider a variety of criteria for selecting k k representative columns from a real matrix 𝑨 \boldsymbol{A} with rank ⁡ ( 𝐀 ) ≥ k \rank(\boldsymbol{A})\geq 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 p -norms for p > 2 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. \newpageafter abstract 1 Introduction Given a general 1 1 1 We make no assumptions on the dimensions m and n of \boldsymbol{A} . matrix \boldsymbol{A}\in{\mathbb{R}}^{m\times n} with \rank(\boldsymbol{A})\geq k , what does it mean to find k representative columns \boldsymbol{C}\in\mathbb{R}^{m\times k} of \boldsymbol{A} ? This problem is known as ‘column subset selection.’ Our goal is to establish the complexity classes for the popular subset selection problems in Table 1 . We show that most criteria in Table 1 are NP hard, which means they cannot be solved in polynomial time unless P=NP . Although most subset selection criteria are NP hard, not all are. For example, a submatrix \boldsymbol{C} with minimal Frobenius norm can be computed in polynomial time 2 2 2 A greedy algorithm picks the columns of \boldsymbol{A} with smallest two-norm. (Section 4 ). Our strategy is the following: Instead of considering the optimization problem, e.g., find a submatrix \boldsymbol{C}\in\mathbb{R}^{m\times k} with maximal volume, we show NP hardness instead for the associated decision problem, e.g., given b>0 , find a submatrix \boldsymbol{C}\in\mathbb{R}^{m\times k} whose volume exceeds b . To connect the optimization and decision problems, we derive optimal values for the subset selection criteria (Section 8 ), so that the optimization problems can be formulated as decision problems for the optimal values. Having established that a criterion is NP hard, it is reasonable to ask if it can be approximated in polynomial time. This leads to the concept of a Polynomial Time Approximation Scheme (PTAS) . A PTAS is a polynomial time algorithm such that for each \epsilon>0 there exists a (1+\epsilon) -approximation algorithm for minimization problems, and a (1-\epsilon) -approximation algorithm for maximization problems [ 31 , Section 1] , [ 34 , Definition 1.2] . We show that most criteria in Table 1 do not admit a PTAS either. 1.1 Complexity Theory We focus on decision problems with a binary output ‘yes’ or ‘no’, and adopt the Turing model of computation, where inputs are rational numbers and the input size is measured in the number of bits. The complexity class P consists of decision problems that a deterministic Turing machine can solve in polynomial time, while the complexity class NP consists of decision problems for which a deterministic Turing machine can verify an output of ‘yes’ in polynomial time. A problem is NP hard if there is polynomial time reduction to this problem from any problem in NP. A decision problem is NP complete if it is in NP and it is also NP hard. Thus, an NP hard problem is at least as hard as an NP complete problem [ 17 , Section 5.1] . A standard strategy for establishing NP hardness performs a polynomial time reduction from an NP complete problem to the problem at hand. This reduction makes it possible to convert any algorithm for solving the problem at hand into a corresponding algorithm for an NP complete problem. In particular, a reduction that operates in polynomial time makes it possible to convert any polynomial time for the problem at hand to a corresponding polynomial time algorithm for the NP complete problem [ 17 , Section 1.5] . Following [ 9 ] , we choose the NP complete problem ‘Exact cover by 3 sets (X3C)’ [ 17 , Section A.3.1] , which appears in Karp’s 1972 list of NP complete problems [ 24 , Section 4] . To show that a subset selection criterion does not admit a PTAS, we create a “gap” between the optimal value and a particular suboptimal value, the so-called threshold , and show that it is NP hard to approximate the criterion beyond the threshold, that is, for any value inside the gap. Unfortunately, creating such a gap is not always feasible [ 31 , Section 1] , and we were not able to do so for a few criteria, including Schatten p -norm minimization for p>2 (Section 4 ) and condition number minimization in Schatten p -norms for p>2 (Section 6 ). Quantity Criterion NP hard No PTAS Definition Volume \max_{\boldsymbol{C}}{\vol(\boldsymbol{C})} [ 9 , Theorem 4] [ 9 , Theorem 6] (1) \vol(\boldsymbol{C})\equiv\prod_{j=1}^{k}{\sigma_{j}(\boldsymbol{C})} Theorem 3 Theorem 4 \max_{\boldsymbol{C}}{\rvol(\boldsymbol{C})} Theorem 1 Theorem 2 \rvol(\boldsymbol{C})\equiv\vol(\boldsymbol{C})/\|\boldsymbol{C}\|_{2}^{k} \max_{\boldsymbol{C}}{\sopt(\boldsymbol{C})} Theorem 3 Theorem 5 \sopt(\boldsymbol{C})\equiv(\vol(\boldsymbol{C})/\prod_{i=1}^{k}{\|\boldsymbol{C}\boldsymbol{e}_{i}\|_{2})^{1/k}} Norm \min_{\boldsymbol{C}}{\|\boldsymbol{C}\|_{2}} [ 9 , Theorem 4] [ 9 , Theorem 5] Theorem 6 Theorem 7 \min_{\boldsymbol{C}}{\|\boldsymbol{C}\|_{F}} No N/A \min_{\boldsymbol{C}}{\|\boldsymbol{C}\|_{(p)}} Theorem 6 Pseudo-inverse \min_{\boldsymbol{C}}{\|\boldsymbol{C}^{\dagger}\|_{2}} [ 9 , Theorem 4] [ 9 , Theorem 7] Theorem 8 Theorem 9 \min_{\boldsymbol{C}}{\|\boldsymbol{C}^{\dagger}\|_{F}} Theorem 8 Theorem 10 \min_{\boldsymbol{C}}{\|\boldsymbol{C}^{\dagger}\|_{(p)}} Theorem 8 Theorem 11 Condition no \min_{\boldsymbol{C}}{\kappa_{2}(\boldsymbol{C})} [ 9 , Theorem 4] [ 9 , Theorem 8] \kappa_{2}(\boldsymbol{C})\equiv\|\boldsymbol{C}\|_{2}\|\boldsymbol{C}^{\dagger}\|_{2} Theorem 12 Theorem 13 \min_{\boldsymbol{C}}{\kappa_{F}(\boldsymbol{C})} Theorem 12 Theorem 14 \kappa_{F}(\boldsymbol{C})\equiv\|\boldsymbol{C}\|_{F}\|\boldsymbol{C}^{\dagger}\|_{F} \min_{\boldsymbol{C}}{\kappa_{D}(\boldsymbol{C})} Theorem 12 Theorem 15 \kappa_{D}(\boldsymbol{C})\equiv\|\boldsymbol{C}\|_{F}\|\boldsymbol{C}^{\dagger}\|_{2} \min_{\boldsymbol{C}}{\kappa_{D,p}(\boldsymbol{C})} Theorem 12 \kappa_{D,p}(\boldsymbol{C})\equiv\|\boldsymbol{C}\|_{(p)}\|\boldsymbol{C}^{\dagger}\|_{2} Stable rank \max_{\boldsymbol{C}}{\sr(\boldsymbol{C})} Theorem 16 Theorem 17 \sr(\boldsymbol{C})\equiv\|\boldsymbol{C}\|_{F}^{2}/\|\boldsymbol{C}\|_{2}^{2} \max_{\boldsymbol{C}}{\sr_{(p)}(\boldsymbol{C})} Theorem 16 \sr_{(p)}(\boldsymbol{C})\equiv\|\boldsymbol{C}\|_{(p)}^{p}/\|\boldsymbol{C}\|_{2}^{p} Residual \min_{\boldsymbol{C}}{\rho_{2}(\boldsymbol{C})} \rho_{2}(\boldsymbol{C})\equiv\|(\boldsymbol{I}-\boldsymbol{C}\boldsymbol{C}^{\dagger})\boldsymbol{A}\|_{2} \min_{\boldsymbol{C}}{\rho_{F}(\boldsymbol{C})} [ 33 , Theorem 2.2] [ 6 , Theorem 1.1] (2) \rho_{F}(\boldsymbol{C})\equiv\|(\boldsymbol{I}-\boldsymbol{C}\boldsymbol{C}^{\dagger})\boldsymbol{A}\|_{F} Table 1: Complexity of criteria for selecting k representative columns \boldsymbol{C} from a matrix \boldsymbol{A} : (1) Exponential inapproximability of the volume is shown in [ 10 , Theorem 5] . (2) Minimizing the Frobenius norm residual is NP complete [ 33 , Theorem 2.2] , and is PTAS inapproximable conditional on the Unique Games Conjecture being true [ 6 , Theorem 1.1] . 1.2 Overview We derive NP hardness results and PTAS approximation thresholds for: relative volume maximization (Section 2 ); volume and S-optimality maximization (Section 3 ); two-norm, Frobenius norm and Schatten p -norm minimization (Section 4 ); two-norm, Frobenius norm and Schatten p -norm minimization of pseudo-inverses (Section 5 ); condition number minimization (Section 6 ); and stable rank maximization (Section 7 ). To formulate the subset selection criteria as decision problems, we derive optimal values for the criteria (Section 8 ), as well as expressions for partitioned pseudo-inverses (Section 9 ). 1.3 Contributions Our main contributions include the following: 1. We introduce the criterion of ‘relative volume maximization’ and show that it is NP-hard and does not admit a PTAS (Section 2 ). 2. We present rigorous proofs to derive PTAS inapproximability thresholds that differ from those in [ 9 ] for two-norm minimization of the pseudo-inverse (Section 5.2 ) and two-norm condition number minimization (Section 6.2 ). 3. We show that the following criteria are NP-hard:

Read the complete text