Walsh関数
概要
Walsh関数（Walsh functions）とは、整数 $n\ge0$ の 2 進表示 $n=\sum_i\alpha_i2^i$ に対し、Rademacher 関数の積 $w_n=\prod_ir_{i+1}^{\alpha_i}$ として $[0,1)$ 上に定める関数である。$(w_n)_{n\ge0}$ は $L^2(0,1)$ の正規直交基底であり、完全でない Rademacher 系に相異なる関数の積をすべて加えて完全にした系にあたる。最初の $2^m$ 個は長さ $2^{-m}$ の 2 進区間上の階段関数の空間を張り、その値の行列は Walsh–Hadamard 変換の行列の列を並べ替えたものになる。$2^m$ 項の部分和は 2 進区間ごとの平均に一致し、$1\le p< \infty$ なら $L^p$ で元の関数に収束する。
前提知識: Rademacher関数, Hilbert空間, Lp空間
Rademacher 関数の積で作る完全系
Rademacher関数 $r_1,r_2,\ldots$ は $L^2(0,1)$ の正規直交系であるが完全ではなく、$r_1r_2$ のような積がすべての $r_n$ に直交する。そこで有限個の $r_n$ の積をすべて集めた系を考える。これが Walsh 関数の系であり、次のことが成り立つ。
- $(w_n)_{n\ge0}$ は $L^2(0,1)$ の正規直交基底（完全正規直交系）である（thm-walsh-complete）。
- 最初の $2^m$ 個は、長さ $2^{-m}$ の 2 進区間の上で定数な関数の空間をちょうど張る。その値を並べた行列は、行列 $\bigl((-1)^{n\cdot k}\bigr)$（Walsh–Hadamard 変換の行列）の列を並べ替えたものである。
- $2^m$ 項までの部分和は、長さ $2^{-m}$ の 2 進区間ごとの平均をとる操作に一致する。このため $L^p$（$1\le p<\infty$）の関数の Walsh 展開は、$2^m$ 項ごとに区切った部分和が $L^p$ で収束する。
三角関数による Fourier 級数（Fourier級数）と同じ役割を、値が $\pm1$ だけの階段関数で果たす系である。この記事では実数値または複素数値の関数を扱い、$L^p(0,1)$ は Lebesgue 測度に関する空間とする。内積は $\langle f,g\rangle=\int_0^1f\bar g\,dt$ である。
定義
記号は Rademacher関数 の記事に合わせる。$r_n(t)=(-1)^{\lfloor2^nt\rfloor}$、$t$ の第 $j$ 桁を $t_j$（$j\ge1$）、2 進区間を $I_{m,k}=[k2^{-m},(k+1)2^{-m})$、各 $I_{m,k}$ の上で定数な関数の空間を $D_m$（次元 $2^m$）と書く。
整数 $n\ge0$ を 2 進表示して $n=\sum_{i\ge0}\alpha_i(n)2^i$（$\alpha_i(n)\in\{0,1\}$、有限個を除いて $0$）とする。$[0,1)$ 上の関数
$$
w_n:=\prod_{i\ge0}r_{i+1}^{\alpha_i(n)}
$$
を第 $n$ の Walsh 関数といい、$(w_n)_{n\ge0}$ を Walsh 系という。空の積は $1$ とするので $w_0=1$ である。
$n$ の第 $i$ 桁（最下位を第 $0$ 桁とする）が $1$ のとき $r_{i+1}$ を掛ける。添字が $1$ ずれていることに注意する。最初のいくつかは
$$
w_0=1,\quad w_1=r_1,\quad w_2=r_2,\quad w_3=r_1r_2,\quad w_4=r_3,\quad w_5=r_1r_3,\quad w_6=r_2r_3,\quad w_7=r_1r_2r_3
$$
である。一般に $w_{2^i}=r_{i+1}$ であり、$w_0=1=r_0$ なので、Rademacher 系 $(r_n)_{n\ge0}$ は Walsh 系の部分系である。Rademacher関数 の補題「桁による表示」の 1 により
$$
w_n(t)=(-1)^{\sum_{i\ge0}\alpha_i(n)\,t_{i+1}}
$$
と書ける。
$n,n'\ge0$ について $w_nw_{n'}=w_{n\oplus n'}$ である。ここで $n\oplus n'$ は、2 進表示の各桁の和を $2$ で割った余りを桁とする整数（排他的論理和）である。
$r_{i+1}^{\alpha_i(n)}r_{i+1}^{\alpha_i(n')}=r_{i+1}^{\alpha_i(n)+\alpha_i(n')}$ であり、$r_{i+1}^2=1$ なので、指数は $2$ で割った余りに置き換えてよい。それは $\alpha_i(n\oplus n')$ である。$\square$
したがって Walsh 系は掛け算で閉じた群をなし、$n\mapsto w_n$ は、$\oplus$ による群 $(\mathbb{Z}_{\ge0},\oplus)$ からの同型である。変数の側でも同じ構造がある。$t,s,u\in[0,1)$ の桁が、すべての $j\ge1$ で $u_j\equiv t_j+s_j\pmod2$ を満たすなら、上の表示から $w_n(u)=w_n(t)w_n(s)$ がすべての $n$ で成り立つ。つまり $w_n$ は、桁ごとの排他的論理和という「足し算」について指数関数のようにふるまう。三角関数系 $e^{2\pi int}$ が実数の足し算について $e^{2\pi in(t+s)}=e^{2\pi int}e^{2\pi ins}$ を満たすことに対応している。
正規直交性と完全性
$(w_n)_{n\ge0}$ は $L^2(0,1)$ の正規直交系である。
$w_n$ は実数値で $|w_n|=1$ なので $\|w_n\|_2=1$ である。$n\ge1$ なら $w_n$ は番号が $1$ 以上の相異なる Rademacher 関数 1 個以上の積なので、Rademacher関数 の命題「符号の組の測度」により $\int_0^1w_n=0$ である。$n\ne n'$ なら $n\oplus n'\ne0$ なので、prop-walsh-product により $\langle w_n,w_{n'}\rangle=\int_0^1w_{n\oplus n'}=0$ である。$\square$
$m\ge0$ とする。$\{w_n:0\le n<2^m\}$ は $D_m$ の基底であり、$L^2$ の内積について正規直交基底である。
$n<2^m$ なら $\alpha_i(n)=0$（$i\ge m$）なので、$w_n$ は $r_1,\ldots,r_m$ の積であり、Rademacher関数 の補題「桁による表示」の 3 により $D_m$ に属する。これら $2^m$ 個は thm-walsh-on により正規直交なので線形独立であり、$\dim D_m=2^m$ だから $D_m$ の基底である。$\square$
$(w_n)_{n\ge0}$ は $L^2(0,1)$ の完全正規直交系である。すなわち、すべての $f\in L^2(0,1)$ について
$$
f=\sum_{n=0}^\infty\langle f,w_n\rangle w_n\quad(L^2\text{ で収束}),\qquad \|f\|_2^2=\sum_{n=0}^\infty|\langle f,w_n\rangle|^2
$$
が成り立つ。
$(w_n)$ の有限一次結合全体を $W$ とする。lem-walsh-span により $W\supset D_m$ がすべての $m$ で成り立つので、$W\supset\bigcup_mD_m$ である。Rademacher関数 の補題「2進階段関数の稠密性」（$p=2$）により $\bigcup_mD_m$ は $L^2(0,1)$ で稠密なので、$W$ も稠密である。有限一次結合が稠密な正規直交系は完全であり、展開と Parseval の等式が成り立つ（Hilbert空間 の記事の定理「完全正規直交系の特徴づけとParsevalの等式」）。$\square$
$r_1r_2=w_3$ は Rademacher 系のすべてに直交するが、Walsh 系の中では $w_3$ 自身との内積が $1$ である。Rademacher 系に欠けていたものは、相異なる 2 個以上の Rademacher 関数の積であり、それをすべて補うと完全になる。
$f(t)=t$ とする。$n\ge1$ について $t_n=(1-r_n(t))/2$ なので、すべての $t\in[0,1)$ で
$$
t=\sum_{j\ge1}t_j2^{-j}=\frac12-\sum_{j\ge1}2^{-j-1}r_j(t)=\frac12w_0(t)-\sum_{j\ge1}2^{-j-1}w_{2^{j-1}}(t)
$$
であり、右辺の級数は一様に収束する。よって $\langle f,w_0\rangle=1/2$、$\langle f,w_{2^{j-1}}\rangle=-2^{-j-1}$ で、ほかの Walsh 係数はすべて $0$ である（一様収束する級数は $L^2$ でも収束するので、内積を項別にとってよい）。Parseval の等式を確かめると
$$
\frac14+\sum_{j\ge1}4^{-j-1}=\frac14+\frac1{12}=\frac13=\int_0^1t^2\,dt
$$
である。恒等関数は Rademacher 系だけで展開でき、2 個以上の積の項は現れない。一方、$1_{[0,1/2)}\cdot1_{[0,1/4)\cup[1/2,3/4)}=1_{[0,1/4)}=\frac14(1+r_1)(1+r_2)$ のように、指示関数の積からは積の項 $w_3=r_1r_2$ が現れる。
部分和と 2 進区間の平均
$f\in L^1(0,1)$ の Walsh 係数を $\hat f(n):=\int_0^1f(s)w_n(s)\,ds$、部分和を $S_Nf:=\sum_{n< N}\hat f(n)w_n$ とする。また、$I_{m,k}$ の上で値 $2^m\int_{I_{m,k}}f$ をとる関数を $E_mf\in D_m$ と書く（各 2 進区間での平均）。
- $f\in L^1(0,1)$ と $m\ge0$ について $S_{2^m}f=E_mf$ である。
- $1\le p<\infty$、$f\in L^p(0,1)$ なら $\|S_{2^m}f-f\|_p\to0$（$m\to\infty$）である。
1：$S_{2^m}f(t)=\int_0^1f(s)K_m(t,s)\,ds$、$K_m(t,s):=\sum_{n<2^m}w_n(t)w_n(s)$ である。$n< 2^m$ は桁の組 $(\alpha_0,\ldots,\alpha_{m-1})\in\{0,1\}^m$ と 1 対 1 に対応するので
$$
K_m(t,s)=\sum_{\alpha\in\{0,1\}^m}\prod_{i=0}^{m-1}(-1)^{\alpha_i(t_{i+1}+s_{i+1})}=\prod_{i=0}^{m-1}\bigl(1+(-1)^{t_{i+1}+s_{i+1}}\bigr)
$$
となる。右辺は、$t$ と $s$ の第 $1$ 桁から第 $m$ 桁がすべて一致するとき $2^m$、そうでなければ $0$ である。Rademacher関数 の補題「桁による表示」の 2 により、桁が一致することは $t$ と $s$ が同じ $I_{m,k}$ に属することと同値である。よって $t\in I_{m,k}$ のとき $S_{2^m}f(t)=2^m\int_{I_{m,k}}f=E_mf(t)$ である。
2：各 $I_{m,k}$ の上で、Hölder の不等式（Hölderの不等式）により $\bigl|2^m\int_{I_{m,k}}f\bigr|^p\le2^m\int_{I_{m,k}}|f|^p$ なので、$I_{m,k}$ について足して $\|E_mf\|_p\le\|f\|_p$ である。$\varepsilon>0$ について、Rademacher関数 の補題「2進階段関数の稠密性」により $\|f-g\|_p<\varepsilon$ となる $g\in D_{m_0}$ がある。$m\ge m_0$ なら $g\in D_m$ なので $E_mg=g$ であり、
$$
\|E_mf-f\|_p\le\|E_m(f-g)\|_p+\|g-f\|_p<2\varepsilon
$$
となる。1 と合わせて結論を得る。$\square$
部分和 $S_{2^m}$ は、Walsh 関数を使わずに書ける平均の操作 $E_m$ で表せる。これは Haar関数系 の最初の $2^m$ 項の部分和と同じ操作である（両者とも $D_m$ への直交射影である）。$N$ が $2$ のべきでないときの $S_Nf$ は、一般にはこのような平均の形にならない（$N=3$ の例が Haar関数系 の節「Walsh 関数系との比較」にある）。
Walsh–Hadamard 行列との関係
$D_m$ の元 $g$ は $2^m$ 個の値 $g_k:=g|_{I_{m,k}}$（$0\le k<2^m$）で決まる。$k=\sum_{j=0}^{m-1}\kappa_j(k)2^j$ と 2 進表示し、$k$ の桁の並びを逆にした数を $\bar k:=\sum_{j=0}^{m-1}\kappa_{m-1-j}(k)2^j$ と書く。$0\le n,k< 2^m$ について $n\cdot k:=\sum_{i=0}^{m-1}\alpha_i(n)\kappa_i(k)$ とおく。
$0\le n,k<2^m$ について、$w_n$ の $I_{m,k}$ の上の値は $(-1)^{n\cdot\bar k}$ である。したがって、$2^m$ 次の行列 $H_m:=\bigl((-1)^{n\cdot k}\bigr)_{n,k}$ の列を $k\mapsto\bar k$ で並べ替えたものが、行列 $\bigl(w_n|_{I_{m,k}}\bigr)_{n,k}$ である。
Rademacher関数 の補題「桁による表示」の 2 により、$t\in I_{m,k}$ の第 $j$ 桁 $t_j$（$1\le j\le m$）は $k$ の下から第 $m-j$ 桁 $\kappa_{m-j}(k)$ である。よって $t_{i+1}=\kappa_{m-1-i}(k)=\kappa_i(\bar k)$ であり、$w_n(t)=(-1)^{\sum_i\alpha_i(n)\kappa_i(\bar k)}=(-1)^{n\cdot\bar k}$ である。$\square$
$H_m$ は群 $(\mathbb{Z}/2\mathbb{Z})^m$ の上の離散 Fourier 変換の行列であり、$H_m^2=2^mI$ を満たす（離散Fourier変換 の例「Walsh–Hadamard 変換」）。prop-walsh-hadamard により、$g\in D_m$ の Walsh 係数は
$$
\hat g(n)=2^{-m}\sum_{k< 2^m}(-1)^{n\cdot\bar k}g_k
$$
であり、値の列 $(g_{\bar k})_k$ の Walsh–Hadamard 変換を $2^m$ で割ったものになる。Walsh 系は、$L^2(0,1)$ の関数の展開と、有限群 $(\mathbb{Z}/2\mathbb{Z})^m$ の上の離散 Fourier 変換とを、段 $m$ ごとに結びつける。
反例の表
thm-walsh-on・thm-walsh-complete・thm-walsh-partial の仮定を 1 つずつ外す。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 2 個以上の積を含むこと（Rademacher 系だけにする） | $f=r_1r_2=w_3$ | 展開 $f=\sum_n\langle f,r_n\rangle r_n$（完全性） |
| 添字のずれ（$r_{i+1}$ の代わりに $r_i$ を掛ける） | $w'_n:=\prod_ir_i^{\alpha_i(n)}$ で $w'_0=w'_1=1$ | 正規直交性 |
| $p< \infty$（$p=\infty$ にする） | $f=1_{[0,1/3)}\in L^\infty(0,1)$ | $\Vert S_{2^m}f-f\Vert_\infty\to0$ |
- Rademacher関数 の定理「Rademacher系の正規直交性と不完全性」の 2 により $\langle w_3,r_n\rangle=0$（すべての $n$）なので右辺は $0$ であるが、$f\ne0$ である。
- $w'_1=r_0=1=w'_0$ なので、異なる番号の元が一致し、$\langle w'_0,w'_1\rangle=1$ である。
- $1/3$ は 2 進有理数でないので、$1/3$ を含む $I_{m,k}$ は $[k2^{-m},1/3)$ と $[1/3,(k+1)2^{-m})$ に正の長さで分かれ、$f$ はそれぞれで $1$ と $0$ をとる。$D_m$ の元はこの区間で定数 $c$ なので、$f$ との差の本質的上限は $\max(|1-c|,|c|)$ 以上であり、これは $1/2$ 以上である。thm-walsh-partial の 1 により $S_{2^m}f\in D_m$ なので、$\Vert S_{2^m}f-f\Vert_\infty\ge1/2$ がすべての $m$ で成り立つ。
文献
Walsh 系の定義（$n=\sum_i\alpha_i2^i$ に対し $w_n=\prod_ir_{i+1}^{\alpha_i}$）と、それが $L^2(0,1)$ の正規直交基底であること、Rademacher 系がその部分系であることを示す演習は Bre11 Exercise 5.32（pp. 155–156）にある。同書 Chapter 5 の Comments の 4（p. 146）は、階段関数からなる $L^2(0,1)$ の基底として Haar 基底と Walsh 基底を挙げている。この記事の証明は記事内で完結させた。
関連項目
- 前提: Rademacher関数, Hilbert空間, Lp空間
- 比較: Haar関数系, Fourier級数, 正規直交基底
- 応用: 離散Fourier変換, Schauder基底
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
