Skip to main content
added 13 characters in body
Source Link
Artemy
  • 695
  • 3
  • 16

It is known that, in general, a monotonic divergence measure does not have to a monotonically-increasing function of an $f$-divergence. See discussion after Definition 1 (and footnote 3) in

  • Polyanskiy and Verdú, Arimoto Channel Coding Converse and Rényi Divergence, 48th Annual Allerton Conference on Communication, Control, and Computing (Allerton), 2010.

The situation is different for divergence measures that are decomposable, meaning they can be written as \begin{align} D(p||q) = \sum_{i=1}^n f(p_i, q_i) \end{align} where $n$ is the size of the alphabet. It is known that for binary alphabet, $n=2$, there are divergence measures that are monotonic and decomposable but are not an $f$-divergencedivergences (nor a function functions of an $f$-divergencedivergences); see Lemma 1 in:

  • J. Jiao, T. A. Courtade, A. No, K. Venkat, and T. Weissman, "Information measures: the curious case of the binary alphabet," IEEE Trans. Inform. Theory, 2014.

For $n\ge 3$, any monotonic and decomposable divergence must be an $f$-divergence; see the above paper by Jiao et al. and Theorem 1 in

  • Pardo and Vajda, About Distances of Discrete Distributions Satisfying the Data Processing Theorem of Information Theory, IEEE Trans on Information Theory, 1997.

(Importantly, Pardo and Vajda do not mention that the proof of Theorem 1 only works for $n\ge 3$,; this was first pointed out in Jiao et al. 2014.)

It is known that, in general, a monotonic divergence measure does not have to a monotonically-increasing function of an $f$-divergence. See discussion after Definition 1 (and footnote 3) in

  • Polyanskiy and Verdú, Arimoto Channel Coding Converse and Rényi Divergence, 48th Annual Allerton Conference on Communication, Control, and Computing (Allerton), 2010.

The situation is different for divergence measures that decomposable, meaning they can be written as \begin{align} D(p||q) = \sum_{i=1}^n f(p_i, q_i) \end{align} where $n$ is the size of the alphabet. It is known that for binary alphabet, $n=2$, there are divergence measures that are monotonic and decomposable but not an $f$-divergence (nor a function of an $f$-divergence); see Lemma 1 in:

  • J. Jiao, T. A. Courtade, A. No, K. Venkat, and T. Weissman, "Information measures: the curious case of the binary alphabet," IEEE Trans. Inform. Theory, 2014.

For $n\ge 3$, any monotonic and decomposable divergence must be an $f$-divergence; see the above paper and Theorem 1 in

  • Pardo and Vajda, About Distances of Discrete Distributions Satisfying the Data Processing Theorem of Information Theory, IEEE Trans on Information Theory, 1997.

(Importantly, Pardo and Vajda do not mention that the proof of Theorem 1 only works for $n\ge 3$, this was first pointed out in Jiao et al. 2014.)

It is known that, in general, a monotonic divergence measure does not have to a monotonically-increasing function of an $f$-divergence. See discussion after Definition 1 (and footnote 3) in

  • Polyanskiy and Verdú, Arimoto Channel Coding Converse and Rényi Divergence, 48th Annual Allerton Conference on Communication, Control, and Computing (Allerton), 2010.

The situation is different for divergence measures that are decomposable, meaning they can be written as \begin{align} D(p||q) = \sum_{i=1}^n f(p_i, q_i) \end{align} where $n$ is the size of the alphabet. It is known that for binary alphabet, $n=2$, there are divergence measures that are monotonic and decomposable but are not $f$-divergences (nor functions of $f$-divergences); see Lemma 1 in:

  • J. Jiao, T. A. Courtade, A. No, K. Venkat, and T. Weissman, "Information measures: the curious case of the binary alphabet," IEEE Trans. Inform. Theory, 2014.

For $n\ge 3$, any monotonic and decomposable divergence must be an $f$-divergence; see the above paper by Jiao et al. and Theorem 1 in

  • Pardo and Vajda, About Distances of Discrete Distributions Satisfying the Data Processing Theorem of Information Theory, IEEE Trans on Information Theory, 1997.

(Importantly, Pardo and Vajda do not mention that the proof of Theorem 1 only works for $n\ge 3$; this was first pointed out in Jiao et al.)

Source Link
Artemy
  • 695
  • 3
  • 16

It is known that, in general, a monotonic divergence measure does not have to a monotonically-increasing function of an $f$-divergence. See discussion after Definition 1 (and footnote 3) in

  • Polyanskiy and Verdú, Arimoto Channel Coding Converse and Rényi Divergence, 48th Annual Allerton Conference on Communication, Control, and Computing (Allerton), 2010.

The situation is different for divergence measures that decomposable, meaning they can be written as \begin{align} D(p||q) = \sum_{i=1}^n f(p_i, q_i) \end{align} where $n$ is the size of the alphabet. It is known that for binary alphabet, $n=2$, there are divergence measures that are monotonic and decomposable but not an $f$-divergence (nor a function of an $f$-divergence); see Lemma 1 in:

  • J. Jiao, T. A. Courtade, A. No, K. Venkat, and T. Weissman, "Information measures: the curious case of the binary alphabet," IEEE Trans. Inform. Theory, 2014.

For $n\ge 3$, any monotonic and decomposable divergence must be an $f$-divergence; see the above paper and Theorem 1 in

  • Pardo and Vajda, About Distances of Discrete Distributions Satisfying the Data Processing Theorem of Information Theory, IEEE Trans on Information Theory, 1997.

(Importantly, Pardo and Vajda do not mention that the proof of Theorem 1 only works for $n\ge 3$, this was first pointed out in Jiao et al. 2014.)