Many (most?) column subset selection criteria are NP hard for a few columns

이 논문은 행렬 $A \in \mathbb{R}^{m \times n}$ 에서 $k$개의 대표 열 (columns) 을 선택하는 열 부분집합 선택 (Column Subset Selection) 문제의 계산 복잡도 (computational complexity) 를 분석한 연구입니다. 저자들은 Ilse C.F. Ipsen 과 Arvind K. Saibaba 로, North Carolina State University 소속입니다.

주요 내용은 다음과 같습니다.

1. 연구 문제 (Problem)

주어진 행렬 $A$에서 $k$개의 열을 선택하여 부분행렬 $C$를 만드는 다양한 기준 (criteria) 들이 존재합니다. 이 논문은 $k$가 충분히 작은 경우 ($1 \le k \le \min\{\text{rank}(A), m/3\}$) 에 다음과 같은 최적화 문제들이 NP-hard인지, 그리고 **다항 시간 근사 알고리즘 (PTAS)**이 존재하는지를 규명하는 것을 목표로 합니다.

고려된 주요 기준들은 다음과 같습니다:

• 부피 최대화 (Volume Maximization): $vol(C) = \prod \sigma_j(C)$
• 상대 부피 최대화 (Relative Volume Maximization): $rvol(C) = vol(C) / \|C\|_2^k$ (새로운 기준)
• S-최적성 최대화 (S-optimality Maximization)
• 노름 최소화 (Norm Minimization): 2-노름, Frobenius 노름, Schatten $p$-노름 ($p>2$)
• 모의역행렬 (Pseudo-inverse) 노름 최소화: $\|C^\dagger\|_p$
• 조건수 최소화 (Condition Number Minimization): 2-노름, Frobenius 노름, 혼합 노름 등
• 안정적 랭크 최대화 (Stable Rank Maximization): $sr(C) = \|C\|_F^2 / \|C\|_2^2$

2. 방법론 (Methodology)

저자들은 다음과 같은 체계적인 접근 방식을 취했습니다.

1. NP-hard 증명 (NP-hardness Proofs):

   • 최적화 문제 대신 **결정 문제 (Decision Problem)**로 변환하여 분석했습니다. (예: "부피가 $b$를 초과하는 부분행렬이 존재하는가?")
   • NP-complete 문제인 3-집합 정확 덮개 (Exact Cover by 3 Sets, X3C) 문제를 열 부분집합 선택 문제로 다항 시간 환원 (polynomial time reduction) 시켰습니다.
   • 단위 노름을 가진 열들을 가진 행렬 $A$를 구성하고, X3C 가 참일 때만 부분행렬 $C$가 **직교 열 (orthonormal columns)**을 가질 수 있음을 보였습니다.
   • 각 기준 (부피, 조건수 등) 에 대한 **최적값 (optimal values)**을 유도하여, 최적값이 달성되는 것이 X3C 의 해와 동치임을 증명했습니다.

2. PTAS 부재 증명 (Inapproximability / No PTAS):

   • 최적값과 특정 하위 최적값 (suboptimal value) 사이의 **갭 (gap)**을 만들어 근사 불가능성 (inapproximability) 을 증명했습니다.
   • **단조성 (Monotonicity)**을 이용했습니다: 열을 제거하면 상대 부피는 증가하고 조건수는 감소하는 등의 성질을 이용해, $k=2$인 경우의 근사 임계값을 유도함으로써 일반적인 $k$에 대한 근사 불가능성을 보였습니다.
   • 특정 기준들에 대해서는 기존 문헌 [9] 의 결과와 다른, 더 엄밀하거나 새로운 근사 임계값 (inapproximability thresholds) 을 유도했습니다.

3. 주요 기여 및 결과 (Key Contributions & Results)

A. 새로운 기준 도입 및 분석

• 상대 부피 (Relative Volume) 도입: 부피는 행렬의 조건수 (condition number) 를 반영하지 못하지만, 상대 부피 ($rvol(C)$) 는 조건수의 역수에 비례하여 **불안정한 행렬 (ill-conditioned matrix)**을 감지할 수 있음을 보였습니다.
• 이 기준이 NP-hard 이며 PTAS 를 허용하지 않음을 증명했습니다 (임계값: $1/\sqrt{2}$).

B. NP-hard 및 PTAS 부재 증명 목록

다음 표는 논문의 핵심 결과를 요약한 것입니다 (대부분의 기준이 NP-hard 이며 PTAS 를 허용하지 않음).

기준 (Criterion)	NP-hard?	PTAS 존재?	비고
부피 (Volume)	Yes	No	기존 결과 재확인 및 엄밀한 증명
상대 부피 (Relative Volume)	Yes	No	새로운 기준
S-최적성 (S-optimality)	Yes	No
2-노름 (Two-norm)	Yes	No
Frobenius 노름	No (다항 시간 가능)	N/A	가장 작은 2-노름 열을 선택하는 그리디 알고리즘으로 해결 가능
Schatten $p$-노름 ($p>2$)	Yes	미확인 (Gap 생성 실패)
모의역행렬 2-노름	Yes	No	기존 결과와 다른 임계값 ($\sqrt{3}/2$) 유도
모의역행렬 Frobenius 노름	Yes	No	A-최적 설계 (A-optimal design) 와 연관
조건수 (Condition Number)	Yes	No	2-노름, Frobenius, 혼합 노름 등 모두 포함
안정적 랭크 (Stable Rank)	Yes	No

C. 수학적 도구의 개발

• 최적값 유도: 단위 노름을 가진 열을 가진 행렬에 대해 각 기준의 이론적 최적값 (예: 부피는 1, 조건수는 1 등) 을 유도하여 결정 문제 형식을 갖도록 했습니다.
• 분할된 모의역행렬 (Partitioned Pseudo-inverses): 행렬을 분할했을 때의 모의역행렬 표현식과 그 노름에 대한 하한을 유도했습니다. 이는 부분집합 선택 문제의 분석에 중요한 도구로 사용되었습니다.

4. 의의 (Significance)

1. 이론적 한계 규명: 열 부분집합 선택 문제의 많은 기준들이 NP-hard 이며, 다항 시간 내에 임의의 정밀도로 근사할 수 없다는 것을 엄밀하게 증명했습니다. 이는 실제 응용에서 근사 알고리즘의 성능 한계를 이해하는 데 기여합니다.
2. 새로운 지표 제안: 조건수에 민감한 '상대 부피'를 도입하여, 단순한 부피 최대화보다 더 강력한 열 선택 기준을 제시했습니다.
3. 정밀한 근사 임계값: 기존 연구 [9] 와 비교하여 2-노름 모의역행렬 최소화 및 조건수 최소화 문제에 대해 더 정확하거나 새로운 근사 불가능 임계값을 제시했습니다.
4. A-최적 설계와의 연관성: Frobenius 노름의 모의역행렬 최소화는 실험 설계 (A-optimal design) 에서의 트레이스 최소화 문제와 동치임을 지적하며, 통계적 실험 설계 이론과의 연결고리를 강화했습니다.

요약

이 논문은 행렬의 열 부분집합 선택 문제에서 널리 사용되는 다양한 최적화 기준들이 계산적으로 매우 어렵다는 것을 증명했습니다. 특히, 단위 노름 열을 가진 행렬을 가정하고 X3C 문제로 환원하여 NP-hard 성을 보였으며, 대부분의 기준에 대해 PTAS 가 존재하지 않음을 보였습니다. 또한, 조건수 민감도를 가진 새로운 '상대 부피' 기준을 제안하고, 분할된 모의역행렬에 대한 새로운 수학적 표현식을 도출하여 이 분야의 이론적 기반을 강화했습니다.