BLISS: Global Blind Identification of Linear Systems with Sparse Inputs

1. 문제 정의 (Problem Statement)

이 논문은 선형 시불변 (LTI) 시스템의 블라인드 식별 (Blind System Identification) 문제를 다룹니다. 기존 시스템 식별 이론은 입력 신호 $u(k)$가 알려진 경우 $A, B$ 행렬을 추정하는 데 있어 잘 정립되어 있지만, 입력이 알려지지 않은 경우 (Blind) 는 제한된 설정을 제외하고는 이론적으로 잘 이해되지 않았습니다.

• 시스템 모델:
  $$x(k+1) = A^\natural x(k) + B^\natural u(k)$$
  여기서 $x(k)$는 상태, $u(k)$는 입력, $A^\natural, B^\natural$은 미지의 시스템 파라미터입니다.
• 목표:
  입력 $u(k)$가 **희소 (Sparse)**하다는 가정 하에, 관측된 상태 데이터 $X^+, X$로부터 시스템 파라미터 $(A^\natural, B^\natural)$와 미지의 희소 입력 $U^\natural$을 동시에 복원하는 것입니다.
• 도전 과제:
  입력이 알려지지 않았기 때문에 이는 비선형 (Non-convex) 문제이며, 기존 희소 딕셔너리 학습 (Sparse Dictionary Learning) 이론을 직접 적용하기 어렵습니다 (왜냐하면 $A$가 미지수이기 때문에 혁신 행렬 $R = X^+ - AX^\top$이 고정되지 않기 때문입니다).

2. 방법론 (Methodology)

저자들은 시스템 식별 문제를 구조화된 행렬 분해 (Structured Matrix Factorization) 문제로 재해석하고, **완전 딕셔너리 학습 (Complete Dictionary Learning)**의 이론적 성과를 차용하여 해결책을 제시했습니다.

A. 볼륨 최소화 (Volume Minimization) 공식화

문제를 다음과 같은 제약 조건이 있는 볼륨 최소화 문제로 공식화했습니다.
$$\min_{A, B, U} \text{vol}(B) \quad \text{s.t.} \quad X^+ = AX^\top + BU^\top, \quad \max_i \|U_i\|_1 \le T\mu$$

• 여기서 $\text{vol}(B) = \sqrt{\det(B^\top B)}$입니다.
• 이 공식화는 입력 $u(k)$가 라플라스 분포를 따른다고 가정할 때의 **최대우도추정 (MLE)**과 동치임을 보였습니다.
• $A$가 알려진 경우, 이는 기존 Hu and Huang [19] 의 완전 딕셔너리 학습 문제와 동일해집니다.

B. 전역 식별성 (Global Identifiability) 조건: Persistent Scattering

기존의 "충분한 산란 (Sufficient Scattering)" 조건을 일반화하여 지속적 산란 (Persistent Scattering) 조건을 도입했습니다.

• 기하학적 정의: 상태와 입력으로 구성된 기본 존토프 (Fundamental Zonotope) $Z$가 단위 구를 포함하고, 그 경계가 특정 조건을 만족해야 합니다.
• 수학적 특징: 이 조건은 $Z$의 지지 함수 (Support Function) $\sigma_Z$와 관련이 있으며, 입력의 희소성과 시스템의 가시성 (Observability) 을 동시에 보장합니다.
• 주요 정리 (Theorem III.1): 만약 $(x, u)$가 지속적 산란 조건을 만족한다면, 위 볼륨 최소화 문제의 전역 최적해 $(A^\star, B^\star, U^\star)$는 참값 $(A^\natural, B^\natural, U^\natural)$과 스케일 및 치환 (Permutation) 을 제외하고 동일함을 증명했습니다.

C. BLISS 알고리즘 (알고리즘적 구현)

이론적 결과를 실제 계산에 적용하기 위해 **일반화된 교대 방향 승수법 (Generalized ADMM)**을 개발했습니다.

• 핵심 아이디어: $A$를 제거하기 위해 $P^\perp_X = I - XX^\dagger$ (상태 공간의 직교 여공간) 를 사용하여 문제를 $\Phi$와 $U$에 대한 문제로 변환합니다.
• 업데이트 규칙:
  • $U$ 업데이트: 확장된 $\ell_1$-볼 (Scaled $\ell_1$-ball) 에 대한 투영 (Projection).
  • $\Phi$ 업데이트: $f(\Phi) = -\log|\Phi|$ 함수에 대한 근사 연산자 (Proximal operator) 를 사용. 이는 SVD 를 통해 폐쇄형 (Closed-form) 으로 계산 가능합니다.
• 수렴성: 원 - 이중 잔차 (Primal-Dual Residual) 균형 조정 기법을 사용하여 매개변수 $\rho$를 적응적으로 조절하며, 유계 (Bounded) 된 반복 수렴을 보장합니다.

3. 주요 기여 (Key Contributions)

1. 문제 공식화: 관측된 상태 데이터만으로 희소 입력을 가진 LTI 시스템의 블라인드 식별을 제약 비볼록 볼륨 최대화 문제로 공식화했습니다.
2. 이론적 증명: 지속적 산란 (Persistent Scattering) 조건 하에서 시스템 파라미터와 입력의 **전역 식별성 (Global Identifiability)**을 증명했습니다. 이는 기존 딕셔너리 학습과 선형 시스템 식별의 조건을 모두 강화한 결과입니다.
3. 알고리즘 개발: 효율적인 폐쇄형 근사 업데이트를 활용하는 BLISS 알고리즘을 제안했습니다.
4. 실험적 검증: 단일 궤적 (Single trajectory) 에서도 충분한 샘플과 입력 희소성이 주어지면 참값을 전역적으로 복원할 수 있음을 실험적으로 입증했습니다.

4. 실험 결과 (Results)

• 실험 설정: 상태 차원 $n=100$, 입력 차원 $m=25$인 안정적이고 제어 가능한 시스템을 사용했습니다. 입력은 가우시안 또는 라플라스 분포를 따르며 희소성을 조절했습니다.
• 위상 전이 (Phase Transition):
  • 입력의 희소도가 높고 (Sparsity fraction $s/m$가 낮음), 궤적 길이 $T$가 길수록 성공 확률이 급격히 증가하는 명확한 위상 전이 현상을 관찰했습니다.
  • 희소 입력 (Sparse inputs) 일수록, 그리고 데이터 양 ($T$) 이 많을수록 평균적으로 성능이 향상되었습니다.
• 비교 분석:
  • 알려진 $A$ (Oracle) vs. 알려지지 않은 $A$: $A$를 아는 경우 (기존 딕셔너리 학습) 가 $A$를 모르는 경우 (BLISS) 보다 성능이 좋지만, BLISS 역시 희소 입력 조건 하에서 높은 성공률을 보였습니다.
  • 분포 영향: 가우시안 입력이 라플라스 입력보다 약간 더 밀집된 입력에서도 복원에 성공하는 경향을 보였습니다.
• 수렴성: 초기 매개변수 $\rho_0$를 오라클 값에 가깝게 설정할 때 알고리즘이 훨씬 빠르게 수렴함을 확인했습니다.

5. 의의 및 결론 (Significance)

• 학문적 통합: 시스템 제어 이론 (System Identification) 과 머신러닝 (Sparse Dictionary Learning) 의 두 분야를 연결하여, 희소성 가정이 블라인드 식별 문제를 해결하는 핵심 열쇠임을 보였습니다.
• 실용적 가치: 실제 자연과학 (확산 과정, 신경망 활성화) 및 정보과학 (고장 감지, 액추에이터 스케줄링) 분야에서 입력 신호를 측정할 수 없는 상황에서도 시스템 모델을 학습할 수 있는 강력한 이론적 기반과 알고리즘을 제공합니다.
• 미래 전망: 이 연구는 잡음이 있는 환경이나 과완전 (Overcomplete, $m > n$) 시스템으로의 확장을 위한 기초를 마련했습니다.

요약하자면, 이 논문은 BLISS 알고리즘을 통해 희소 입력을 가진 선형 시스템의 블라인드 식별 문제를 볼륨 최소화 관점에서 접근하고, 지속적 산란이라는 새로운 기하학적 조건 하에서 전역적 해의 유일성을 수학적으로 증명하며, 이를 효율적으로 계산하는 알고리즘을 제시한 획기적인 연구입니다.