许多（大多数？）列子集选择标准在列数较少时是NP难问题

《Linear Algebra and its Applications》：Many (most?) column subset selection criteria are NP hard for a few columns

　　

摘要

我们考虑了从一个实矩阵 $A \in \mathbb{R}^{m \times n}$ 中选择 $k$ 个代表性列的多种准则，适用于所需列数较少的情况，即 $1 \leq k \leq \min\{\text{rank}(A), m/3\}$。这些准则包括以下优化问题：绝对体积和S-最优性的最大化；二范数、Frobenius范数和 $p > 2$ 的Schatten $p$-范数下的范数、伪逆范数以及条件数的最小化；稳定秩的最大化；以及新的相对体积最大化准则，后者与条件数的幂次成反比。我们证明这些准则均为NP难问题，并且许多问题不允许存在多项式时间近似方案（PTAS）。为了将这些优化问题表述为判定问题，我们推导了子集选择准则的最优值，以及分块伪逆的表达式。

引言

给定一个一般矩阵 $A \in \mathbb{R}^{m \times n}$，寻找 $k$ 个代表性列 $C \in \mathbb{R}^{m \times k}$ 意味着什么？该问题被称为"列子集选择"。我们的目标是确立表1.1中流行的子集选择问题的复杂度类，当所需列数足够少时，即 $1 \leq k \leq \min\{\text{rank}(A), m/3\}$。

我们证明表1.1中大多数准则均为NP难问题，这意味着除非 $P = NP$，否则它们无法在多项式时间内求解。尽管大多数子集选择准则是NP难的，但并非全部如此。例如，具有最小Frobenius范数的子矩阵 $C$ 可以在多项式时间内计算（第4节）。

我们的策略如下：我们不考虑优化问题本身，例如寻找一个体积最大的子矩阵 $C \in \mathbb{R}^{m \times k}$，而是证明相关联的判定问题是NP难的，例如，给定 $b > 0$，寻找一个体积超过 $b$ 的子矩阵 $C \in \mathbb{R}^{m \times k}$。为了连接优化问题和判定问题，我们推导了子集选择准则的最优值（第8节），从而使优化问题可以表示为最优值对应的判定问题。

在确立了某个准则是NP难问题之后，合理地提出它是否可以在多项式时间内被近似。这引出了多项式时间近似方案（PTAS）的概念。PTAS是一种多项式时间算法，使得对于每个 $\epsilon > 0$，存在一个针对最小化问题的 $(1+\epsilon)$-近似算法，以及针对最大化问题的 $(1-\epsilon)$-近似算法[38, 第1节], [43, 定义1.2]。我们证明表1.1中的大多数准则也不允许存在PTAS。

我们聚焦于具有二元输出"是"或"否"的判定问题，并采用图灵计算模型，其中输入为有理数，输入规模以比特数衡量。我们归约中唯一的无理数是 $1/3$，它也可以用有理算术表示和计算[24, 第9节]。或者，我们的归约只需要验证矩阵 $A$ 的列是正交归一的，这可以完全基于稀疏模式确定，且内积为有理数。

复杂度类 $P$ 由确定性图灵机可以在多项式时间内求解的判定问题组成，而复杂度类 $NP$ 由确定性图灵机可以在多项式时间内验证"是"输出的判定问题组成。如果一个问题是NP难的，意味着 $NP$ 中的任意问题都可以对其进行多项式时间归约。如果一个判定问题属于 $NP$ 且也是NP难的，则它是NP完全问题。因此，一个NP难问题至少与NP完全问题一样难[20, 第5.1节]。

一个确立NP难性的标准策略是从一个NP完全问题到待解决问题进行多项式时间归约。这种归约使得可以将求解待解决问题的任何算法转换为求解NP完全问题的相应算法。特别地，在多项式时间内运行的归约使得可以将求解待问题的任何多项式时间算法转换为求解NP完全问题的相应多项式时间算法[20, 第1.5节]。遵循[9]，我们选择NP完全问题"精确覆盖3元集（X3C）"[20, A.3.1节]，该问题出现在Karp 1972年的NP完全问题列表中[28, 第4节]。

为了证明某个子集选择准则不允许存在PTAS，我们在最优值和某个特定的次优值之间创建一个"间隙"，即所谓的不可近似性阈值，并证明在超出该阈值处近似该准则是NP难的，即在间隙内的任何值处都是NP难的。

不幸的是，创建这样的间隙并不总是可行的[38, 第1节]，我们对几个准则未能做到这一点，包括 $p > 2$ 的Schatten $p$-范数最小化（第4节）和 $p > 2$ 的Schatten $p$-范数条件数最小化（第6节）。

我们推导了以下内容的NP难性结果和PTAS近似阈值：相对体积最大化（第2节）；体积和S-最优性最大化（第3节）；二范数、Frobenius范数和Schatten $p$-范数最小化（第4节）；伪逆的二范数、Frobenius范数和Schatten $p$-范数最小化（第5节）；条件数最小化（第6节）；以及稳定秩最大化（第7节）。为了将子集选择准则表述为判定问题，我们推导了这些准则的最优值（第8节），以及分块伪逆的表达式（第9节）。

我们的主要贡献包括以下方面：

1. 我们引入了"相对体积最大化"准则，并证明它是NP难的且不允许存在PTAS。与体积不同，相对体积能够检测矩阵是否病态，因为它与条件数的幂次成反比（第2节）。

2. 我们提供了严格的证明，推导了与[9]中不同的PTAS不可近似性阈值，针对伪逆的二范数最小化（第5.2节）和二范数条件数最小化（第6.2节）。

3. 我们证明以下准则是NP难的：$p$-范数伪逆最小化、$p$-范数条件数最小化以及 $p \geq 2$ 的混合$p$-范数条件数最小化（第6.1节），以及稳定秩最大化和 $p > 2$ 的$p$-稳定秩最大化（第7.1节）。

4. 我们证明以下准则不允许存在PTAS：伪逆的Frobenius范数最小化（第5.3节）以及 $p > 2$ 的伪逆$p$-范数最小化（第5.4节）；Frobenius范数条件数最小化（第6.3节）和混合条件数最小化（第6.4节）；以及稳定秩最大化（第7.2节）。

5. 我们推导了子集选择准则的最优值（第8节），从而使它们的优化版本可以表述为判定问题。

6. 我们推导了分块伪逆的表达式和$p$-范数界（第9节）。

我们简要概述了推导上述子集选择准则的NP难性结果（第1.4.1节）和PTAS结果（第1.4.2节）的方法。

我们执行以下步骤：

1. 通过将子集集合表示为具有单位范数列的矩阵 $A$，将子集选择准则在多项式时间内归约为X3C。

2. 对于具有单位范数列的这类矩阵，我们建立了子集选择准则的最优值（第8节），并证明最优值由具有正交归一列的矩阵达到。为以下准则推导了最优值：最大体积和S-最优性（引理1）、最大相对体积（引理2）、最小范数（引理4）、最小伪逆范数（引理5）、最小条件数（引理6）以及最大稳定秩（引理8）。

3. 根据[9]，X3C为真当且仅当 $A$ 具有正交归一列的子矩阵。

4. 结合以上两项意味着该准则达到最优当且仅当X3C为真。

这证明了以下准则的NP难性：相对体积最大化（定理1）、体积和S-最优性最大化（定理3）、范数最小化（定理6）、伪逆范数最小化（定理8）、条件数最小化（定理12）以及稳定秩最大化（定理16）。

我们执行以下步骤：

1. 单调性：奇异值交错定理意味着从矩阵中删除列只会增加其相对体积（引理3）并减小其条件数（引理7）。换句话说，添加列只会减小相对体积并增大条件数。

2. 因此，只需通过对具有2列的矩阵建立近似阈值来证明不存在PTAS即可。

3. 单调性意味着具有更多列的矩阵无法跨越近似阈值。

这证明了以下准则不允许存在PTAS：相对体积最大化（定理2）、体积（定理4）和S-最优性（定理5）的最大化；二范数最小化（定理7）；伪逆在二范数（定理9）、Frobenius范数（定理10）和Schatten $p$-范数（定理11）下的最小化；二范数（定理13）、Frobenius范数（定理14）和混合范数（定理15）下的条件数最小化；以及稳定秩最大化（定理17）。

我们回顾了列子集选择的现有工作，重点关注计算复杂度。列子集选择算法的早期综述包括[8]、[25]。

范数最小化。二范数的NP难性和PTAS不可近似性已在[9, 定理5和7]中证明。

伪逆范数最小化。二范数的NP难性和PTAS不可近似性已在[9, 定理4和7]中证明。针对宽矩阵 $A \in \mathbb{R}^{m \times n}$（$m < n$）的随机化和确定性算法在[1]、[2]、[29]、[34]、[35]、[37]中给出。在A-最优设计背景下，迹最小化对应于伪逆的Frobenius范数最小化[34]、[35]。例如，如果 $A$ 具有完全行秩，则 $A^\dagger = A^T(AA^T)^{-1}$，且 $\|A^\dagger\|_F^2 = \text{trace}((A^\dagger)^T A^\dagger) = \text{trace}((AA^T)^{-1})$。对于 $m = k$ 的归约基于奇圈打包（Odd Cycle Packing），即在简单无向图中寻找最大规模的顶点不相交奇圈族。

条件数最小化。二范数条件数的NP难性和PTAS不可近似性已在[9, 定理4和8]中证明。

体积最大化。NP难性和PTAS不可近似性已在[9, 定理4和6]中证明，而体积的指数不可近似性在[10, 定理5]、[18, 定理8]中提出。后者涉及针对矩阵 $A \in \mathbb{R}^{m \times n}$（$\text{rank}(A) = m$，$k = m$，$m = 1320d$，$n = 2112d$，对于某个 $d > 0$）的基于奇圈打包的归约。

一个早期结果[42, 定理3]在D-最优性背景下通过从哈密顿回路归约证明了体积最大化的NP难性，其中需要从 $m \times n$ 邻接矩阵中选择 $k \geq n$ 行 $C \in \mathbb{R}^{k \times n}$ 以最大化 $\text{vol}(C)^2 = \det(C^T C)$。

贪心算法在[9]、[14]中提出，局部确定性和随机化算法在[22]、[23]、[33]、[36]中提出。在[30]中将其扩展到Hilbert空间。局部体积最大化对于揭示秩的重要性在[13]中进行了展示。

S-最优性准则与相对体积相似，在[39, (3.5)]和[31, (3.10)]中引入。

残差最小化。Frobenius范数下的NP完全性在[40, 定理2.2]中建立，PTAS不可近似性在有唯一游戏猜想（Unique Games Conjecture）为真的条件下在[6, 定理1.1]中证明。二范数和Frobenius范数的算法在[5]中给出。早期的基于体积采样的随机化算法在[5]、[16]、[17]中给出。统计视角在[41]中提供，并证明子集选择等价于主变量方法。

设 $A \in \mathbb{R}^{m \times n}$ 为一个一般矩阵，$\text{rank}(A) \geq k$，奇异值为 $\sigma_1(A) \geq \cdots \geq \sigma_{\min\{m,n\}}(A) \geq 0$。设 $C \in \mathbb{R}^{m \times k}$ 为 $A$ 的 $k$ 列组成的子矩阵，其奇异值为 $\sigma_1(C) \geq \cdots \geq \sigma_k(C) \geq 0$。

奇异值交错定理[26, 7.3.P44]表明 $\sigma_{\min\{m,n\}-k+j}(A) \leq \sigma_j(C) \leq \sigma_j(A)$，$1 \leq j \leq k$。我们用 $I_n \equiv [e_1 \cdots e_n] \in \mathbb{R}^{n \times n}$ 表示单位矩阵，$e_j \in \mathbb{R}^n$ 表示其列。

章节片段

相对体积

我们引入了相对体积的概念，并证明相对体积最大化是NP难的（第2.1节）且不存在PTAS（第2.2节）。

对于秩 $\text{rank}(C) = k$ 的矩阵 $C \in \mathbb{R}^{m \times k}$，其相对体积定义为
$$\text{rvol}(C) \equiv \frac{\text{vol}(C)}{\|C\|_2^k} = \frac{\prod_{j=1}^k \sigma_j(C)}{\sigma_1(C)}$$
其中秩为 $k$ 的矩阵 $C \in \mathbb{R}^{m \times k}$ 的体积定义为
$$\text{vol}(C) \equiv \det(C^T C) = \prod_{j=1}^k \sigma_j(C)$$
如果 $C$ 是方阵，则 $\text{vol}(C) = |\det(C)|$。

从几何上讲，相对体积是平行六面体体积与包含它的立方体体积之比。

体积和S-最优性

我们证明体积和S-最优性最大化是NP难的（第3.1节），给出了体积最大化PTAS不可近似性阈值的严格证明（第3.2节），并证明S-最优性最大化不允许存在PTAS（第3.3节）。

我们想要寻找 $A \in \mathbb{R}^{m \times n}$ 的 $k$ 个列 $C$ 使得体积最大，$\max_C \text{vol}(C)$。该准则是NP难的且不允许存在PTAS[9]。目前最好的确定性算法[23]是局部体积最大化，生成的矩阵 $C$ 的奇异值为

二范数和Schatten $p$-范数

我们证明二范数和 $p > 2$ 的Schatten $p$-范数最小化是NP难的（第4.1节），并且二范数最小化不存在PTAS（第4.2节）。

对于 $p \geq 1$，矩阵 $A \in \mathbb{R}^{m \times n}$ 的Schatten $p$-范数定义为
$$\|A\|_{(p)} \equiv \left(\sum_{j=1}^{\min\{m,n\}} \sigma_j(A)^p\right)^{1/p}$$
特殊情况包括Frobenius范数 $\|A\|_{(2)} = \|A\|_F$ 和二范数 $\|A\|_{(\infty)} = \|A\|_2$。这里我们只考虑 $p$ 的整数值。

我们希望在 $A \in \mathbb{R}^{m \times n}$ 中找到 $k$ 列 $C$，使得其 Schatten p-范数最小，即 $\min_C \|C\|_{(p)}$。

**伪逆范数**

我们证明了最小化伪逆的 Schatten p-范数是 NP 难问题（第5.1节），推导了最小化伪逆的2-范数的新的可逼近性阈值（第5.2节），并证明了伪逆的Frobenius范数最小化（第5.3节）和 Schatten p-范数最小化（第5.4节）不存在 PTAS。

我们希望在 $A \in \mathbb{R}^{m \times n}$ 中找到 $k$ 列 $C$，使得其伪逆具有最小的 Schatten p-范数，即 $\min_C \|C^{\dagger}\|_{(p)}$。

**条件数**

我们证明了最小化2-范数条件数、Frobenius范数条件数、Schatten p-范数条件数、混合条件数以及当 $p>2$ 时的 Schatten p-范数混合条件数均为 NP 难问题（第6.1节），推导了2-范数条件数最小化的新的可逼近性阈值（第6.2节），并证明了Frobenius范数条件数最小化（第6.3节）和混合条件数最小化（第6.4节）不存在 PTAS。

对于 $p \geq 1$，矩阵 $C \in \mathbb{R}^{m \times k}$ 关于左逆的 p-范数条件数为

**稳定秩**

我们证明了最大化稳定秩以及当 $p>2$ 时的 p-稳定秩是 NP 难问题（第7.1节），并证明了稳定秩最大化不存在 PTAS（第7.2节）。

非零矩阵 $C \in \mathbb{R}^{m \times k}$ 的稳定秩定义为 $\mathrm{sr}(C) \equiv \|C\|_{\mathrm{F}}^2 / \|C\|_{2}^2$，且 $\mathrm{sr}(0_{m \times k}) = 0$。将其推广到当 $p>2$ 时的 Schatten p-范数[27]为 $\mathrm{sr}_{(p)}(C) \equiv \|C\|_{(p)}^p / \|C\|_{2}^p$，且 $\mathrm{sr}_{(p)}(0_{m \times k}) = 0$。显然，$\mathrm{sr}_{(2)}(A) = \mathrm{sr}(A)$。

我们希望在 $A \in \mathbb{R}^{m \times n}$ 中找到 $k$ 列 $C$，使得其 p-稳定秩最大，即 $\max_C \mathrm{sr}_{(p)}(C)$，其中 $p \geq 2$。

**子集选择准则的最优值**

为了将子集选择准则的优化版本表示为判定问题，我们推导了以下准则的最优值：最大体积和 S-最优性（第8.1节）、最大相对体积（第8.2节）、最小2-范数和 Schatten p-范数（第8.3节）、最小伪逆范数（第8.4节）、最小条件数（第8.5节）以及最大稳定秩（第8.6节）。

**分块伪逆的表达式**

对于分块列满秩矩阵，我们推导了分块伪逆的表达式（引理9），以及分块伪逆的Frobenius范数的下界（引理10）和当 $p>2$ 时 Schatten p-范数的下界（引理11）。

以下表达式的不同版本已出现在文献[3, 定理1]、[11, 定理2]和[7, 引理3.3和3.4]中。此处我们给出一个简短的、自包含的证明。

**引理 9** 设 $C = [C_1 \; C_2] \in \mathbb{R}^{m \times n}$，其中 $C_1 \in \mathbb{R}^{m \times k}$，$C_2 \in \mathbb{R}^{m \times (n-k)}$，$1 \leq k < n$。若 $\mathrm{rank}(C) = n$，则

$$C^{\dagger} = \begin{bmatrix} M_1^{\dagger} \\ M_2^{\dagger} \end{bmatrix}$$

**致谢**

我们非常感谢三位匿名审稿人，他们关于文章表述和文献引用的建设性反馈。

Ilse C.F. Ipsen | Arvind K. Saibaba