Efficient computation of "discrete infimal convolution" - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T06:52:18Z http://mathoverflow.net/feeds/question/121517 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/121517/efficient-computation-of-discrete-infimal-convolution Efficient computation of "discrete infimal convolution" Noah Stein 2013-02-11T18:53:51Z 2013-02-18T15:03:40Z <p>This question arises from an application to graphical models in probability theory, but I have abstracted that part out so only algebra remains. Let $\mathbb{R}$ denote standard field of real numbers and $\mathcal{R} = (\mathbb{R}\cup\{\infty\},\min,+)$ the tropical semiring. Let $\mathbb{Z}_n$ denote the cyclic group of order $n$.</p> <p>Elements of the group ring $\mathbb{R}\mathbb{Z}_n$ are tuples $(x_0,\ldots,x_{n-1})$ and multiplication of these corresponds to discrete cyclic convolution. The Fast Fourier Transform gives an embedding $\mathbb{R}\mathbb{Z}_n\to\mathbb{C}^n$ (with elementwise sum and product). The FFT and its inverse can be computed in $O(n\log n)$ arithmetic operations, so elements of $\mathbb{R}\mathbb{Z}_n$ can be multiplied in $O(n\log n)$ arithmetic operations.</p> <p>Define the group semiring $\mathcal{R}\mathbb{Z}_n$ in an analogous way. The product of $x = (x_0,\ldots, x_{n-1})$ and $y = (y_0,\ldots,y_{n-1})$ in this semiring is given by $(x\cdot y)_k = \min _{j \in \mathbb{Z}_n} (x_j + y_{k-j})$. This operation could perhaps be called "discrete cyclic infimal convolution" by analogy with <a href="http://en.wikipedia.org/wiki/Convex_conjugate#Infimal_convolution" rel="nofollow">the notion of infimal convolution in convex analysis</a>. I'm not sure whether there is a more standard name -- this one does not pop up in quick google searches.</p> <p>The naive way of computing a discrete infimal convolution uses $O(n^2)$ operations, just as the naive method for computing a standard cyclic convolution. <strong>My question is: is there a way to compute this "discrete cyclic infimal convolution" in $O(n\log n)$ arithmetic operations?</strong></p> <p>In convex analysis, there is an analog of the Fourier transform which turns infimal convolution into pointwise addition: the <a href="http://en.wikipedia.org/wiki/Convex_conjugate" rel="nofollow">convex conjugate (or Fenchel or Legendre transformation)</a>. However, this operation only behaves nicely for convex functions, so it is not clear to me how one would translate it to an equivalent tool for $\mathcal{R}\mathbb{Z}_n$, but perhaps there is something there.</p> <p>I would be interested in answers to the question regardless of whether they go through some analog of the Fourier transform. Also, I don't mind various restrictions such as making $n$ a power of $2$, replacing $\mathbb{R}$ with $\mathbb{Q}$, removing $\infty$ from the definition of the semiring, etc. Really anything on this theme would be helpful. Also any suggestions for better tags would be appreciated; perhaps this is a well-studied area I'm not aware of.</p> http://mathoverflow.net/questions/121517/efficient-computation-of-discrete-infimal-convolution/121692#121692 Answer by Ngoc Mai Tran for Efficient computation of "discrete infimal convolution" Ngoc Mai Tran 2013-02-13T09:17:56Z 2013-02-13T09:17:56Z <p>Hi Noah,</p> <p>Nice question! I tried thinking of the discrete fourier transform as a change of basis to the eigenbasis of a circulant matrix, but this did not generalize well tropically. </p> <p>However, there are work on generalized Legendre-Fenchel transform to non convex/concave functions, including discrete ones, which preserves the convolution-to-sum property. See, for example</p> <p><em>Characterization of a simple communication network using legendre transform</em></p> <p>or </p> <p><em>Slope transforms: theory and application to nonlinear signal processing</em></p> <p>As to fast computation of the discrete Legendre-Fenchel transform, see Lucet's thesis:</p> <p><em>La transformee de legendre-fenchel etla convexifiee d'une fonction: algorithmes rapides de calcul, analyse et regularite du second ordre</em></p> <p>I haven't read the last two papers very carefully, but hopefully they're relevant. As a small observation, you can order either $y$ or $x$ in decreasing order, thus at least one of the Legendre transform is straight forward.</p> http://mathoverflow.net/questions/121517/efficient-computation-of-discrete-infimal-convolution/122178#122178 Answer by Noah Stein for Efficient computation of "discrete infimal convolution" Noah Stein 2013-02-18T15:03:40Z 2013-02-18T15:03:40Z <p>After a bit more google searching, I found the 2006 paper <a href="http://compgeom.cs.uiuc.edu/~jeffe/pubs/pdf/necklace.pdf" rel="nofollow">Necklaces, Convolutions, and X+Y</a>, which addresses this problem. The nine authors give an $O(n\sqrt{n})$ algorithm in the nonuniform linear decision tree model (I'm having little trouble pinning down the details of this computational model) and an $O\left(\frac{n^3(\log \log n)^3}{(\log n)^2}\right)$ algorithm in the real RAM model. I haven't found any newer results, so it seems that the problem I posed is open.</p>