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

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$$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}\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!

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!

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!

Added the information theory tag so that others have easier time finding this question. Was also forced to reduce title to <=150 chars.
Link

Is it possible to extend this Generalizing inequality aboutrelating Euclidean distance &Frobenius& Frobenius norm to more general Bregman divergencedivergences such as relative entropy & von Neumann divergence?

Source Link
ppyang
  • 607
  • 8
  • 15

Is it possible to extend this inequality about Euclidean distance &Frobenius norm to more general Bregman divergence 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!