Is it possible to extend this inequality about Euclidean distance &Frobenius norm to more general Bregman divergence such as relative entropy & von Neumann divergence? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T22:33:24Z http://mathoverflow.net/feeds/question/93149 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/93149/is-it-possible-to-extend-this-inequality-about-euclidean-distance-frobenius-norm Is it possible to extend this inequality about Euclidean distance &Frobenius norm to more general Bregman divergence such as relative entropy & von Neumann divergence? ppyang 2012-04-04T17:40:44Z 2012-04-18T05:44:09Z <h2>Motivation- A Special Case</h2> <p>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 <em>squared Euclidean distance</em> of two quadratic forms $\left(\mathbf{x}^\top A\mathbf{x}-\mathbf{x}^\top B\mathbf{x}\right)^2$ is bounded by the <em>squared Frobenius norm of difference</em> of the two matrices $\|A-B\|_F^2$.</p> <p>Denoting the <em>spectral decomposition</em> 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} &amp;&amp;\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\\ =&amp;&amp;\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$.</p> <p>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$.</p> <h2>Question- Could this be generalized?</h2> <p>However, the <em>squared Euclidean distance</em> is a special case of <em>Bregman divergence</em> $$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 <em>convex seed function</em>.</p> <p>On the other hand, the <em>squared Frobenius norm of difference</em> of two matrices is a special case of <em>Bregman matrix divergence</em> $$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 <em>convex seed function</em>.</p> <p>In the example above, the seed function is $\varphi(\mathbf{x})=\mathbf{x}^\top\mathbf{x}$ and <strong>we can rewrite the inequality as</strong> $$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.</p> <p>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) &amp;=&amp;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)\\ &amp;\leq&amp;\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.</p> <p>My Question is: <strong>can this inequality be extended to general Bregman divergence and Bregman matrix divergence with different seed functions chosen?</strong></p> <p>Or <strong>under what condition such an inequality exists?</strong></p> <p>For example, if $\varphi(\mathbf{x})=\sum_i{x_i\log x_i-x_i}$,</p> <p>then $D_\varphi$ is the <em>relative entropy (KL-divergence)</em> $$\mathrm{KL}(\mathbf{x},\mathbf{y})=\sum_i\left(x_i(\log x_i-\log y_i)-x_i+y_i\right),$$</p> <p>and $D_\phi$ is the <em>von Neumann divergence</em> $$D_{vn}(A,B)=\mathrm{tr}\left(A\log A-A\log B-A+B\right).$$</p> <p>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)$$</p> <p>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?</p> <p>Could anyone please give me some help for this question or recommend some relevant papers? Any suggestion will be appreciated. Thank you very much!</p> http://mathoverflow.net/questions/93149/is-it-possible-to-extend-this-inequality-about-euclidean-distance-frobenius-norm/94306#94306 Answer by ppyang for Is it possible to extend this inequality about Euclidean distance &Frobenius norm to more general Bregman divergence such as relative entropy & von Neumann divergence? ppyang 2012-04-17T17:11:05Z 2012-04-18T05:44:09Z <p>I found a proof of this problem for the case of $\varphi(x)=\sum_i{x_i\log x_i-x_i}$. If you find there is anything mistake in the proof, please let me know. Thank you!</p> <p>The case of $\varphi(x)=\sum_i{x_i\log x_i-x_i}$ can be proved with the method similar to Lindblad, <em>Completely positive maps and entropy inequalities</em>, 1975 and Lindblad, <em>Expectations and entropy inequalities for finite quantum systems</em>, 1974. The inequality can be strengthened as $$\sum_i{\mathrm{KL}\left(\mathbf{x}_i^\top A\mathbf{x}_i,\mathbf{x}_i^\top B\mathbf{x}_i\right)}\leq D_{vN}\left(A,B\right)$$</p> <p>Actually, a very similar result has been proposed in some papers about quantum information theory, such as the two papers referred above. The referred result is that for any trace preserving map $\Phi$, given by $\Phi(A)=\sum_{i=1}^n{V_iAV_i^\top}$ and $\sum_{i=1}^n{V_i^\top V_i}=1$, we have that $\mathrm{tr}\left(\Phi(A),\Phi(B)\right)\leq D_\phi(A,B)$, where $A,B$ are both <em>density operators</em> which are Hermitian positive definite matrices satisfying $\mathrm{tr}A=\mathrm{tr}B=1$ and $\varphi(x)=x\log x$.</p> <p>We found that if the trace constraints $\mathrm{tr}A=\mathrm{tr}B=1$ are dropped and $\varphi(x)=x\log x$ is replaced with $\varphi(x)=x\log x-x$, the inequality still holds.</p> <p>The proof is outlined as following:</p> <ol> <li><p>The von Neumann divergence has the following additivity property with Kronecker product: $$D_{vN}(A\otimes P,B\otimes P)=D_{vN}(A,B)\cdot\mathrm{tr}P$$</p></li> <li><p>Using the joint convexity and the additivity, we can prove that the von Neumann divergence has the monotonicity with partial trace as \begin{equation*} \begin{split} D_{vN}(\mathrm{tr}_2(A),\mathrm{tr}_2(B)) =&amp;D_{vN}\left(\mathrm{tr}_2(A)\otimes\frac{\mathbf{I}_2}{m}, \mathrm{tr}_2(B)\otimes\frac{\mathbf{I}_2}{m}\right) /\mathrm{tr}\left(\frac{\mathbf{I}_2}{m}\right)\\ =&amp;D_{vN}\left(\sum_{j=1}^N{p_jW_jAW_j^+},\sum_{j=1}^N{p_jW_jBW_j^+}\right)\\ \leq&amp;\sum_{j=1}^{N}{p_jD_{vN}\left(W_jAW_j^+,W_jBW_j^+\right)}\\ =&amp;D_{vN}(A,B)\end{split} \end{equation*}</p></li> <li><p>For any trace preserving map $\Phi$, given by $\Phi(A)=\sum_{i=1}^n{V_iAV_i^\top}$ and $\sum_{i=1}^n{V_i^\top V_i}=1$, it can be represented as a <strong>unitary operation+partial tracing</strong>. Therefore, we have that \begin{equation*} \begin{split} D_{vN}\left(\Phi(A),\Phi(B)\right) =&amp;D_{vN}\left(\mathrm{tr}_2(W(A\otimes\mathbf{s}\mathbf{s}^\top)W^\top), \mathrm{tr}_2(W(B\otimes\mathbf{s}\mathbf{s}^\top)W^\top)\right)\\ \leq&amp;D_{vN}\left(W(A\otimes\mathbf{s}\mathbf{s}^\top)W^\top, W(B\otimes\mathbf{s}\mathbf{s}^\top)W^\top\right)\\ =&amp;D_{vN}\left(A,B\right) \end{split} \end{equation*}</p></li> <li><p>Then the sum of relative entropy of the quadratic forms could be represented as matrix divergence and bounded. \begin{equation*} \begin{split} \sum_i{\mathrm{KL}\left(\mathbf{x}_i^\top A\mathbf{x}_i,\mathbf{x}_i^\top B\mathbf{x}_i\right)} =&amp;\sum_{i,j}{(\mathbf{x}_i^\top\mathbf{x}_j)^2 \mathrm{KL}(\mathbf{x}_i^\top A\mathbf{x}_i,\mathbf{x}_j^\top B\mathbf{x}_j)}\\ =&amp;D_{vN}(\sum_i{X_iAX_i^\top},\sum_i{X_iBX_i^\top})\\ \leq&amp;D_{vN}\left(A,B\right) \end{split} \end{equation*} where $X_i=\mathbf{x}_i\mathbf{x}_i^\top$.</p></li> </ol> <p>If there is any mistake in the proof, please let me know. Any other suggestions are also welcomed. Thank you very much!</p>