하한 합성곱

1. 개요[편집]

하한 합성곱 Infimal Convolution
다른 이름	에피-덧셈, (min,+) 합성곱, 최소-덧셈 합성곱
표기	f □ g
기하	에피그래프의 민코프스키 합
켤레	(f □ g)* = f* + g*
특수 사례	모로 포락 · 파쉬-하우스도르프 포락 · 거리함수

하한 합성곱은 두 함수를 “자원을 나눠 갖는 최적 배분”으로 합치는 연산이다. $f, g : \mathbb{R}^n \to (-\infty,+\infty]$ 에 대해

$$(f \,\square\, g)(x) \;=\; \inf_{y \in \mathbb{R}^n} \bigl\{\, f(y) + g(x-y) \,\bigr\}$$

로 정의한다. 보통의 합성곱에서 적분을 하한으로, 곱을 합으로 바꾼 것 — 즉 $(\min, +)$ 대수(열대 대수) 위의 합성곱이다. 읽는 법은 두 가지가 있고 둘 다 자주 쓴다.

• 경제학적 독법: 총량 $x$ 를 두 생산자에게 $y$ 와 $x-y$ 로 나눠 줄 때, 각자의 비용함수가 $f, g$ 라면 최적 분담의 총비용이 $(f\square g)(x)$ 다. 그래서 “비용함수의 합병”이라 부르기도 한다.
• 기하학적 독법: 아래에서 볼 대로 에피그래프의 민코프스키 합이다. 함수 두 개를 그래프째로 서로 쓸어 준 것.

이름은 낯설어도 결과물은 이미 다 봤을 것이다. 모로 포락도, 립시츠 정칙화도, 거리함수도, 영상처리의 침식·팽창도, 심지어 동적 계획법의 비용 합치기도 전부 이 연산의 사례다. 비매끄러운 것을 매끄럽게, 불연속을 연속으로 바꾸는 조작 대부분이 정체를 까 보면 하한 합성곱이라는 것이 이 문서의 요지다.¹

2. 기하 — 에피그래프의 민코프스키 합[편집]

정의를 에피그래프 $\mathrm{epi}\,f = \{(x,t) : t \ge f(x)\}$ 로 옮겨 보면 정체가 드러난다. 엄밀 에피그래프($t > f(x)$)에 대해

$$\mathrm{epi}_s (f \,\square\, g) \;=\; \mathrm{epi}_s f \;+\; \mathrm{epi}_s g$$

가 정확히 성립한다. 하한 합성곱은 에피그래프를 민코프스키 합으로 더하는 연산이며, 그래서 “에피-덧셈”(epi-addition)이라 불린다. 하한이 달성되는 경우에는 보통의 에피그래프에 대해서도 등식이 성립한다.

이 그림 하나로 여러 성질이 즉시 보인다. $g$ 의 에피그래프가 뾰족한 원뿔이면 $f$ 의 그래프 위에 그 원뿔을 대고 아래에서 쓸어 준 결과가 나오고, $g$ 가 포물면이면 포물면으로 쓸어 준 결과가 나온다. **“구조요소(structuring element)로 그래프를 아래에서 쓸어낸다”**는 이 이미지가 모로 포락, 립시츠 포락, 형태학 필터를 하나로 묶는다.

대수적 성질도 정리해 두자. 교환·결합법칙이 성립하고($f\square g = g\square f$, $(f\square g)\square h = f\square(g\square h)$), 항등원은 원점의 지시함수 $\delta_{\{0\}}$ 다. 즉 확장실수값 함수들의 모임은 $\square$ 아래에서 가환 모노이드를 이룬다. 그리고 $f, g$ 가 볼록이면 $f\square g$ 도 볼록이다(에피그래프의 민코프스키 합이 볼록이므로). 하한 합성곱은 항상 $f\square g \le \min\{f,g\}$ 를 만족한다 — 정의에서 $y=0$ 또는 $y=x$ 를 넣어 보면 $g(0)$ 이나 $f(0)$ 만큼의 상수가 붙지만, $f(0)=g(0)=0$ 인 표준 상황에서는 문자 그대로 둘 다보다 작다.

3. 켤레에서는 그냥 덧셈이다[편집]

하한 합성곱을 이론적으로 특별하게 만드는 항등식은 이것이다.

$$(f \,\square\, g)^* \;=\; f^* + g^*$$

언제나 성립한다 (고유성만 있으면 된다). 르장드르-펜셸 변환 아래에서 하한합성곱과 덧셈이 서로 자리를 바꾼다는 뜻이며, 보통의 합성곱이 푸리에 변환 아래에서 곱으로 바뀌는 것과 정확히 같은 구조다. 열대 대수에서는 르장드르 변환이 푸리에 변환 역할을 한다.

역방향은 조건이 붙는다.

$$(f+g)^* = \overline{f^* \,\square\, g^*}$$

이고, 하한이 달성되고 폐포를 취할 필요가 없으려면 정칙성 조건(예: $f$ 와 $g$ 의 정의역이 어떤 점의 근방에서 겹치고 그중 하나가 그 점에서 연속)이 필요하다. 이 비대칭 — 한쪽은 공짜, 다른 쪽은 조건부 — 이 볼록해석 정리들에 자꾸 “적절한 정칙성 조건 아래”라는 단서가 붙는 이유의 상당 부분이다.

부수적으로 나오는 판정 기준 하나. $f\square g$ 가 어디선가 $-\infty$ 가 되지 않으려면(즉 고유하려면) $f$ 와 $g$ 에 공통의 아핀 하계가 있어야 하고, 이는 $\mathrm{dom}\,f^* \cap \mathrm{dom}\,g^* \neq \emptyset$ 과 같다. 예컨대 $f(x)=x$, $g(x)=-x$ 를 넣으면 $(f\square g)(x) = \inf_y\{y - (x-y)\} = -\infty$ 로 즉시 붕괴한다. 하한 합성곱은 볼록성은 보존하지만 고유성은 보존하지 않는다.

4. 특수 사례 카탈로그[편집]

$g$ 를 무엇으로 잡느냐가 전부다.

• $g = \frac{1}{2t}\|\cdot\|_2^2$ → 모로 포락. 가장 유명한 사례. 볼록 $f$ 를 $C^1$ 으로 만들면서 최솟값과 최소점을 보존한다. 그 문서가 근접 연산자·후버 함수·prox 기반 알고리즘까지 다루고 있으니 여기서는 **“일반 연산의 한 사례”**로만 위치를 잡아 둔다. 켤레 항등식에 대입하면 $(M_{tf})^* = f^* + \frac{t}{2}\|\cdot\|^2$ — 원 쪽 평활화 = 쌍대 쪽 강볼록화 — 가 한 줄로 떨어진다는 것만 확인하면 충분하다.
• $g = L\|\cdot\|$ → 파쉬-하우스도르프 포락. $f \square (L\|\cdot\|)$ 는 $f$ 이하인 $L$-립시츠 함수 중 가장 큰 것이다. 원뿔로 쓸어 주니 기울기가 $L$ 을 넘을 수 없고, 원래 기울기가 $L$ 이하이던 곳은 그대로 남는다. 이 성질이 립시츠 정칙화, 확장 정리(맥셰인 확장), 그리고 요즘의 립시츠 제약 신경망 논의에 반복해서 나온다.
• $g = \delta_C$ (지시함수) → 평행이동 최소화. $(f \square \delta_C)(x) = \inf_{z\in C} f(x-z)$. 특히 $f=\delta_A$ 면 $\delta_A \square \delta_B = \delta_{A+B}$ 로 민코프스키 합이 나오고, $f = \|\cdot\|$ 면 $$(\|\cdot\| \,\square\, \delta_C)(x) = \inf_{z \in C}\|x - z\| = \mathrm{dist}(x, C)$$ 로 거리함수가 나온다. 지지함수가 볼록집합을 함수로 번역하는 사전이라면, 이쪽은 집합 연산을 함수 연산으로 옮기는 반대 방향 사전이다.
• $g = \frac12 \mathrm{dist}(\cdot, C)^2$ 계열 → 벌점법의 매끄러운 벌점항들이 여기서 나온다. 지시함수의 모로 포락이 거리 제곱의 절반이라는 사실과 위 항목을 조합하면 제약 최적화의 벌점 계열이 통째로 정리된다.
• $f$ 와 $g$ 가 각각 1계·2계 전변분 → 샹볼-리옹(1997)이 제안한 하한합성곱 정규화항. 조각별 상수(1계)와 조각별 아핀(2계) 중 싼 쪽으로 국소적으로 갈아탈 수 있어 전변분 잡음제거의 계단화를 완화한다. 오늘날 TGV의 직계 조상이다.

5. 형태학 — 침식과 팽창[편집]

영상처리의 수학적 형태학은 사실상 하한 합성곱의 응용 분야다. 평평한 구조요소 $B$ (대칭이라 하자)에 대해

$$(f \,\square\, \delta_B)(x) = \inf_{z \in B} f(x-z)$$

가 바로 그레이스케일 침식(erosion)이고, 부호를 뒤집은 상한 합성곱이 팽창(dilation)이다. 침식 뒤 팽창이 열림(opening), 반대가 닫힘(closing)이며, 이들이 잔점 제거·구멍 메우기 같은 실무 필터가 된다. 이진 영상으로 좁히면 지시함수만 남아 침식·팽창이 집합의 민코프스키 차·합으로 정확히 환원된다. 형태학의 대수 구조가 볼록해석의 그것과 같은 것은 우연이 아니라, 둘 다 $(\min,+)$ 대수 위에 있기 때문이다.

여기서 볼록성은 유지되지 않는다는 점만 주의하면 된다 — 영상은 볼록 함수가 아니고, 그래도 위 등식은 성립한다. 하한 합성곱 자체는 볼록성을 요구하지 않는 연산이다. 볼록성은 좋은 성질을 추가로 얹어 줄 뿐이다.

6. 계산 — 1차원 격자에서 O(n)[편집]

정의대로 계산하면 격자점 $n$ 개에 대해 $O(n^2)$ 이다. 그런데 실무에서 자주 쓰는 두 경우는 선형 시간에 끝난다.

(1) 이차 구조요소 — 하부 포물선의 하한포락. $D(p) = \min_{q}\{f(q) + (p-q)^2\}$ 를 구하는 문제는, 각 격자점 $q$ 마다 꼭짓점이 $(q, f(q))$ 인 포물선 하나를 놓고 그 포물선들의 하한포락(lower envelope)을 읽는 것과 같다. 포물선들이 폭이 같으므로 인접한 두 개의 교점이 단조롭게 이동하고, 스택 하나로 왼쪽에서 오른쪽으로 훑으며 가려지는 포물선을 버리면 $O(n)$ 에 포락이 완성된다. 펠젠스발브-후텐로허(2004)가 정리한 이 알고리즘이 거리변환·동적 계획법 기반 스테레오 정합·물체 검출의 표준 부품이다. 다차원은 축마다 1차원 패스를 돌리면 되는데, 이는 이차 커널이 분리가능(separable)하기 때문이다.

(2) 볼록 수열끼리. $f, g$ 가 볼록 수열이면 그 하한 합성곱은 두 증분 수열을 정렬 병합한 것의 누적합이다. 볼록 함수의 기울기가 단조증가하므로, 총량을 늘려 갈 때 항상 “지금 가장 싼 증분”을 고르면 되고 그게 곧 병합이다. 정렬이 이미 되어 있으니 $O(n+m)$. 자원 배분 문제의 그리디 최적성이 사실 이 항등식의 다른 표현이다.

일반적인 경우는 사정이 다르다. 임의의 두 수열에 대한 $(\min,+)$ 합성곱은 MinConv 문제로, $n^2/2^{\Theta(\sqrt{\log n})}$ 보다 실질적으로 빠른 알고리즘이 알려져 있지 않고 하위이차 알고리즘의 존재는 어렵다고 널리 여겨진다. 배낭 문제·최단경로 계열의 세밀 복잡도 논의가 이 문제를 허브로 삼는다. 즉 “쉬운 하한 합성곱”은 볼록성이나 이차 커널이라는 구조를 대가로 얻은 것이지 공짜가 아니다.²

7. 최적화 알고리즘에서의 역할[편집]

분리 가능한 정규화 문제 $\min_{u+v=x} \{J_1(u) + J_2(v)\}$ 의 최적값은 정의 그대로 $(J_1 \square J_2)(x)$ 다. 영상의 만화-질감 분해, 잡음 성분 분리, 저계수+희소 분해가 전부 이 꼴이고, 그래서 분해 모형의 값함수는 언제나 하한 합성곱이다.

알고리즘 쪽 접점은 켤레 항등식에서 곧장 나온다. $\min f(x) + g(Ax)$ 의 쌍대에는 $f^*$ 와 $g^*$ 의 합이 등장하고, 이 합을 원 쪽으로 되돌리면 하한 합성곱이 된다. 교대방향 승수법·더글러스-래치포드·근접 경사법이 “두 항을 갈라 각각 prox를 때리는” 구조를 갖는 것은, 그 분할이 하한합성곱↔덧셈 쌍대성을 따라 원시/쌍대를 오가기 때문이다. 실전 팁 하나 — $f\square g$ 의 근접 연산자는 일반적으로 닫힌 형태가 없지만, 켤레가 $f^*+g^*$ 라는 사실을 이용해 쌍대에서 처리하는 편이 대개 싸다.

8. 함정 — inf가 min이 아닐 때[편집]

이름이 “하한”인 데는 이유가 있다. 하한이 달성되지 않을 수 있다.

가장 깔끔한 예는 닫힌 볼록집합 두 개의 민코프스키 합이 닫히지 않는 고전적 사례다. $A = \{(s,t) : s>0,\ t \ge 1/s\}$ 와 $B = \{(s,0)\}$ (가로축)을 잡으면 둘 다 닫힌 볼록인데 $A + B$ 는 $\{t>0\}$ 이라 닫히지 않는다. 그러면 $\delta_A \square \delta_B = \delta_{A+B}$ 는 하반연속이 아니고, 켤레를 두 번 취하면 원래로 돌아오지 않는다. 이 때문에 정리 진술에 폐포 기호 $\overline{(\cdot)}$ 가 붙어 다닌다.

실전에서 이게 무슨 의미인가.

• 최적 분담점이 존재하지 않을 수 있다. 값은 잘 정의되는데 그 값을 주는 $y$ 가 없다. 수치적으로는 반복이 발산하거나 경계로 무한히 밀려나는 형태로 나타난다.
• 하한이 달성되는 충분조건을 챙겨 두는 것이 안전하다. $f$ 가 강제적(coercive)이거나, $g$ 가 강볼록이거나, 둘 중 하나의 정의역이 콤팩트면 대개 해결된다. 모로 포락이 유난히 얌전한 것도 $\frac{1}{2t}\|\cdot\|^2$ 가 강볼록이라 부분문제가 강볼록이 되어 최소점이 유일하게 존재하기 때문이다.
• 비볼록에서는 볼록성 보존이 깨진다. $f$ 나 $g$ 가 비볼록이면 결과도 비볼록이고, 하부 포물선 포락 알고리즘은 여전히 정확히 돌지만(그건 볼록성이 아니라 커널 구조에 의존한다) 최적화 이론의 보증은 전부 사라진다.³

9. 관련 문서[편집]

• 모로 포락 · 르장드르-펜셸 변환 · 지지함수 · 쌍대성
• 볼록 최적화 · 근접 경사법 · 교대방향 승수법
• 전변분 잡음제거 · 유계 변동 함수 · 수학적 형태학
• 거리 변환 · 부호 거리 함수 · 레벨셋 방법
• 동적 계획법 · 푸리에 변환 · 최적수송

10. Footnotes[편집]

1. 표기 $\square$ 는 록카펠라 이후 굳어졌는데, 논문마다 $\oplus$, $\nabla$, $\#$ 을 쓰기도 해서 처음 보면 무슨 기호인지 감이 안 온다. 참고로 이 연산을 “에피-덧셈”이라 부르는 유파와 “(min,+) 합성곱”이라 부르는 유파는 각각 볼록해석과 이산 알고리즘 쪽인데, 같은 등식을 서로 인용하지 않고 30년쯤 따로 발전시켰다. 학제간 연구의 어려움은 대개 이런 데서 온다. ↩

2. 그래서 “우리 알고리즘은 하한 합성곱을 계산합니다”라는 문장을 보면 자동으로 다음 줄을 찾아야 한다. 이차 커널인지, 볼록인지, 아니면 그냥 $O(n^2)$ 을 돌리고 있는지. 셋 다 아니면서 빠르다고 주장하면 뭔가 근사가 들어가 있다. ↩

3. 여담으로, 비볼록 $f$ 에 대해 $t\to\infty$ 로 모로 포락을 키우면 $f$ 의 볼록 포락(정확히는 $f^{**}$)에 가까워진다. 그래서 큰 $t$ 로 시작해 점점 줄이는 연속화 전략은 “볼록화된 문제에서 시작해 원래 문제로 돌아온다”는 그림이 된다. 물론 돌아오는 길에 원래 문제의 국소최소들이 하나씩 되살아나므로, 이 전략이 전역최적을 보장하지는 않는다. 마케팅 문구에서 이 부분은 대개 생략된다. ↩