テプリッツ行列

線型代数学において、テプリッツ行列（Toeplitz Matrix）または対角定数行列（だいかくじょうていぎょう）は、オットー・テプリッツにちなんで名付けられ、左から右へ下降する各対角成分が定数である行列である。例えば、次の行列はテプリッツ行列である。

${\displaystyle \qquad {\begin{bmatrix}a&b&c&d&e\\f&a&b&c&d\\g&f&a&b&c\\h&g&f&a&b\\i&h&g&f&a\end{bmatrix}}.}$

任意の行列の 形式${\displaystyle n\times n}$ ${\displaystyle A}$

${\displaystyle A={\begin{bmatrix}a_{0}&a_{-1}&a_{-2}&\cdots &\cdots &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}&\cdots &\cdots &a_{2}&a_{1}&a_{0}\end{bmatrix}}}$

はテプリッツ行列である。の要素を と表記すると、 ${\displaystyle i,j}$ ${\displaystyle A}$ ${\displaystyle A_{i,j}}$

${\displaystyle A_{i,j}=A_{i+1,j+1}=a_{i-j}.}$

テプリッツ行列は必ずしも正方行列ではありません。

テプリッツ方程式を解く

次のような行列方程式

${\displaystyle Ax=b}$

がテプリッツ行列であるとき、テプリッツ系と呼ばれます。 がテプリッツ行列であるとき、系は ではなく、最大で 個の一意の値しか持ちません。したがって、テプリッツ系の解はより容易であると予想されます。実際、その通りです。 ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle n\times n}$ ${\displaystyle 2n-1}$ ${\displaystyle n^{2}}$

テプリッツシステムは、シュアーアルゴリズムやレビンソンアルゴリズムなどのアルゴリズムによって時間的に解くことができます。^{[1] [2]} 後者の変種は弱安定（つまり、条件付き線形システムに対して数値安定性を示す）であることが示されています。^[3]これらのアルゴリズムは、テプリッツ行列の行列式を時間的に 求めるためにも使用できます。^[4]${\displaystyle O(n^{2})}$ ${\displaystyle O(n^{2})}$

テプリッツ行列は時間で分解（因数分解）することもできます。^[5] LU分解 のBareissアルゴリズムは安定しています。^[6] LU分解はテプリッツ行列を解くための簡単な方法であり、行列式の計算にも役立ちます。 ${\displaystyle O(n^{2})}$

プロパティ

• テプリッツ行列は、定数 に対して となる行列として定義されます。テプリッツ行列の集合は、行列のベクトル空間の部分空間です（行列の加算とスカラー乗算の下で）。${\displaystyle n\times n}$ ${\displaystyle A}$ ${\displaystyle A_{i,j}=c_{i-j}}$ ${\displaystyle c_{1-n},\ldots ,c_{n-1}}$ ${\displaystyle n\times n}$ ${\displaystyle n\times n}$
• 2 つのテプリッツ行列は、時間内に加算され（各対角要素の 1 つの値のみを保存することにより）、時間内に乗算される可能性があります。${\displaystyle O(n)}$ ${\displaystyle O(n^{2})}$
• テプリッツ行列は、半対称行列です。対称テプリッツ行列は、中心対称かつ両対称です。
• テプリッツ行列はフーリエ級数とも密接に関連しています。これは、有限次元空間に圧縮された三角多項式による乗算演算子が、このような行列で表せるためです。同様に、線形畳み込みはテプリッツ行列による乗算として表すことができます。
• テプリッツ行列は漸近的に交換します。つまり、行と列の次元が無限大に近づくとき、同じ基底で対角化します。
• 対称テプリッツ行列の場合、分解は次のようになる。

${\displaystyle {\frac {1}{a_{0}}}A=GG^{\operatorname {T} }-(G-I)(G-I)^{\operatorname {T} }}$

はの下三角部分です。${\displaystyle G}$ ${\displaystyle {\frac {1}{a_{0}}}A}$

• 非特異対称テプリッツ行列の逆行列は次のように表現される。

${\displaystyle A^{-1}={\frac {1}{\alpha _{0}}}(BB^{\operatorname {T} }-CC^{\operatorname {T} })}$

ここで、およびは下三角テプリッツ行列であり、は厳密に下三角行列である。^[7]${\displaystyle B}$ ${\displaystyle C}$ ${\displaystyle C}$

離散畳み込み

畳み込み演算は行列乗算として構築することができ、入力の1つはテプリッツ行列に変換されます。例えば、と畳み込みは次のように定式化できます。 ${\displaystyle h}$ ${\displaystyle x}$

${\displaystyle 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}}}$

${\displaystyle 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}}.}$

このアプローチは、自己相関、相互相関、移動平均など を計算するように拡張できます。

無限テプリッツ行列

双無限テプリッツ行列（つまり、 によってインデックス付けされた要素）は、上に線形演算子を誘導します。 ${\displaystyle \mathbb {Z} \times \mathbb {Z} }$ ${\displaystyle A}$ ${\displaystyle \ell ^{2}}$

${\displaystyle 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}}.}$

誘導演算子が有界となるのは、テプリッツ行列の係数が本質的に有界な関数のフーリエ係数である場合のみです。 ${\displaystyle A}$ ${\displaystyle f}$

このような場合、はテプリッツ行列 の記号と呼ばれ、テプリッツ行列のスペクトルノルムはその記号のノルムと一致する。証明は、BöttcherとGrudskyの定理1.1に見られる。^[8]${\displaystyle f}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle L^{\infty }}$

参照

• 巡回行列は、次の追加の性質を持つ正方テプリッツ行列である。${\displaystyle a_{i}=a_{i+n}}$
• ハンケル行列、「逆」（つまり行が反転した）テプリッツ行列
• シェグーの極限定理 – 大規模なテプリッツ行列の行列式
• テプリッツ演算子

注記

1. Press et al. 2007, §2.8.2—テプリッツ行列
2. ヘイズ 1996、第5.2.6章
3. クリシュナ＆ワン 1993
4. Monahan 2011, §4.5—テプリッツシステム
5. ブレント 1999
6. Bojanczykら 1995
7. ムケルジー＆マイティ 1988
8. ボッチャー＆グルツキー 2012

参考文献

• Bojanczyk, AW; Brent, RP; de Hoog, FR; Sweet, DR (1995)「Bareiss分解アルゴリズムと関連するToeplitz分解アルゴリズムの安定性について」、SIAM Journal on Matrix Analysis and Applications、16 : 40– 57、arXiv : 1004.5510、doi :10.1137/S0895479891221563、S2CID  367586
• ベッチャー、アルブレヒト。 Grudsky、Sergei M. (2012)、Toeplitz Matrices、Asymptotic Linear Algebra、および Functional Analysis、Birkhäuser、ISBN 978-3-0348-8395-5
• Brent, RP (1999)、「構造化線形システムのための高速アルゴリズムの安定性」、Kailath, T.; Sayed, AH (編)、『構造付き行列のための高速で信頼性の高いアルゴリズム』、SIAM、pp.  103– 116、arXiv : 1005.0671、doi :10.1137/1.9781611971354.ch4、hdl : 1885/40746、ISBN 978-0-89871-431-9、S2CID  13905858
• Chan, RH-F.; Jin, X.-Q. (2007),反復テプリッツソルバー入門, SIAM , doi :10.1137/1.9780898718850, ISBN 978-0-89871-636-8
• Chandrasekeran, S.; Gu, M.; Sun, X.; Xia, J.; Zhu, J. (2007)、「Toeplitz線形方程式系のための超高速アルゴリズム」、SIAM Journal on Matrix Analysis and Applications、29 (4): 1247– 66、CiteSeerX  10.1.1.116.3297、doi :10.1137/040617200
• Chen, WW; Hurvich, CM; Lu, Y. (2006)「離散フーリエ変換の相関行列と長期記憶時系列に対する大規模テプリッツシステムの高速解について」アメリカ統計学会誌、101 (474): 812– 822、CiteSeerX  10.1.1.574.4394、doi :10.1198/016214505000001069、S2CID  55893963
• Hayes, Monson H. (1996)、統計的デジタル信号処理とモデリング、Wiley、ISBN 0-471-59431-8
• クリシュナ、H.; ワン、Y. (1993)、「スプリット・レビンソン・アルゴリズムは弱安定である」、SIAM Journal on Numerical Analysis、30 (5): 1498– 1508、doi :10.1137/0730078
• モナハン、JF（2011）、数値統計法、ケンブリッジ大学出版局、doi：10.1017/CBO9780511977176、ISBN 978-1-139-08211-2
• Mukherjee, Bishwa Nath; Maiti, Sadhan Samar (1988)「正定値テプリッツ行列のいくつかの性質とその応用について」（PDF） , Linear Algebra and Its Applications , 102 : 211– 240, doi : 10.1016/0024-3795(88)90326-6
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007)、『Numerical Recipes: The Art of Scientific Computing』（第3版）、ケンブリッジ大学出版局、ISBN 978-0-521-88068-8
• スチュワート、M.（2003）「数値安定性を向上させた超高速テプリッツソルバー」、SIAM Journal on Matrix Analysis and Applications、25（3）：669–693、doi：10.1137/S089547980241791X、S2CID  15717371
• Yang, Zai; Xie, Lihua; Stoica, Petre (2016)、「多次元超解像への応用を伴う多段テプリッツ行列のヴァンダーモンド分解」、IEEE Transactions on Information Theory、62 (6): 3685– 3701、arXiv : 1505.02510、doi :10.1109/TIT.2016.2553041、S2CID  6291005

さらに読む

• Bareiss, EH (1969)、「テプリッツ行列とベクトルテプリッツ行列を用いた線形方程式の数値解」、Numerische Mathematik、13 (5): 404– 424、doi :10.1007/BF02163269、S2CID  121761517
• Goldreich, O. ; Tal, A. (2018)、「ランダムテプリッツ行列の行列剛性」、Computational Complexity、27 (2): 305– 350、doi :10.1007/s00037-016-0144-9、S2CID  253641700
• Golub, GH ; van Loan, CF (1996)、『行列計算』、ジョンズ・ホプキンス大学出版局、§4.7—Toeplitzと関連システム、ISBN 0-8018-5413-X、OCLC  34515797
• Gray, RM (2005)、「Toeplitzと循環行列：レビュー」（PDF）、通信情報理論の基礎と動向、2（3）、Now Publishers：155– 239、doi：10.1561/0100000006
• Noor, F.; Morgera, SD (1992)、「任意の固有値集合からのエルミート・テプリッツ行列の構築」、IEEE Transactions on Signal Processing、40 (8): 2093– 4、Bibcode :1992ITSP...40.2093N、doi :10.1109/78.149978
• Pan, Victor Y. (2001), Structured Matrices and Polynomials: unified superfast algorithms , Birkhäuser , ISBN 978-0817642402
• Ye, Ke; Lim, Lek-Heng (2016)、「すべての行列はテプリッツ行列の積である」、計算数学の基礎、16 (3): 577– 598、arXiv : 1307.5132、doi :10.1007/s10208-015-9254-z、S2CID  254166943