Distance to nearest skew-symmetric matrix polynomials of bounded rank

기술 요약: 유계 랭크를 갖는 반대칭 행렬 다항식까지의 거리

문제 정의
본 논문은 구조화된 행렬 근사 문제(structured matrix nearness problem)를 다룬다. 주어진 $m \times m$ 크기의 차수 $d$인 행렬 다항식 $P(\lambda)$(복소 계수)에 대하여, 동일한 차수(또는 최대 $d$)와 지정된 짝수 랭크 $2r$ ($2 \le 2r \le m-1$)를 갖는 반대칭 행렬 다항식 $S(\lambda)$를 찾아 $P(\lambda)$와의 프로베니우스 거리(Frobenius distance)를 최소화하는 것이 목표이다.

이 문제는 잘 알려진 "특이성까지의 거리(distance to singularity)" 문제를 일반화한 것이다. 특이성까지의 거리가 특이 행렬 다항식(랭크 $< m$)을 찾는 것이라면, 본 연구는 특정된 더 낮은 랭크 $2r$을 목표로 한다. 저자들은 반대칭 행렬의 경우 랭크가 항상 짝수라는 점을 언급하며, 짝수 랭크 $2r$이라는 제약 조건이 자연스럽다고 설명한다. 문제는 $P(\lambda)$와 $S(\lambda)$의 계수 행렬 간 차이의 제곱 프로베니우스 노름의 합을 최소화하는 것으로 정식화된다.

방법론
제안된 방식인 GEARS(Generic Eigenstructures and Alternating direction method for Rank 2r approximation of Skew-symmetric matrix polynomials)는 반대칭 행렬 다항식의 일반적 고유 구조(generic eigenstructures)에 관한 최근의 이론적 발전에 기반한다.

1. 일반적 인수분해 (이론적 토대):
   핵-방법은 랭크가 최대 $2r$인 반대칭 행렬 다항식의 집합을 매개변수화하는 데 있다. [17, 18]의 결과에 기초하여, 저자들은 반대칭 행렬 다항식의 집합이 "일반적 집합" $G^{ss}_{d, 2r, m}$의 폐포(closure)라는 정리 3.1을 활용한다. 이 일반적 집합의 임의의 원소는 다음과 같이 인수분해될 수 있다:
   $$S(\lambda) = U(\lambda)V(\lambda)^T - V(\lambda)U(\lambda)^T$$
   여기서 $U(\lambda)$는 차수가 $\lfloor d/2 \rfloor$인 $m \times r$ 크기의 행렬 다항식이고, $V(\lambda)$는 차수가 $\lceil d/2 \rceil$인 $m \times r$ 크기의 행렬 다항식이다.

2. 교로 최소제곱법 (알고리즘 구현):
   벡터화 연산자($\text{vec}$)와 크로네커 곱(Kronecker product)을 사용하여 최소화 문제를 재정식화한다. 인수분해를 거리 측정식에 대입함으로써, 이 문제는 $U(\lambda)$와 $V(\lambda)$의 계수들에 대한 비볼록 최적화 문제(non-convex optimization task)가 된다.
   저자들은 이를 교로 최소제곱법(Alternating Least Squares, ALS) 전략을 사용하여 해결한다:

   • $U(\lambda)$를 고정하고, 구조화된 행렬 $M(U(\lambda))$를 포함하는 선형 최소제곱 문제를 통해 $V(\lambda)$를 구한다.
   • 새로 계산된 $V(\lambda)$를 고정하고, 유사하게 $U(\lambda)$를 구한다.
   • 수렴할 때까지 반복한다. 이 과정에서 거리의 수열은 단조 감소함이 보장된다.

3. 행렬 펜실에 대한 특수화 (차수 $d=1$):
   행렬 펜실(차수 1)의 특정 사례를 위해, 저자들은 더 효율적인 변형 알고리즘인 GEARS-SVD를 개발하였다.

   • 이들은 반대칭 펜실에 대한 랭크-1 분해를 제공하는 정리 5.3을 활용한다: $S_0 - \lambda S_1 = \sum_{i=1}^r (u_i v_i^T - v_i u_i^T)$, 여기서 $u_i$는 상수 벡터이고 $v_i$는 선형 다항식 벡터이다.
   • 이러한 구조 덕분에, 일반적인 다항식의 경우에 사용되는 거대한 크로네커 곱 시스템을 구축하는 대신, SVD 및 블록 분할을 통해 작은 선형 시스템을 직접 해결함으로써 ALS 단계를 수행할 수 있다. 이는 계산 비용을 크게 줄여준다.

주요 기여

• 임의의 짝수 랭크를 위한 알고리즘: 기존 방법들이 주로 특이성까지의 거리(랭크가 $m-1$ 또는 $m-2$인 경우)를 다루었던 것과 달리, 이 알고리즘은 임의로 지정된 짝수 랭크 $2r \ge 2$에 대해 작동한다.
• 이론적 매개변수화: 인수분해 기반 최적화를 가능하게 하는, 유계 랭크를 갖는 반대칭 다항식의 폐포에 대한 구성적 매개변수화를 확립하였다.
• 효율적인 펜실 솔버: GEARS-SVD는 반대칭 펜실의 특성을 활용하여 거대한 크로네커 곱 형식을 피함으로써 일반적인 GEARS 알고리즘보다 상당한 속도 향상을 제공한다.
• 수치적 검증: 저자들은 GEARS 및 GEARS-SVD를 기존 방법들(Riemann-Oracle 및 Matrix-Valued Function 접근법)과 비교하는 수치 실험을 제공한다.

결과
무작위 반대칭 행렬 다항식 및 펜실(최대 $50 \times 50$ 크기)에 대해 수행된 수치 실험은 다음을 보여준다:

• 정확도: GEARS는 다른 최신 방법들과 대등한 거리의 해를 찾아낸다.
• 특이성 품질: GEARS에 의해 생성된 해는 경쟁 알고리즘들보다 "더 특이하며"(더 작은 최소 특이값을 보임), 이는 해당 방법의 구성 방식과 일치한다.
• 성능: GEARS는 Riemann-Oracle 및 MVF 알고리즘보다 현저히 빠르다. 행렬 펜실의 경우, GEARS-SVD는 거대한 크로네커 곱 형식을 피함으로써 일반적인 GEARS 알고리즘보다 우수한 성능을 보인다.
• 확장성: 실행 시간은 행렬 크기에 따라 합리적으로 확장되며, 실수 영역의 경우가 동일한 출력 품질 대비 복소수 영역보다 약 10배 정도 빠르다.

의의 및 주장
본 논문은 자신의 접근 방식이 반대칭 다항식의 특정한 대수적 구조를 활용함으로써 기존의 최적화 기반 전략(예: Riemann-Oracle)과 구별되며 상호 보완적이라고 주장한다. 주요 의의는 다음을 수행하는 통합된 프레임워크를 제공하는 데 있다:

1. 특이성까지의 문제를 특수 사례로서 해결한다.
2. 임의의 지정된 짝수 랭크를 갖는 가장 가까운 다항식을 찾는 기능으로 확장한다.
3. 중요한 사례인 행렬 펜실에 대해 계산 효율적인 특화 알고리즘을 제공한다.

저자들은 현재의 방법이 반대칭 구조로 제한되어 있으며, 다른 구조화된 클래스(대칭, 팔린드롬 등)로의 확장은 향촉 과제로 남겨두고 있다고 겸허히 언급하였다. 이 알고리즘은 (반올림 오차를 제외하면) 정확히 랭크 $2r$인 다항식을 생성하며, 이러한 구조적 저계수 근사가 요구되는 제어 이론, 시스템 식별 및 미분-대수 방정식 분석 분야에서 실용적인 도구가 되도록 설계되었다.