6
$\begingroup$

In the paper Faster Algorithms for Max-Product Message Passing by McAuley and Caetano (see e.g. here or here), several statements are made which seem mathematically questionable to me.

For completeness sake some of the relevant quotes are included below, but my main point is this:

To the best of my knowledge, 'tropical' (at least in 'tropical geometry') refers to either the max-plus algebra or the min-plus algebra, such that tropical matrix multiplication corresponds to the shortest-path problem, and, e.g. Dijkstra's or the Floyd-Warshall algorithm

The authors of the paper seem to implicitly be stating that results in the max-plus, min-plus algebras are equivalent to results in the max-product and min-product algebras.

Question: Why should we expect that to be true? I.e., is there not any "fundamental" distinction between min-plus, max-plus, min-product, and max-product algebras? And if not, why not?

Sure, we can derive all four from the min-plus algebra using multiplication by -1 or "tropical exponentiation" (i.e. iterated addition i.e. multiplication), but why should these operations preserve the essential structure of the min-plus algebra? What is the obvious point I am missing?

Thus our results certainly apply to the max-sum and min-sum (‘tropical’) semirings (as well as max-product and min-product, assuming non-negative potentials)...

... message-passing becomes some variant of matrix multiplication. Finally we shall explore other applications besides message-passing that make use of tropical matrix multiplication as a subroutine, such all-pairs shortest-path problems.

our algorithm is closely related to a well-studied problem known as ‘tropical matrix multiplication’ (Kerr, 1970).

the problem of matrix-matrix multiplication in the max-product semiring (often referred to as ‘tropical matrix multiplication’, ‘funny matrix multiplication’, or simply ‘maxproduct matrix multiplication’)

(Note: I'm not sure if this is the right place to ask this question. If it is not, please tell me, so the question can be deleted. Please don't hesitate to suggest a better place to ask it either.)

EDIT: Qiaochu Yuan's correct answer is also corroborated by the paper, The Generalized Distributive Law, by Aji and McEliece (2000), which states on p.3 that all four of the above commutative semirings are isomorphic to one another, using (essentially) the same isomorphisms as stated by Qiaochu Yuan in his correct answer.

Improve this question
$\endgroup$
2
  • 6
    $\begingroup$ Aren't all four of them just isomorphic as semirings? The maps you described are semiring isomorphisms, right? $\endgroup$
    – Qiaochu Yuan
    Commented Dec 5, 2017 at 1:33
  • $\begingroup$ @QiaochuYuan I don't know. $(*-1): \mathbb{N} \to -\mathbb{N}$ is probably a semiring isomorphism (at least it's bijective), then $(\min, +)$ on $-\mathbb{N}$ seemingly should also be isomorphic to $(\max, +)$ on $\mathbb{N}$, so in total one might get a semiring isomorphism between $(\min, +)$ and $(\max, +)$ on $\mathbb{N}$. What would be the explicit isomorphism between $(\min, +)$ and $(\min, \times)$ or $(\max, \times)$? (This is the biggest sticking point for me.) Is it just somehow applying the fact that two positive integers are smaller than both their sum and their product? $\endgroup$
    – Chill2Macht
    Commented Dec 5, 2017 at 2:15

1 Answer 1

Reset to default
17
$\begingroup$

Consider the following four semirings, listed in the order underlying set, addition, additive identity, multiplication, multiplicative identity:

  1. $A = (\mathbb{R} \cup \{ \infty \}, \text{min}, \infty, +, 0)$
  2. $B = (\mathbb{R} \cup \{ - \infty \}, \text{max}, -\infty, +, 0)$
  3. $C = (\mathbb{R}_{> 0} \cup \{ \infty \}, \text{min}, \infty, \times, 1)$
  4. $D = (\mathbb{R}_{\ge 0}, \text{max}, 0, \times, 1)$.

These semirings are all isomorphic. Explicit isomorphisms are as follows:

$$A \ni a \mapsto -a \in B$$ $$A \ni a \mapsto \exp(a) \in C$$ $$C \ni c \mapsto \frac{1}{c} \in D.$$

Is it clear now?

Improve this answer
$\endgroup$
1
  • $\begingroup$ It's clear now, thank you. Then I suppose we can conclude that an algorithm of a given complexity for one of the semirings "induces" an algorithm of the same complexity for an isomorphic semiring as long as the isomorphism can be calculated in constant time. (But anyway that's outside of the scope of the question as framed above.) $\endgroup$
    – Chill2Macht
    Commented Dec 5, 2017 at 14:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .