Skip to main content
3 of 3
fixed Latex (uses of "\_")
Wolfgang
  • 13.4k
  • 5
  • 45
  • 102

Generalizing inequality relating Euclidean distance & Frobenius norm to Bregman divergences such as relative entropy & von Neumann divergence

Motivation- A Special Case

Supposing $A,B\in\mathbb{S}^{m\times m}$ are symmetric positive semi-definite (SPD) matrices and $\mathbf{x}\in\mathbb{R}^m$ is a unit vector where $\|\mathbf{x}\|=1$, we found that the squared Euclidean distance of two quadratic forms $\left(\mathbf{x}^\top A\mathbf{x}-\mathbf{x}^\top B\mathbf{x}\right)^2$ is bounded by the squared Frobenius norm of difference of the two matrices $\|A-B\|_F^2$.

Denoting the spectral decomposition of $A-B$ as $A-B=W\Phi W^\top$ where $\Phi=\mathrm{diag}\left(\phi_1,\phi_2,\ldots,\phi_m\right)$ is a diagonal matrix of eigenvalues, we have \begin{eqnarray} &&\left(\mathbf{x}^\top A\mathbf{x}-\mathbf{x}^\top B\mathbf{x}\right)^2 =\left(\mathbf{x}^\top(A-B)\mathbf{x}\right)^2 =\left(\mathbf{x}^\top W\Phi W^\top\mathbf{x}\right)^2\\\ =&&\left(\sum_i{x_{W,i}^2\phi_i}\right)^2 \leq\max_i{\phi_i^2}\leq\sum_i{\phi_i^2} =\|A-B\|_F^2 \end{eqnarray} where $W^\top\mathbf{x}=\mathbf{x}_W=\left[x_{W,1}\;x_{W,2}\;\ldots\;x_{W,m}\right]^\top$ and $\mathbf{x}_W^\top\mathbf{x}_W=\sum_i{x_{W,i}^2}=1$.

Therefore, for $\forall \mathbf{x}\in\mathbb{R}^m\;\mathrm{s.t.}\;\|\mathbf{x}\|=1$, we have $\left(\mathbf{x}^\top A\mathbf{x}-\mathbf{x}^\top B\mathbf{x}\right)^2\leq\|A-B\|_F^2$.

Question- Could this be generalized?

However, the squared Euclidean distance is a special case of Bregman divergence $$ D_\varphi(\mathbf{x},\mathbf{y})=\varphi(\mathbf{x})-\varphi(\mathbf{y})-\nabla\varphi(\mathbf{y})^\top(\mathbf{x}-\mathbf{y}) $$ where $\varphi$ is the convex seed function.

On the other hand, the squared Frobenius norm of difference of two matrices is a special case of Bregman matrix divergence $$ D_\phi(A,B)=\phi(A)-\phi(B)-\mathrm{tr}\left((\nabla\phi(B))^\top(A-B)\right) $$ where $\phi(A)=(\varphi\circ\lambda)(A)$ is a compound matrix function in which $\lambda$ is the function that lists the eigenvalues of $A$ and $\varphi$ is the convex seed function.

In the example above, the seed function is $\varphi(\mathbf{x})=\mathbf{x}^\top\mathbf{x}$ and we can rewrite the inequality as $$ D_\varphi\left(\mathbf{x}^\top A\mathbf{x},\mathbf{x}^\top B\mathbf{x}\right) \leq D_\phi(A,B) $$ where $\|\mathbf{x}\|=1$ and $\phi=\varphi\circ\lambda$. The function $\lambda$ lists the eigenvalues of the matrix argument.

With the property of Bregman matrix divergence, the inequality can also be written as \begin{eqnarray} D_\varphi\left(\mathbf{x}^\top\mathbf{V}\Lambda\mathbf{V}^\top\mathbf{x}, \mathbf{x}^\top\mathbf{U}\Theta\mathbf{U}^\top\mathbf{x}\right) &=&D_\varphi\left(\sum_i(\mathbf{v}_i^\top\mathbf{x})^2\lambda_i,\sum_j(\mathbf{u}_j^\top\mathbf{x})^2\theta_j\right)\\\ &\leq&\sum_i\sum_j{(\mathbf{v}_i^\top\mathbf{u}_j)^2D_\varphi(\lambda_i,\theta_j)} \end{eqnarray} where $A=V\Lambda V^\top,B=U\Theta B^\top$ are spectral decompositions and $\mathbf{v}_i,\mathbf{u}_j$ are columns of $V,U$ respectively.

My Question is: can this inequality be extended to general Bregman divergence and Bregman matrix divergence with different seed functions chosen?

Or under what condition such an inequality exists?

For example, if $\varphi(\mathbf{x})=\sum_i{x_i\log x_i-x_i}$,

then $D_\varphi$ is the relative entropy (KL-divergence) $$\mathrm{KL}(\mathbf{x},\mathbf{y})=\sum_i\left(x_i(\log x_i-\log y_i)-x_i+y_i\right),$$

and $D_\phi$ is the von Neumann divergence $$D_{vn}(A,B)=\mathrm{tr}\left(A\log A-A\log B-A+B\right).$$

In this case, does the following inequality holds for $\forall\mathbf{x}\in\mathbb{R}^m$ satisfying $\|\mathbf{x}\|=1$? $$ \mathrm{KL}\left(\mathbf{x}^\top A\mathbf{x},\mathbf{x}^\top B\mathbf{x}\right) \leq D_{vN}(A,B) $$

I did many experiments about this inequality about relative entropy and von Neumann divergence with random generalized SPD matrices using Matlab and it always holds. However, does it really hold?

Could anyone please give me some help for this question or recommend some relevant papers? Any suggestion will be appreciated. Thank you very much!

ppyang
  • 607
  • 8
  • 15