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

Question

El Teorema de la convolución se explota a menudo para calcular la convolución de dos secuencias de manera eficiente: tomar la transformación de Fourier (discreta) de cada secuencia, multiplicarlas y luego realizar la transformación inversa sobre el resultado.

Lo mismo puede hacerse para las convoluciones en el anillo de cociente Z/pZ a través del análogo Transformación teórica de los números .

¿Este procedimiento se generaliza a otras estructuras algebraicas? ¿Anillos arbitrarios? ¿Semirings? Las convoluciones rápidas sobre el semirritamiento (min,+) serían particularmente útiles.

Me lleva a sospechar esto porque tanto la clasificación como la FFT pueden ser computadas usando la misma red tipo mariposa con operaciones simples como "min", "max", "+" y "*" en los nodos de la red, y la clasificación puede ser pensada como una especie de convolución.

Answer 1

Puedes hacer la convolución infimal usando la transformación de Legendre. Ciertamente puedes implementar un algoritmo razonablemente rápido para la convolución infimal de funciones lineales convexas, aunque no conozco los algoritmos más rápidos conocidos que no usan la transformación de Legendre. La transformación de Legendre también se llama el conjugado de Fenchel en los documentos de optimización, así que es otro buen término para buscar en Google.

Answer 2

En general, en los algoritmos discretos es una cuestión importante que queda abierta en cuanto a qué estructuras algebraicas admiten algoritmos de convolución rápida y cuáles no. (Para ser concreto, defino el $( \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).$$ Aquí, $ \otimes $ y $ \oplus $ son las operaciones de multiplicación y adición de algunos semirremolques subyacentes).

Para cualquier $ \otimes $ y $ \oplus $ la convolución puede ser computada trivialmente en $O(n^2)$ operaciones. Como usted nota, 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, y no conocemos bien los límites inferiores. El mejor algoritmo para $( \min ,+)$ la convolución es $n^2/2^{ \Omega ( \sqrt { \log n})}$ debido a la combinación de mi reciente documento de la APSP

Ryan Williams: Pares más rápidos, caminos más cortos a través de la complejidad de los circuitos. 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, y X + Y. ESA 2006: 160-171

Un algoritmo sustancialmente subcuadrático para $( \min ,+)$ La convolución implicaría (hasta donde yo sé) un algoritmo subcúbico de todos los pares de caminos más cortos en los gráficos 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 "(mediana,+) convolución".

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

Answer 3

Mira el teorema del resto de los chinos sobre los anillos. La discreta transformación de Fourier es sólo un ejemplo.

La discreta transformación de Fourier sobre un campo $ \mathbb {F}$ (por ejemplo $ \mathbb {C}$ o $ \mathbb {F}_{q}$ ) usando 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 el DFT inverso puede ser igualado a (o fácilmente derivado de) la interpolación de Lagrange.

La interpolación es un caso especial del teorema del resto de China sobre $ \mathbb {F}[x]$ . Reducir un polinomio $f(x)$ modulo $(x- \alpha )$ es idéntica a la evaluación $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]$ de tal manera 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 de Lagrange. 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 el DFT el producto final del módulo es $ \prod_ {k=0}^{n-1}(x- \alpha ^n)=(x^n-1)$ y el módulo de multiplicación de polinomios $(x^n-1)$ es equivalente a la convolución de dos $n$ vectores largos.

El efecto mariposa del FFT proviene del uso de un $2^n$ -la raíz primitiva de la unidad, $ \alpha $ . Un efecto similar (aunque no tan elegante) puede lograrse usando $3^n$ -las primitivas raices de la unidad (o cualquier otra $p^n$ ) y combinando conjuntos específicos de tres ( $p$ ).

Lo que el teorema del resto de China te está dando es un isomorfismo entre los anillos de factor $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 $ \mathbb {Z}$ o $ \mathbb {F}[x]$ estas propiedades especiales equivalen a los ideales generados por elementos relativamente primarios. Por ejemplo, sobre $ \mathbb {Z}$ los ideales se verían como $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 haga modulo el producto puede realizarse en paralelo modulo cada factor.

Answer 4

Me tropecé con esta pregunta después de encontrar el problema en la inferencia Bayesiana (específicamente, realizar la inferencia del producto máximo en variables aleatorias donde $M = L + R$ donde $L$ y $R$ (o, una forma alternativa del problema, $M$ y $L$ ) han conocido distribuciones discretas y la distribución en $M$ (o $R$ en el problema alternativo). La función de masa de probabilidad (PMF) en $M$ que se logra mediante la maximización de $L$ y $R$ será el resultado de la máxima convolución entre los PMF de $L$ y $R$ .

Después de jugar un poco con él, me di cuenta de que puedes reescribir el problema generando $u^{(m)}$ para cada índice $m$ del resultado (donde $u^{(m)}[ \ell ] = L[ \ell ] R[{m- \ell }]$ ). Cuando los vectores no son negativos (en mi caso, esto era cierto porque son PMFs), entonces puedes realizar la $ \max_\ell u^{(m)}_ \ell $ con la norma 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 ser aproximado sustituyendo el $p^*$ -norma, donde $p^*$ es una constante suficientemente grande (esencialmente, esto explota el hecho de que la $p^*$ -norma hace tienen operaciones inversas, mientras que las $ \max $ no lo hace, pero el $p^*$ -la norma todavía 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 se puede realizar en $n \log (n)$ a través de FFT. Un breve artículo que ilustra la aproximación para los problemas de inferencia probabilística a gran escala está en prensa en el Journal of Computational Biology ( Serang 2015 arXiv preprint ).

Después un estudiante de doctorado, Julianus Pfeuffer, y yo hackeamos un límite preliminar sobre el error absoluto ( $p^*$ -Las aproximaciones de la norma Chebyshev son pobres cuando $p^*$ es pequeño, pero en los í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, entonces el simple método del primer papel funciona bien). El método modificado funciona a destajo $ \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 partículas en el universo observable, y esos 18 FFT pueden hacerse en paralelo). ( Pfeuffer y Serang arXiv link que tiene un enlace con una demostración del enfoque en Python) 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 de los elementos con la FFT multidimensional.

Oliver Serang