von Neumannのtrace不等式

abstract　Frobeniusノルムの場合のEckart-Youngの定理に対して別証を与えるなど、さまざまな応用が知られているvon Neumannのtrace不等式を紹介し、その証明を与えます。

1　Introduction

意外なことに、行列の特異値とtraceとの間には面白い関係があります。行列 $${A}$$ が $${n}$$ 個の特異値を持つとき、これを大きい順に $${\sigma_{1}(A)\geq\cdots\geq\sigma_n(A)}$$ と表すことにします。行列 $${B}$$ に対しても同様とします。このとき、

$$
|\mathrm{tr}(AB^T)| \leq\displaystyle \sum_{i=1}^{n}\sigma_{i}(A)\sigma_{i}(B)
$$

という関係が成り立つのです。1937年にvon Neumann [vN] が発表したため、von Neumannのtrace不等式とよばれています。

von Neumannのtrace不等式の証明はいくつか知られており、現在の最もよく知られている証明は二重確率行列の性質を利用した1975年のMinsky [M] によるものです。このnoteでは、Minskyによるエレガントな証明を紹介します。

2　von Neumannのtrace不等式の言い換え

von Neumannのtrace不等式を証明するときには、掲げた不等式をそのまま示すのではなく、事前に左辺を式変形しておくと便利です。技術的ではありますが、この言い換えを挟んでおくことで証明しやすくなります。

行列 $${A}$$ の特異値分解を、対角成分が $${\sigma_1(A),\cdots,\sigma_n(A)}$$ の順に並び、非対角要素が $${0}$$ になっているような行列 $${D_A}$$ を用いて $${A=U_AD_AV_A^T}$$ と取ります。同様にして、行列 $${B}$$ の特異値分解を $${B=U_VD_BV_B^T}$$ と取ります。このとき、von Neumannのtrace不等式の左辺は次のように式変形できます。

$$
\mathrm{tr}(AB^T) = \mathrm{tr}(U_AD_AV_A^TV_BD_B^TU_B^T) = \mathrm{tr}(U_B^TU_AD_AV_B^TV_BD_B^T)
$$

ここで $${U=U_B^TU_A=(u_{ij})}$$、$${V=V_B^TV_A=(v_{ij})}$$ と表すことにします。このとき、次の二つの事実が従います。一つめは行列 $${U, V}$$ は直交行列であるということです。二つめは、von Neumannのtrace不等式を以下のように式変形できるということです。

$$
\mathrm{tr}(AB^T) = \mathrm{tr}(UD_AV^TD_B^T) = \displaystyle\sum_{i,j=1}^{n}u_{ij}v_{ij}\sigma_{j}(A)\sigma_{i}(B)
$$

Remark　ここから凸結合の概念を援用して、直接的にブロック行列の掛け算を計算しながらvon Neumannのtrace不等式を証明する方法もあります。

3　二重確率行列とその性質

定義　正方行列が以下の二条件を満たすとき、二重確率行列（doubly stochastic matrix）といいます。
(1)　すべての要素が $${0}$$ 以上の値である。
(2)　行方向・列方向の和が必ず $${1}$$ である。

例えば以下のような行列は二重確率行列です。

$$
D=\begin{pmatrix}
0.1&0.5&0.4\\
0.3&0.2&0.5\\
0.6&0.3&0.1
\end{pmatrix}
$$

二重確率行列は直交行列から作ることができます。直交行列 $${U=(u_{ij})}$$ は

$$
\displaystyle\sum_{i=1}^{n}u_{ij}^2=1,\quad \displaystyle\sum_{j=1}^{n}u_{ij}^2=1
$$

が成り立つので、$${P=(u_{ij}^2)}$$ は二重確率行列です。また、二重確率行列には次の事実が成り立ちます。これらの事実は、von Neumannのtrace不等式を証明するときに重要な役割を果たします。

補題　$${D=(d_{ij})}$$ を二重確率行列とします。$${0}$$ 以上の実数列 $${x_1\geq\cdots\geq x_n}$$ と $${y_1\geq\cdots\geq y_n}$$ に対して、以下の不等式が成立します。

$$
\displaystyle\sum_{i,j=1}^{n}d_{ij}x_iy_j \leq \sum_{i=1}^{n}x_iy_i
$$

証明　実数列の定義の仕方から、次のような $${0}$$ 以上の実数列 $${\alpha_1,\cdots,\alpha_n}$$, $${\beta_1,\cdots,\beta_n}$$ を取ることができます。

$$
x_i = \displaystyle\sum_{i\leq k\leq n}\alpha_k,\quad y_i = \displaystyle\sum_{i\leq k\leq n}\beta_k
$$

この事実を用いて、不等式の右辺と左辺の差を $${\alpha_i,\beta_i}$$ を用いて表してみましょう。以下、$${\delta_{ij}}$$ はクロネッカーのデルタを意味します。また、$${\mathbb{1}[A]}$$ は条件 $${A}$$ が正しい場合に $${1}$$ を、そうでない場合には $${0}$$ を返す関数です。

$$
\begin{align*}
\sum_{i=1}^{n}x_iy_i - \sum_{i,j=1}^{n}d_{ij}x_iy_j
&= \sum_{i,j=1}^{n}(\delta_{ij}-d_{ij})x_iy_j\\
&= \sum_{i,j=1}^{n}\left\{(\delta_{ij}-d_{ij})\sum_{i\leq k\leq n}\alpha_k\sum_{j\leq l\leq n}\beta_l\right\}\\
&=  \sum_{i,j,k,l=1}^{n}(\delta_{ij}-d_{ij})\alpha_k\mathbb{1}[i\leq k]\beta_l\mathbb{1}[j\leq l]\\
&= \sum_{k,l=1}^{n}\left\{\alpha_k\beta_l\sum_{\substack{1\leq i \leq k\\1\leq j\leq l}}(\delta_{ij}-d_{ij})\right\}\\
\end{align*}
$$

あとは、$${k,l}$$ を固定した時の各項が $${0}$$ 以上の実数になっていることを示せば十分です。$${\alpha_k,\beta_l}$$ はもともと $${0}$$ 以上の実数でした。さらに、$${k\geq l}$$ を仮定すると

$$
\begin{align*}
\sum_{\substack{1\leq i \leq k\\1\leq j\leq l}}(\delta_{ij}-d_{ij})&= \sum_{1\leq j\leq l}\delta_{jj}-\sum_{\substack{1\leq i \leq k\\1\leq j\leq l}}d_{ij}\\
&\geq  \sum_{1\leq j\leq l}\delta_{jj}-\sum_{\substack{1\leq i \leq n\\1\leq j\leq l}}d_{ij}\\
&= l - l\\
&= 0
\end{align*}
$$

が成り立ちます。これは $${k\leq l}$$ の場合も同様です。以上の議論から、不等式の右辺と左辺の差は $${0}$$ 以上の実数の和で表されることがわかり、不等式が成り立つことが従います。■

4　von Neumannのtrace不等式の証明

実は、von Neumannのtrace不等式の左辺を、第3章で紹介した二重確率行列の補題の左辺の形に帰着させることができます。第2章の結果と相加相乗の不等式

$$
\displaystyle |u_{ij}v_{ij}| \leq \frac{1}{2}(u_{ij}^2+v_{ij}^2)
$$

から、von Neumannのtrace不等式の左辺に対して以下のような不等式評価が従います。

$$
\begin{align*}
|\mathrm{tr}(AB^T)| &\leq  \sum_{i,j=1}^{n}|u_{ij}v_{ij}|\sigma_{j}(A)\sigma_{i}(B)\\
&\leq \frac{1}{2}\sum_{i,j=1}^{n}u_{ij}^2\sigma_{j}(A)\sigma_{i}(B) + \frac{1}{2}\sum_{i,j=1}^{n}v_{ij}^2\sigma_{j}(A)\sigma_{i}(B)
\end{align*}
$$

ここで $${U,V}$$ は直交行列だったので、行列 $${(|u_{ij}|^2),(|v_{ij}|^2)}$$ は二重確率行列です。二重確率行列の補題から

$$
\begin{align*}
\sum_{i,j=1}^{n}u_{ij}^2\sigma_{j}(A)\sigma_{i}(B) &\leq \sum_{i=1}^{n}\sigma_{i}(A)\sigma_{i}(B)
\end{align*}
$$

が成り立ちます。これは $${\displaystyle\sum_{i,j=1}^{n}v_{ij}^2\sigma_{j}(A)\sigma_{i}(B)}$$ に対しても同様です。以上の議論から、von Neumannのtrace不等式

$$
|\mathrm{tr}(AB^T)| \leq\displaystyle \sum_{i=1}^{n}\sigma_{i}(A)\sigma_{i}(B)
$$

が従います。

Acknowledgement

これは、すうがくぶんか Advent Calendar 2023のために書いたnoteです。議論に付き合ってくださった、すうがくぶんかの會澤先生、井汲先生、伊集院先生、齋藤先生に感謝申し上げます。

References

[M]　Mirsky, L. (1975). A trace inequality of John von Neumann. Monatshefte für mathematik, 79(4), 303-306.
[vN]　von Neumann, J. (1937). Some matrix-inequalities and metrication of matrix-space. Tomsk Univ. Rev. 1, 286-300.