상호간섭성

1. 개요[편집]

상호간섭성 Mutual Coherence
다른 이름	상호간섭도, 코히런스, μ(A)
정의	단위노름 열들의 최대 절대 내적
계산 비용	O(mn²) — 그람 행렬 한 번
하한	웰치 하한 √((n−m)/(m(n−1)))
등호 조건	등각 타이트 프레임(ETF)
대표 용도	희소 복원 보증, 사전·코드북 설계

상호간섭성(mutual coherence)은 행렬의 열들이 서로 얼마나 닮았는지를 숫자 하나로 요약한 양이다. 열이 전부 단위 노름으로 정규화된 $A = [a_1\,\cdots\,a_n] \in \mathbb{R}^{m\times n}$ 에 대해

$$\mu(A) = \max_{i \ne j} \bigl|\langle a_i,\, a_j\rangle\bigr|$$

로 정의한다. 열 중 가장 사이가 나쁜 — 정확히는 가장 사이가 좋은 — 한 쌍이 전부를 결정하는 최악의 경우 지표다.

값의 범위는 $0 \le \mu \le 1$ 이다. $\mu = 0$ 은 열들이 서로 직교한다는 뜻이고, 이건 $n \le m$ 일 때만 가능하다. 압축센싱처럼 $n \gg m$ 인 과완비(overcomplete) 상황에서는 $m$ 차원 공간에 $n$ 개의 방향을 우겨 넣어야 하니 $\mu > 0$ 이 강제되고, 문제는 “0으로 만들 수 있느냐”가 아니라 **“얼마나 작게 만들 수 있느냐”**로 바뀐다.

이 양이 이론에서 유독 자주 등장하는 이유는 하나다. 기저 추구나 직교 매칭 추구의 복원 보증에 쓰이는 다른 조건들 — 제한등척성(RIP), 스파크, 널공간 성질 — 은 전부 주어진 행렬에 대해 계산하는 것 자체가 NP-난해다. 반면 $\mu$ 는 그람 행렬 한 번이면 끝난다. 계산 가능한 유일한 보증 조건이라는 점이 $\mu$ 의 존재 이유이자, 뒤에 보게 될 지독한 보수성의 대가다.

2. 그람 행렬로 보기[편집]

$\mu$ 를 실제로 계산하는 방법은 정의 그대로다. 그람 행렬

$$G = A^\top A, \qquad G_{ij} = \langle a_i, a_j\rangle$$

를 만들면 열이 단위노름이므로 대각은 전부 1이고, $\mu$ 는 비대각 성분 절댓값의 최댓값이다. 비용은 $O(mn^2)$, 코드로는 두 줄이다. 여기서 $\mu$ 의 성격이 그대로 드러난다 — $G$ 가 단위행렬에 가까울수록 좋은 행렬이고, $\mu$ 는 그 “가까움”을 $\ell_\infty$ 식으로, 즉 가장 나쁜 한 칸만 보고 잰다.

이 정의 방식이 곧 한계이기도 하다. 비대각 성분 하나만 크고 나머지가 전부 0이어도 $\mu$ 는 그 하나의 값을 그대로 뱉는다. 실제 복원 성능은 “닮은 열 쌍이 몇 개나 있는가”에 훨씬 크게 좌우되는데 $\mu$ 는 그 정보를 통째로 버린다. 뒤에 나올 바벨 함수가 이 구멍을 메우려는 시도다.

3. 스파크, 그리고 $k < \frac12(1+1/\mu)$ 가 나오는 곳[편집]

$\mu$ 가 복원 보증으로 번역되는 경로는 스파크(spark)를 거친다. $\mathrm{spark}(A)$ 는 선형종속인 열들의 최소 개수로 정의한다. 행렬식 계수(rank)와 헷갈리기 쉬운데, 계수는 “최대 몇 개까지 독립인가”이고 스파크는 “최소 몇 개부터 종속인가”이며 둘은 전혀 다른 양이다. 항상 $2 \le \mathrm{spark}(A) \le m+1$ 이고, 등호를 달성하는 행렬을 풀 스파크(full spark) 행렬이라 부른다.

스파크가 중요한 이유는 유일성 정리 때문이다(Donoho–Elad 2003). $Ax = y$ 의 어떤 해가

$$\|x\|_0 < \tfrac12\,\mathrm{spark}(A)$$

를 만족하면, 그 해는 유일한 최희소해다. 증명은 한 줄이다 — 서로 다른 두 희소해가 있으면 그 차가 영공간에 들어가는데, 차의 비영 성분 수가 $\mathrm{spark}$ 미만이면 그런 영공간 벡터는 존재할 수 없다.

문제는 스파크 계산이 조합 탐색이라 NP-난해라는 것. 여기서 $\mu$ 가 등판한다. 임의의 $k$ 개 열을 골라 만든 부분 그람 행렬은 대각이 1이고 비대각 절댓값이 $\mu$ 이하이므로, 게르슈고린 원판 정리에 의해 최소 고윳값이 $1 - (k-1)\mu$ 이상이다. 이 값이 양수이면, 즉 $k < 1 + 1/\mu$ 이면 그 $k$ 개 열은 반드시 독립이다. 따라서

$$\mathrm{spark}(A) \ \ge\ 1 + \frac{1}{\mu(A)}$$

이고, 유일성 정리에 대입하면 그 유명한

$$\|x\|_0 < \frac12\left(1 + \frac{1}{\mu(A)}\right)$$

가 나온다. 이 문턱 아래에서는 최희소해가 유일할 뿐 아니라 기저 추구($\ell_1$ 최소화)와 직교 매칭 추구가 둘 다 그 해를 찾아낸다(Donoho–Elad 2003, Gribonval–Nielsen 2003, Tropp 2004). OMP 쪽은 흔히 $\mu < 1/(2k-1)$ 로 쓰는데, 이건 위 부등식을 $k$ 에 대해 정리한 것과 같은 조건이다.

4. 웰치 하한 — 아무리 잘 설계해도 여기까지[편집]

그럼 $\mu$ 를 얼마나 작게 만들 수 있나. 답은 순수하게 대수적인 하한으로 나온다. $G = A^\top A$ 의 계수는 많아야 $m$ 이므로 코시-슈바르츠에 의해

$$\mathrm{tr}(G^2) \ \ge\ \frac{(\mathrm{tr}\,G)^2}{\mathrm{rank}(G)} = \frac{n^2}{m}$$

이다. 한편 $\mathrm{tr}(G^2) = \sum_{i,j} G_{ij}^2 = n + \sum_{i \ne j} G_{ij}^2 \le n + n(n-1)\mu^2$ 이다. 두 식을 이어 붙이면 웰치 하한(Welch bound, 1974)이 떨어진다.

$$\mu(A) \ \ge\ \sqrt{\frac{n-m}{m(n-1)}}$$

$n \gg m$ 이면 우변은 $1/\sqrt{m}$ 에 수렴한다. 즉 간섭성은 측정 수의 제곱근 역수보다 작아질 수 없다. 이것이 이 분야에서 “제곱근 장벽”이라 부르는 벽의 정체다.

부등식 두 개가 동시에 등호가 되려면 조건이 두 개 붙는다. 첫째, $G$ 의 비영 고윳값이 전부 같아야 한다 — 이는 $AA^\top = \frac{n}{m}I_m$, 즉 $A$ 가 타이트 프레임이라는 뜻이다. 둘째, 모든 비대각 성분의 절댓값이 정확히 $\mu$ 로 같아야 한다 — 등각(equiangular). 둘을 합쳐 등각 타이트 프레임(equiangular tight frame, ETF)이라 부르고, 웰치 하한을 달성하는 행렬은 정확히 ETF다.

가장 작은 예가 평면 위 $120°$ 간격의 세 벡터(이른바 벤츠 프레임)다. $m=2, n=3$ 이면 웰치 하한은 $\sqrt{1/4} = 1/2$ 이고 실제 내적 절댓값도 $|\cos 120°| = 1/2$ 로 정확히 일치한다.

문제는 ETF가 아무 $(m,n)$ 에나 존재하지 않는다는 것이다. 실수 ETF는 $n \le m(m+1)/2$, 복소 ETF는 $n \le m^2$ 라는 상한이 있고, 그 안에서도 존재 여부는 조합론적 설계(아다마르 행렬, 차집합, 슈타이너 계)에 걸린 미해결 문제다.¹ 존재하지 않는 구간에서 간섭성을 최소화하는 프레임을 일반적으로 그라스만 프레임(Grassmannian frame)이라 부르는데, 이름 그대로 그라스만 다양체 위의 선 채우기(line packing) 문제 — ”$m$ 차원 공간에 $n$ 개의 직선을 서로 최대한 벌려 꽂기” — 와 정확히 같은 문제다(Strohmer–Heath 2003). 구면 코드·구 채우기와 같은 동네 문제이고, 대부분의 파라미터에서 최적해는 수치 탐색으로만 알려져 있다.

5. 랜덤 행렬은 얼마나 나쁜가[편집]

설계를 포기하고 그냥 가우시안 난수를 뽑으면 어떻게 되나. 정규화된 두 독립 랜덤 벡터의 내적은 대략 평균 0, 표준편차 $1/\sqrt{m}$ 이고, 그런 쌍이 $\binom{n}{2}$ 개 있다. 가우시안 최댓값의 점근으로

$$\mu \ \approx\ \sqrt{\frac{2\log\binom{n}{2}}{m}} \ =\ \Theta\!\left(\sqrt{\frac{\log n}{m}}\right)$$

이다. 즉 랜덤 행렬은 웰치 하한 $1/\sqrt{m}$ 을 $\sqrt{\log n}$ 배만큼 초과한다. 로그 인자 하나 차이니 점근적으로는 “거의 최적”이라 부를 만하고, 실제로 대부분의 압축센싱 논문이 랜덤 행렬로 만족하는 이유가 이것이다. 다만 상수배가 아니라 로그배라는 점이 아래에서 뼈아프게 작용한다.

6. 왜 이렇게 보수적인가[편집]

$\mu$ 기반 보증의 문제는 “약간 보수적”이 아니라 실용적으로 쓸 수 없을 만큼 보수적이라는 데 있다. 웰치 하한을 $k < \frac12(1+1/\mu)$ 에 대입하면 최선의 경우에도

$$k \ \lesssim\ \tfrac12\bigl(1 + \sqrt{m}\bigr) = O(\sqrt{m})$$

이다. 반면 $\ell_1$ 최소화의 실제 성공 영역은 $k = O(m/\log(n/m))$ 로, 차수 자체가 다르다. 숫자로 보면 더 참담하다. 가우시안 랜덤 행렬을 실제로 뽑아 $\mu$ 를 재고(5회 평균) 각 보증이 허용하는 최대 희소도를 계산하면 이렇다.

크기 m × n	랜덤 가우시안 μ	웰치 하한	μ 보증 최대 k	하한 달성 시 최대 k
64 × 256	0.55	0.109	1	5
128 × 512	0.42	0.077	1	7
256 × 1024	0.30	0.054	2	9

$256 \times 1024$ 행렬에서 간섭성이 보장해 주는 희소도는 $k = 2$ 다. 웰치 하한을 정확히 달성하는 ETF를 어떻게든 구해 와도 $k = 9$ 다. 그런데 같은 크기에서 $\ell_1$ 최소화는 실험적으로 수십 개 규모의 희소도를 안정적으로 복원한다. 이론이 예측하는 값과 실제 성능이 한 자릿수와 두 자릿수로 갈린다.

이유는 명확하다. $\mu$ 는 최악의 한 쌍만 보고, 유일성 논증은 그 최악값이 모든 $k$ 개 열 조합에 동시에 나타난다고 가정한다. 실제 행렬에서 그런 일은 일어나지 않는다. 게르슈고린 원판이라는 도구 자체도 매우 무딘 고윳값 한계다. 요컨대 $\mu$ 기반 보증은 “계산 가능”이라는 유일한 장점을 위해 정확도를 거의 전부 내다 판 결과물이다.²

7. 덜 비관적인 사촌들[편집]

• 바벨 함수(Babel function, Tropp 2004). $\mu_1(k) = \max_{|\Lambda|=k}\max_{j\notin\Lambda} \sum_{i\in\Lambda} |\langle a_i, a_j\rangle|$. 최댓값 하나가 아니라 $k$ 개의 합을 본다. 항상 $\mu_1(k) \le k\mu$ 이고, 대부분의 실제 사전에서는 훨씬 작다. 보증도 더 날카로워서 $\mu_1(k) + \mu_1(k-1) < 1$ 이면 OMP와 BP가 성공한다. 계산은 여전히 다항시간이지만 $\mu$ 보다는 비싸다.
• 정확 복원 조건(ERC). $\max_{j\notin S}\|A_S^{+}a_j\|_1 < 1$. 지지집합 $S$ 를 알아야 확인할 수 있어 사후 분석용이지만, 위 조건들의 진짜 뿌리다.
• 평균 간섭성(average coherence). 비대각 성분의 평균을 보는 지표로, 표적 지지집합이 랜덤이라는 가정 아래 훨씬 넓은 영역을 커버한다.
• 제한등척성(RIP). 가장 강력하지만 검증이 NP-난해라 “랜덤 행렬은 높은 확률로 만족한다”는 확률적 진술로만 쓴다.

정리하면 계산 가능성과 날카로움은 정확히 반비례한다 — $\mu$ 는 즉시 계산되지만 쓸모없이 보수적이고, RIP는 날카롭지만 계산할 수 없다. 그 사이 어딘가를 메우는 것이 바벨 함수와 평균 간섭성이다.

8. 실제로 쓰이는 곳[편집]

보증 자체는 쓸모가 없어도 $\mu$ 는 여전히 여기저기서 돈다. 설계 목적함수로서의 쓸모가 남아 있기 때문이다.

• 딕셔너리 학습의 정규화항. 학습된 사전은 원자들이 서로 닮아지는 경향이 있어 희소 코딩이 불안정해진다. 그람 행렬을 단위행렬 쪽으로 미는 항($\|A^\top A - I\|_F^2$)이나 간섭성 상한을 직접 제약으로 걸어 이를 억제한다. 여기서 목표는 “정리를 만족시키기”가 아니라 “알고리즘이 흔들리지 않게 하기”다.
• 통신 코드북·확산 수열. CDMA 확산 수열, MIMO 프리코딩 코드북, 다중 접속 서명 설계가 전부 “간섭성 최소 프레임 찾기”다. 웰치 하한이 원래 태어난 곳도 통신 쪽 신호 설계 문제였다.
• 측정 행렬 최적화. 센서 위치나 표본화 패턴에 자유도가 있는 문제(레이더 파형, MRI 궤적)에서 $\mu$ 를 대리 목적함수로 놓고 최적화한다. 완벽한 지표가 아니라는 걸 알면서도 미분 가능한 완화형(예: 그람 성분의 소프트맥스)을 쓰는 이유는, 대안이 없어서다.
• 진단 도구. 희소 복원이 잘 안 될 때 가장 먼저 재 보는 숫자. $\mu$ 가 0.9 같은 값이면 알고리즘을 고칠 게 아니라 사전 설계를 다시 해야 한다는 뜻이다. 열 정규화를 빼먹으면 $\mu$ 정의 자체가 무의미해지므로, 재기 전에 정규화부터 확인하는 것이 국룰이다.³

또 하나 짚어 둘 것 — 두 직교기저 사이의 간섭성은 별도 개념으로 $\mu(\Phi,\Psi) = \sqrt{m}\max_{i,j}|\langle \phi_i, \psi_j\rangle|$ 처럼 정규화해 정의하며, 값의 범위가 $[1, \sqrt{m}]$ 이 되도록 잡는다. 푸리에 변환 기저와 표준 기저 쌍이 최소값 1을 달성하는 최대 비간섭 쌍이고, 압축센싱에서 “무작위 주파수로 측정하고 시간 영역 희소성을 가정한다”가 잘 통하는 이유가 바로 이것이다. 이름과 기호가 비슷해 혼동하기 쉬운데, 이쪽은 작을수록 나쁜 값이 아니라 1에 가까울수록 좋은 값이다.⁴

9. 관련 문서[편집]

• 압축센싱 · 기저 추구 · 직교 매칭 추구 · CoSaMP
• 딕셔너리 학습 · 희소행렬 · 벡터 양자화
• 조건수 · 특이값 분해 · QR 분해
• 푸리에 변환 · 웨이블릿 변환 · 고속 푸리에 변환
• 라쏘 · 볼록 최적화 · 역문제

10. Footnotes[편집]

1. 복소 ETF의 상한 $n = m^2$ 를 달성하는 경우가 양자정보에서 말하는 SIC-POVM이다. 모든 차원에서 존재하는가(자우너 추측)는 1999년 제기된 이래 아직 미해결이며, 수치적으로는 수백 차원까지 찾아냈지만 일반 증명은 없다. 압축센싱 논문을 읽다가 갑자기 대수적 수론 논문으로 끌려가는 흔치 않은 경로. ↩

2. 그래서 이 조건을 실무에서 쓰는 방식은 대개 반대 방향이다. ”$k$ 가 이 문턱 아래니까 복원된다”가 아니라 ”$\mu$ 가 1에 가까우니 복원이 안 되는 게 당연하다”는 실패 설명용으로 쓴다. 충분조건을 필요조건처럼 읽는 셈인데, 논리적으로는 틀렸지만 경험적으로는 꽤 잘 맞는다. ↩

3. 열 정규화를 안 한 채로 $\mu$ 를 재면 노름이 큰 열이 무조건 최댓값을 만들어 낸다. 이 상태로 “우리 사전의 간섭성은 0.98입니다”라고 보고하는 실수가 생각보다 흔하다. 정의에 “단위노름”이 굵게 들어가 있는 데는 이유가 있다. ↩

4. 두 정의가 같은 단어(“coherence”)를 쓰는 바람에 생기는 혼란은 이 분야의 고질병이다. 논문을 읽을 때는 값의 범위부터 확인하는 게 빠르다 — $[0,1]$ 이면 열 간섭성, $[1,\sqrt{m}]$ 이면 기저 간 간섭성이다. ↩