¿se aplica el "teorema de convolución" a estructuras algebraicas más débiles?

Question

En Teorema de convolución se utiliza a menudo para calcular la convolución de dos secuencias de forma eficaz: se toma la transformada (discreta) de Fourier de cada secuencia, se multiplican y, a continuación, se realiza la transformada inversa sobre el resultado.

Lo mismo se puede hacer para las circunvoluciones en el anillo cociente Z/pZ mediante la análoga Transformada teórica de números .

¿Se puede generalizar este procedimiento a otras estructuras algebraicas? ¿Anillos arbitrarios? ¿Semirings? Las circunvoluciones rápidas sobre el semiring (min,+) serían particularmente útiles.

Sospecho esto porque tanto la ordenación como la FFT pueden calcularse utilizando la misma red en forma de mariposa con operaciones sencillas como "min", "max", "+" y "*" en los nodos de la red, y la ordenación puede considerarse una especie de convolución.

Answer 1

En general, es una importante cuestión abierta en los algoritmos discretos qué estructuras algebraicas admiten algoritmos de convolución rápidos y cuáles no. (Para concretar, defino la $(\oplus,\otimes)$ convolución de dos $n$ -vectores $[x_0,\ldots,x_{n-1}]$ y $[y_0,\ldots,y_{n-1}]$ para ser el vector $[z_0,\ldots,z_{n-1}]$ con $$z_k = (x_0 \otimes y_k) \oplus (x_1 \otimes y_{k-1}) \oplus \cdots \oplus (x_k \otimes y_0).$$ Toma, $\otimes$ y $\oplus$ son las operaciones de multiplicación y suma de algún semiring subyacente).

Para cualquier $\otimes$ y $\oplus$ la convolución puede calcularse trivialmente en $O(n^2)$ operaciones. Como usted señala, cuando $\otimes = \times$ , $\oplus = +$ y trabajamos sobre los números enteros, esta convolución se puede hacer eficientemente, en $O(n \log n)$ operaciones.

Pero para operaciones más complejas, no conocemos algoritmos eficientes ni buenos límites inferiores. El mejor algoritmo para $(\min,+)$ convolución es $n^2/2^{\Omega (\sqrt{\log n})}$ operaciones, debido a la combinación de mi reciente documento APSP

Ryan Williams: Faster all-pairs shortest paths via circuit complexity. STOC 2014: 664-673

y

David Bremner, Timothy M. Chan, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Perouz Taslakian: Necklaces, Convolutions, and X + Y. ESA 2006: 160-171

Un algoritmo sustancialmente subcuadrático para $(\min,+)$ La convolución implicaría (que yo sepa) un algoritmo subcúbico de todos los pares de caminos más cortos en grafos generales, un problema abierto desde hace mucho tiempo. La referencia ESA06 anterior también da una $O(n^2 (\log \log n)^2/\log n)$ algoritmo para una convolución "(mediana,+)".

La situación es sutil. No está claro cuándo la convolución sobre un semiring es fácil y cuándo es difícil. Por ejemplo, la $(\min,\max)$ convolución puede calcularse en tiempo subcuadrático: Creo que $O(n^{3/2} \log n)$ operaciones es suficiente. Esto puede obtenerse adaptando el $(\min,\max)$ algoritmo de multiplicación de matrices en mi trabajo con Vassilevska y Yuster sobre caminos de cuello de botella de todos los pares. Básicamente se reduce el problema a calcular $\sqrt{n}$ instancias de un $(+,\times)$ convolución en anillo.

Answer 2

Puedes hacer convolución infima utilizando la transformada de Legendre. Ciertamente se puede implementar un algoritmo razonablemente rápido para la convolución infima de funciones lineales convexas a trozos, aunque no conozco los algoritmos más rápidos conocidos que no utilicen la transformada de Legendre. La transformada de Legendre también se denomina conjugada de Fenchel en los artículos sobre optimización, así que es otro buen término para buscar en Google.

Answer 3

Mira el teorema chino del resto sobre anillos. La transformada discreta de Fourier es sólo un ejemplo.

La transformada discreta de Fourier sobre un campo $\mathbb{F}$ (por ejemplo $\mathbb{C}$ o $\mathbb{F}_{q}$ ) utilizando un $n^{th}$ raíz primitiva de la unidad $\alpha$ (en $\mathbb{C}$ , $\alpha=e^{2\pi i/n}$ ) de un vector $\left[a_{n-1}\ a_{n-2}\ \ldots\ a_0\right]$ es equivalente a evaluar el polinomio $\sum^{(n-1)}_{j=0}a_jx^k $ en $\alpha^k$ para $k=0,1,\ldots, (k-1)$ : $$\mathcal{F}\left( \sum^{(n-1)}_{j=0}a_jx^k\right)= \left[\sum^{(n-1)}_{j=0}a_j(\alpha^k)^j\right]_{j=0}^{n-1}$$ y la DFT inversa puede equipararse a (o derivarse fácilmente de) la interpolación lagrangiana.

La interpolación es un caso especial del teorema del resto chino sobre $\mathbb{F}[x]$ . Reducción de un polinomio $f(x)$ modulo $(x-\alpha)$ es idéntico a evaluar $f(x)$ en $\alpha$ ( $x\equiv \alpha \bmod{(x-\alpha)}$ ). Interpolación del conjunto de puntos distintos $\left\{(\alpha_k,\beta_k),\ k=0,1,\ldots,(n-1)\right\}$ es equivalente a encontrar el polinomio $f(x)\in \mathbb{F}[x]/\left(\prod_{k=0}^{n-1}(x-\alpha_k)\right)\mathbb{F}[x]$ tal que $f(x)\equiv \beta_k\bmod{(x-\alpha_k)}$ : $$\begin{array}{rl}f(x)&\equiv\sum_{k=0}^{n-1}\left(\prod_{j\neq k}(x-\alpha_j)\right)\left(\left(\prod_{j\neq k}(x-\alpha_j)\right)^{-1}\beta_k\bmod{(x-\alpha_k)}\right)\\ &\equiv \sum_{k=0}^{n-1}\left(\frac{\prod_{j\neq k}(x-\alpha_j)}{\prod_{j\neq k}(\alpha_k-\alpha_j)}\right)\beta_k \bmod{\prod_{k=0}^{n-1}(x-\alpha_k)}\end{array}$$ La segunda línea de esa ecuación, menos el mod, es la fórmula de interpolación lagrangiana. El mod sólo significa que cualquier polinomio de la forma $f(x)+h(x)\prod_{k=0}^{n-1}(x-\alpha_k)$ donde $h(x)$ es cualquier polinomio sobre $\mathbb{F}$ pasará por estos mismos puntos.

Para la DFT, el producto final del módulo es $\prod_{k=0}^{n-1}(x-\alpha^n)=(x^n-1)$ y la multiplicación polinómica módulo $(x^n-1)$ es equivalente a la convolución de dos $n$ vectores largos.

El efecto mariposa de la FFT proviene de utilizar un $2^n$ -enésima raíz primitiva de la unidad, $\alpha$ . Se puede conseguir un efecto similar (aunque no tan elegante) utilizando $3^n$ -raíces primitivas de la unidad (o cualquier otra $p^n$ ) y combinando conjuntos especificados de tres ( $p$ ).

Lo que el teorema chino del resto nos da en realidad es un isomorfismo entre los anillos factoriales $R/\bigcap_{k=0}^{n-1}I_k\cong \bigotimes_{k=0}^{n-1}R/I_k$ donde $I_k<R$ son ideales en $R$ con propiedades especiales. Si $R$ es un dominio euclidiano, como por ejemplo $\mathbb{Z}$ o $\mathbb{F}[x]$ estas propiedades especiales equivalen a que los ideales están generados por elementos relativamente primos. Por ejemplo, sobre $\mathbb{Z}$ los ideales serían $I_k=p_k\mathbb{Z}$ con $GCD(p_k,p_j)=1$ para todos los pares distintos de $(k,j)$ y la intersección de los ideales sería $\bigcap I_k=\left(\prod p_k\right)\mathbb{Z}$ . Cualquier operación que se realice en el módulo del producto puede realizarse en paralelo en el módulo de cada factor.

Answer 4

Me topé con esta pregunta después de encontrarme con el problema en la inferencia bayesiana (en concreto, realizar la inferencia de producto máximo en variables aleatorias donde $M = L + R$ donde $L$ y $R$ (o, una forma alternativa del problema, $M$ y $L$ ) tienen distribuciones discretas conocidas y la distribución en $M$ (o $R$ en el problema alternativo). La función de masa de probabilidad (PMF) en $M$ que se consigue maximizando $L$ y $R$ será el resultado de la max-convolución entre los PMF de $L$ y $R$ .

Después de jugar un poco con él, me di cuenta de que se puede reescribir el problema generando $u^{(m)}$ para cada índice $m$ del resultado (donde $u^{(m)}[\ell] = L[\ell] R[{m-\ell}]$ ). Cuando los vectores son no negativos (en mi caso, esto era así porque se trata de PMFs), entonces se puede realizar la operación $\max_\ell u^{(m)}_\ell$ con la norma de Chebyshev:

$$ M[m] = \max_\ell u^{(m)}_\ell \\ = \lim_{p \to \infty} \| u^{(m)} \|_p \\ = \lim_{p \to \infty} {\left( \sum_\ell {\left( u^{(m)}[\ell] \right)}^{p} \right)}^{\frac{1}{p}} $$

Esto, a su vez, puede aproximarse sustituyendo el $p^*$ -norma, donde $p^*$ es una constante suficientemente grande (esencialmente, esto explota el hecho de que el $p^*$ -norm hace tienen operaciones inversas, mientras que $\max$ no lo hace, pero el $p^*$ -puede aproximarse a la $\max$ ) : $$ \approx {\left( \sum_\ell {\left( u^{(m)}[\ell] \right)}^{p^*} \right)}^{\frac{1}{p^*}}\\ = {\left( \sum_\ell {L[\ell]}^{p^*} ~ {R[{m-\ell}]}^{p^*} \right)}^{\frac{1}{p^*}}\\ = {\left( \sum_\ell {\left(L^{p^*}\right)}[\ell] ~ {\left(R^{p^*}\right)}[{m-\ell}] \right)}^{\frac{1}{p^*}}\\ = {\left( L^{p^*} ~*~ R^{p^*} \right)}^{\frac{1}{p^*}}[m] $$

donde $*$ es la convolución estándar, que puede realizarse en $n \log(n)$ a través de FFT. Un breve artículo que ilustra la aproximación para problemas de inferencia probabilística a gran escala está en prensa en el Journal of Computational Biology ( Serang 2015 arXiv preprint ).

Posteriormente, un estudiante de doctorado, Julianus Pfeuffer, y yo elaboramos un límite preliminar del error absoluto ( $p^*$ -de la norma de Chebyshev son malas cuando $p^*$ es pequeño, pero en índices donde el resultado normalizado $\frac{M[m]}{\max_{m'} M[m']}$ es muy pequeño, grande $p^*$ puede ser numéricamente inestable). Julianus y yo elaboramos un método modificado para los casos en que el rango dinámico del resultado $M$ es muy grande (si no, el método sencillo del primer artículo funciona bien). El método modificado opera a trozos sobre $\log(\log(n))$ diferente $p^*$ (incluidas las constantes de tiempo de ejecución, esto equivale a $\leq 18$ FFT incluso cuando $n$ está en la escala de las partículas del universo observable, y esas 18 FFT pueden hacerse en paralelo). ( Enlace arXiv de Pfeuffer y Serang que tiene un enlace a una demostración en Python del enfoque) El enfoque (y el código de demostración en Python) se generalizan a los tensores ( es decir , numpy.array s) combinando esencialmente la norma de Frobenius por elementos con la FFT multidimensional.

Oliver Serang