퇴플리츠 행렬

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

퇴플리츠 행렬은 모든 i, j에 대해 M(i,j) = M(i+1, j+1)의 속성을 만족하는 정사각 행렬이다. 퇴플리츠 행렬은 덧셈과 곱셈 연산의 계산 복잡도가 낮고, 선형 컨볼루션과 푸리에 급수와 밀접하게 연결되어 있다. 이러한 행렬은 레빈슨 재귀 알고리즘과 같은 알고리즘을 사용하여 효율적으로 해를 구할 수 있는 퇴플리츠 시스템을 정의하며, 합성곱 계산에도 활용된다. 퇴플리츠 행렬은 독일 수학자 오토 퇴플리츠에 의해 도입되었다.

퇴플리츠 행렬

기본 정보

정의	주대각선 위의 모든 성분이 같은 정사각 행렬
종류	띠 행렬 순환 행렬
이름 유래	Otto Toeplitz

수학적 속성

연산	행렬 곱셈, 행렬 덧셈
관련 개념	컨벌루션

응용 분야

신호 처리	선형 시불변 시스템 컨벌루션 부호화
기타	수치 해석 시계열 분석

📚 더 읽어볼만한 페이지

선형대수학 - 벡터 공간
벡터 공간은 체 위의 가군으로 정의되는 대수적 구조로, 벡터 덧셈과 스칼라 곱셈 연산을 가지며 특정 공리들을 만족하고, 기저, 차원, 선형 사상 등의 개념을 통해 수학과 물리학 등 다양한 분야에서 활용된다.
선형대수학 - 선형 결합
선형 결합은 벡터 공간에서 벡터들의 스칼라 곱의 합으로 표현되는 식으로, 벡터 집합의 선형 독립성 판단 및 부분 공간 생성과 관련되며, 계수 제약을 통해 다양한 종류의 결합을 정의할 수 있고, 위상 벡터 공간이나 가군으로 일반화될 수 있다.
행렬 - 스핀 (물리학)
스핀은 양자역학적 각운동량으로, 양자화된 값을 가지며 자기 쌍극자 모멘트를 유발하여 다양한 분야에 응용되고 스핀트로닉스 기술 발전에 기여하지만, 전자의 스핀 기원은 아직 완전히 밝혀지지 않았다.
행렬 - 파울리 행렬
파울리 행렬은 양자역학에서 스핀을 나타내는 데 사용되는 에르미트 행렬이자 유니타리 행렬로, 행렬식은 -1이고 대각합은 0이며, 리 대수의 생성원이자 파울리 벡터로 정의되어 다양한 물리학 분야에서 활용된다.

1. 개요
2. 정의
3. 성질
- 3.1. 퇴플리츠 시스템
- 3.2. 추가 성질
4. 이산 컨볼루션
5. 무한 퇴플리츠 행렬
6. 역사

2. 정의

퇴플리츠 행렬은 모든 $i$ , $j$ 에 대해 $M_{i,j}=M_{i+1,j+1}$ 성질을 만족시키는 정사각 행렬 $M$ 이다. 즉, $n\times n$ 퇴플리츠 행렬은 다음과 같은 꼴이다.

: $M= \begin{pmatrix} a_{0} & a_{-1} & a_{-2} & \ldots & \ldots &a_{-n+1} \\ a_{1} & a_0 & a_{-1} & \ddots & & \vdots \\ a_{2} & a_{1} & \ddots & \ddots & \ddots& \vdots \\ \vdots & \ddots & \ddots & \ddots & a_{-1} & a_{-2}\\ \vdots & & \ddots & a_{1} & a_{0}& a_{-1} \\ a_{n-1} & \ldots & \ldots & a_{2} & a_{1} & a_{0} \end{pmatrix}$

3. 성질

두 $n \times n$ 퇴플리츠 행렬 $M, M'$ 에 대한 연산의 계산 복잡도는 다음과 같다.
* 덧셈: $O(n)$ 시간에 덧셈이 가능하다.
* 곱셈: $O(n^2)$ 시간에 곱셈이 가능하다.
* 연립 일차 방정식 $Mx=a$ 의 해: $O(n^2)$ (레빈슨 재귀 알고리즘)
* 행렬식 $\det M$ : $O(n^2)$ (레빈슨 재귀 알고리즘)

$n \times n$ 퇴플리츠 행렬은 $A_{i,j}=c_{i-j}$ 인 행렬 $A$ 로 정의될 수 있으며, 여기서 $c_{1-n},\ldots,c_{n-1}$ 은 상수이다. 이러한 퇴플리츠 행렬의 집합은 $n\times n$ 행렬의 부분 공간을 이루는 벡터 공간이다.

퇴플리츠 행렬은 역대칭이며, 대칭 퇴플리츠 행렬은 중심 대칭 및 양대칭 행렬이다. 또한, 퇴플리츠 행렬은 푸리에 급수와 밀접하게 연결되어 있는데, 이는 유한 차원 공간으로 압축된 삼각 다항식에 의한 곱셈 연산자가 이러한 행렬로 표현될 수 있기 때문이다. 선형 컨벌루션 역시 퇴플리츠 행렬과의 곱셈으로 표현할 수 있다.

퇴플리츠 행렬은 점근적으로 교환 가능하다. 이는 행과 열의 차원이 무한대로 갈 때 동일한 기저에서 대각화됨을 의미한다.

대칭 퇴플리츠 행렬의 경우, $\frac{1}{a_0} A = G G^\operatorname{T} - (G - I)(G - I)^\operatorname{T}$ 와 같은 분해가 존재한다. 여기서 $G$ 는 $\frac{1}{a_0} A$ 의 하삼각 부분이다. 역 비특이 대칭 퇴플리츠 행렬은 $A^{-1} = \frac{1}{\alpha_0} (B B^\operatorname{T} - C C^\operatorname{T})$ 로 표현된다. 여기서 $B$ 와 $C$ 는 하삼각 퇴플리츠 행렬이며 $C$ 는 엄격한 하삼각 행렬이다.

$A$ 가 퇴플리츠 행렬일 때, $Ax = b$ 형태의 행렬 방정식을 퇴플리츠 시스템이라고 부른다. $A$ 가 $n \times n$ 퇴플리츠 행렬이면, 이 시스템은 $n^2$ 개가 아닌 최대 $2n-1$ 개의 고유값을 갖기 때문에, 퇴플리츠 시스템의 해를 구하는 것은 일반적인 행렬 방정식보다 더 쉽다.

퇴플리츠 시스템은 슈어 알고리즘이나 레빈슨 재귀와 같은 알고리즘을 통해 $O(n^2)$ 시간 안에 해를 구할 수 있다. 레빈슨 재귀 알고리즘의 변형은 약하게 안정적인 것으로 알려져 있는데, 이는 조건이 좋은 선형 시스템에 대해 수치적 안정성을 보인다는 의미이다. 이러한 알고리즘들은 행렬식 $\det M$ 을 $O(n^2)$ 시간에 계산하는 데에도 활용될 수 있다. 퇴플리츠 행렬은 $O(n^2)$ 시간에 분해(인수분해)가 가능하며, LU 분해를 위한 베어리스 알고리즘은 안정적이다. LU 분해는 퇴플리츠 시스템을 풀고 행렬식을 계산하는 빠른 방법을 제공한다.

합성곱은 행렬 곱셈으로 표현될 수 있으며, 이 때 입력 중 하나는 퇴플리츠 행렬로 변환된다. 이 기법은 자기 상관, 상관, 이동 평균 등의 계산에도 확장할 수 있다.

퇴플리츠 행렬이 $a_i=a_{i+n}$ 이라는 추가적인 속성을 가지면 순환 행렬이라고 부른다. 퇴플리츠 행렬은 이다. 대칭 퇴플리츠 행렬은 이며, 동시에 이다.

3.1. 퇴플리츠 시스템

$A$ 가 퇴플리츠 행렬일 때, $Ax = b$ 형태의 행렬 방정식을 퇴플리츠 시스템이라고 부른다. $A$ 가 $n \times n$ 퇴플리츠 행렬이면, 이 시스템은 $n^2$ 개가 아닌 최대 $2n-1$ 개의 고유값을 갖기 때문에, 퇴플리츠 시스템의 해를 구하는 것은 일반적인 행렬 방정식보다 더 쉽다.

퇴플리츠 시스템은 슈어 알고리즘이나 레빈슨 재귀와 같은 알고리즘을 통해 $O(n^2)$ 시간 안에 해를 구할 수 있다. 레빈슨 재귀 알고리즘의 변형은 약하게 안정적인 것으로 알려져 있는데, 이는 조건이 좋은 선형 시스템에 대해 수치적 안정성을 보인다는 의미이다. 이러한 알고리즘들은 행렬식 $\det M$ 을 $O(n^2)$ 시간에 계산하는 데에도 활용될 수 있다. 퇴플리츠 행렬은 $O(n^2)$ 시간에 분해(인수분해)가 가능하며, LU 분해를 위한 베어리스 알고리즘은 안정적이다. LU 분해는 퇴플리츠 시스템을 풀고 행렬식을 계산하는 빠른 방법을 제공한다.

두 퇴플리츠 행렬의 덧셈은 O(n) 시간에, 퇴플리츠 행렬과 벡터의 곱셈은 O(n log n) 시간에, 두 퇴플리츠 행렬의 곱셈은 O( $n^2$ ) 시간에 수행 가능하다.

합성곱은 행렬 곱셈으로 표현될 수 있으며, 이 때 입력 중 하나는 퇴플리츠 행렬로 변환된다. 예를 들어, $\boldsymbol{h}$ 와 $\boldsymbol{x}$ 의 합성곱은 다음과 같이 나타낼 수 있다.

: $\begin{align}\boldsymbol{y} &= \boldsymbol{h} \ast \boldsymbol{x} \\&= \begin{bmatrix}h_1 & 0 & \ldots & 0 & 0 \\h_2 & h_1 & \ldots & \vdots & \vdots \\h_3 & h_2 & \ldots & 0 & 0 \\\vdots & h_3 & \ldots & h_1 & 0 \\h_{m-1} & \vdots & \ldots & h_2 & h_1 \\h_m & h_{m-1} & \vdots & \vdots & h_2 \\0 & h_m & \ldots & h_{m-2} & \vdots \\0 & 0 & \ldots & h_{m-1} & h_{m-2} \\\vdots & \vdots & \vdots & h_m & h_{m-1} \\0 & 0 & 0 & \ldots & h_m \\\end{bmatrix}\begin{bmatrix}x_1 \\ x_2 \\ x_3 \\ \vdots \\ x_n \\\end{bmatrix} \\\boldsymbol{y}^{\intercal} & =\begin{bmatrix}h_1 & h_2 & h_3 & \ldots & h_{m-1} & h_m \\\end{bmatrix}\begin{bmatrix}x_1 & x_2 & x_3 & \ldots & x_n & 0 & 0 & 0& \ldots & 0 \\0 & x_1 & x_2 & x_3 & \ldots & x_n & 0 & 0 & \ldots & 0 \\0 & 0 & x_1 & x_2 & x_3 & \ldots & x_n & 0 & \ldots & 0 \\\vdots & \vdots & \vdots & \vdots & \vdots & \ldots & \vdots & \vdots & \ldots & 0 \\0 & \ldots & 0 & 0 & x_1 & \ldots & x_{n-2} & x_{n-1} & x_{n} & \vdots \\0 & \ldots & 0 & 0 & 0 & x_1 & \ldots & x_{n-2} & x_{n-1} & x_{n} \\\end{bmatrix}\end{align}$

이러한 기법은 자기 상관, 상관, 이동 평균 등의 계산에도 활용할 수 있다.

퇴플리츠 행렬이 $a_i=a_{i+n}$ 이라는 추가적인 속성을 가지면 순환 행렬이라고 부른다. 퇴플리츠 행렬은 이다. 대칭 퇴플리츠 행렬은 이며, 동시에 이다. 푸리에 급수와 관련하여, 유한 차원 공간에 압축된 삼각 함수 다항식에 의한 곱셈 연산자는 퇴플리츠 행렬로 표현될 수 있기 때문에, 퇴플리츠 행렬은 푸리에 급수와 밀접하게 연관되어 있다.

3.2. 추가 성질

두 $n \times n$ 퇴플리츠 행렬 $M, M'$ 에 대한 연산의 계산 복잡도는 다음과 같다.
* 덧셈: $O(n)$ 시간에 덧셈이 가능하다.
* 곱셈: $O(n^2)$ 시간에 곱셈이 가능하다.
* 연립 일차 방정식 $Mx=a$ 의 해: $O(n^2)$ (레빈슨 재귀 알고리즘)
* 행렬식 $\det M$ : $O(n^2)$ (레빈슨 재귀 알고리즘)

$n \times n$ 퇴플리츠 행렬은 $A_{i,j}=c_{i-j}$ 인 행렬 $A$ 로 정의될 수 있으며, 여기서 $c_{1-n},\ldots,c_{n-1}$ 은 상수이다. 이러한 퇴플리츠 행렬의 집합은 $n\times n$ 행렬의 부분 공간을 이루는 벡터 공간이다.

퇴플리츠 행렬은 역대칭이며, 대칭 퇴플리츠 행렬은 중심 대칭 및 양대칭 행렬이다. 또한, 퇴플리츠 행렬은 푸리에 급수와 밀접하게 연결되어 있는데, 이는 유한 차원 공간으로 압축된 삼각 다항식에 의한 곱셈 연산자가 이러한 행렬로 표현될 수 있기 때문이다. 선형 컨벌루션 역시 퇴플리츠 행렬과의 곱셈으로 표현할 수 있다.

퇴플리츠 행렬은 점근적으로 교환 가능하다. 이는 행과 열의 차원이 무한대로 갈 때 동일한 기저에서 대각화됨을 의미한다.

대칭 퇴플리츠 행렬의 경우, $\frac{1}{a_0} A = G G^\operatorname{T} - (G - I)(G - I)^\operatorname{T}$ 와 같은 분해가 존재한다. 여기서 $G$ 는 $\frac{1}{a_0} A$ 의 하삼각 부분이다. 역 비특이 대칭 퇴플리츠 행렬은 $A^{-1} = \frac{1}{\alpha_0} (B B^\operatorname{T} - C C^\operatorname{T})$ 로 표현된다. 여기서 $B$ 와 $C$ 는 하삼각 퇴플리츠 행렬이며 $C$ 는 엄격한 하삼각 행렬이다.

$\boldsymbol{A} \boldsymbol{x} = \boldsymbol{b}$ 형태의 방정식은 n원 선형 방정식계를 나타내며, $\boldsymbol{A}$ 가 퇴플리츠 행렬인 경우 자유도가 $n^2$ 가 아닌 $2n - 1$ 이 된다. 퇴플리츠 계는 Levinson recursion^영어을 사용하여 Θ( $n^2$ ) 시간 내에 풀 수 있으며, 이 알고리즘의 변형은 제임스 번치(James Bunch)적 의미에서 약한 안정성을 가진다.

합성곱은 행렬의 곱으로 나타낼 수 있으며, 이때 입력 중 하나는 퇴플리츠 행렬로 변환된다. 이 기법은 자기 상관, 상관, 이동 평균 등의 계산에도 확장할 수 있다.

4. 이산 컨볼루션

컨볼루션 연산은 행렬 곱셈으로 구성될 수 있으며, 입력 중 하나를 퇴플리츠 행렬로 변환한다. 예를 들어, $h$ 와 $x$ 의 컨볼루션은 다음과 같이 공식화할 수 있다.

: $y = h \ast x =\begin{bmatrix}h_1 & 0 & \cdots & 0 & 0 \\h_2 & h_1 & & \vdots & \vdots \\h_3 & h_2 & \cdots & 0 & 0 \\\vdots & h_3 & \cdots & h_1 & 0 \\h_{m-1} & \vdots & \ddots & h_2 & h_1 \\h_m & h_{m-1} & & \vdots & h_2 \\0 & h_m & \ddots & h_{m-2} & \vdots \\0 & 0 & \cdots & h_{m-1} & h_{m-2} \\\vdots & \vdots & & h_m & h_{m-1} \\0 & 0 & 0 & \cdots & h_m\end{bmatrix}\begin{bmatrix}x_1 \\x_2 \\x_3 \\\vdots \\x_n\end{bmatrix}$

: $y^T =\begin{bmatrix}h_1 & h_2 & h_3 & \cdots & h_{m-1} & h_m\end{bmatrix}\begin{bmatrix}x_1 & x_2 & x_3 & \cdots & x_n & 0 & 0 & 0& \cdots & 0 \\0 & x_1 & x_2 & x_3 & \cdots & x_n & 0 & 0 & \cdots & 0 \\0 & 0 & x_1 & x_2 & x_3 & \ldots & x_n & 0 & \cdots & 0 \\\vdots & & \vdots & \vdots & \vdots & & \vdots & \vdots & & \vdots \\0 & \cdots & 0 & 0 & x_1 & \cdots & x_{n-2} & x_{n-1} & x_n & 0 \\0 & \cdots & 0 & 0 & 0 & x_1 & \cdots & x_{n-2} & x_{n-1} & x_n\end{bmatrix}.$

이러한 접근 방식은 자기상관, 상관 관계, 이동 평균 등을 계산하는 데 확장될 수 있다.

5. 무한 퇴플리츠 행렬

양방향 무한 퇴플리츠 행렬(즉, $\mathbb Z\times\mathbb Z$ 로 색인된 항목) $A$ 는 $\ell^2$ 에 대한 선형 연산자를 유도한다.

: $A=\begin{bmatrix}& \vdots & \vdots & \vdots & \vdots \\\cdots & a_0 & a_{-1} & a_{-2} & a_{-3} & \cdots \\\cdots & a_1 & a_0 & a_{-1} & a_{-2} & \cdots \\\cdots & a_2 & a_1 & a_0 & a_{-1} & \cdots \\\cdots & a_3 & a_2 & a_1 & a_0 & \cdots \\& \vdots & \vdots & \vdots & \vdots\end{bmatrix}.$

유도된 연산자는 퇴플리츠 행렬 $A$ 의 계수가 일부 본질적으로 유계인 함수 $f$ 의 푸리에 계수일 때에만 유계 연산자이다.

이러한 경우, $f$ 는 퇴플리츠 행렬 $A$ 의 심볼이라고 불리며, 퇴플리츠 행렬 $A$ 의 스펙트럼 노름은 그 심볼의 $L^\infty$ 노름과 일치한다. 수학적 증명은 쉽게 확립할 수 있으며, 참조 문헌 1.1절에서 찾을 수 있다.

6. 역사

독일의 수학자 오토 퇴플리츠(1881~1940)가 도입하였다.