¿Cómo hago convolución en F #?

Question

Me gustaría que convolve una señal discreta con un filtro discreto. La señal y el filtro son secuencias de float en F #.

La única forma en que puedo descubrir cómo hacerlo es con dos ciclos anidados para bucles y una matriz mutable para almacenar el resultado, pero no se siente muy funcional.

Así es como lo haría no funcional:

conv = double[len(signal) + len(filter) - 1]
for i = 1 to len(signal)
  for j = 1 to len(filter)
    conv[i + j] = conv[i + j] + signal(i) * filter(len(filter) - j) 

Answer 1

Prueba esta función:

let convolute signal filter =
    [|0 .. Array.length signal + Array.length filter - 1|] |> Array.map (fun i ->
        [|0 .. i|] |> Array.sum_by (fun j -> signal.[i] * filter.[Array.length filter - (i - j) - 1]))

Probablemente no sea la mejor solución funcional, pero debería hacer el trabajo. Sin embargo, dudo que exista una solución puramente funcional que coincida con la imperativa de velocidad.

Espero que ayude.

Nota: la función no está probada actualmente (aunque he confirmado que se compila). Déjame saber si no hace lo que debería. También, observe que las variables i y j no se refieren a las mismas cosas que su publicación original.

Answer 2

No sé F #, pero publicaré algo de Haskell y espero que esté lo suficientemente cerca como para usarlo. (Solo tengo VS 2005 y una versión antigua de F #, por lo que creo que sería más confuso publicar algo que funcione en mi máquina)

Permítame comenzar por publicar una implementación en Python de su pseudocódigo para asegurarme de que estoy obteniendo la respuesta correcta:

def convolve(signal, filter):
    conv = [0 for _ in range(len(signal) + len(filter) - 1)]
    for i in range(len(signal)):
        for j in range(len(filter)):
            conv[i + j] += signal[i] * filter[-j-1]
    return conv

Ahora convolve ([1,1,1], [1,2,3]) da [3, 5, 6, 3, 1] . Si esto está mal, por favor dígame.

Lo primero que podemos hacer es convertir el bucle interno en un zipWith; Esencialmente, estamos agregando una serie de filas de una manera especial, en el ejemplo anterior: [[3,2,1], [3,2,1], [3,2,1]] . Para generar cada fila, comprimimos cada i en la señal con el filtro invertido:

makeRow filter i = zipWith (*) (repeat i) (reverse filter)

(Nota: según un google rápido, zipWith es map2 en F #. Es posible que tenga que usar una lista de comprensión en lugar de repetir ) Ahora:

makeRow [1,2,3] 1
=> [3,2,1]
makeRow [1,2,3] 2
=> [6,4,2]

Para obtener esto para todos los i , necesitamos mapear sobre la señal:

map (makeRow filter) signal
=> [[3,2,1], [3,2,1], [3,2,1]]

Bien. Ahora solo necesitamos una manera de combinar las filas correctamente. Podemos hacer esto notando que la combinación es agregar la nueva fila a la matriz existente, excepto por el primer elemento, que está atascado en el frente. Por ejemplo:

[[3,2,1], [6,4,2]] = 3 : [2 + 6, 1 + 4] ++ [2]
// or in F#
[[3; 2; 1]; [6; 4; 2]] = 3 :: [2 + 6; 1 + 4] @ [2]

Entonces, solo necesitamos escribir un código que haga esto en el caso general:

combine (front:combinable) rest =
    let (combinable',previous) = splitAt (length combinable) rest in
    front : zipWith (+) combinable combinable' ++ previous

Ahora que tenemos una forma de generar todas las filas y una forma de combinar una nueva fila con una matriz existente, todo lo que tenemos que hacer es unir las dos con un doblez:

convolve signal filter = foldr1 combine (map (makeRow filter) signal)

convolve [1,1,1] [1,2,3]
=> [3,5,6,3,1]

Así que esa es una versión funcional. Creo que está razonablemente claro, siempre y cuando entiendas foldr y zipWith . Pero es al menos tan largo como la versión imperativa y, como dicen otros comentaristas, probablemente sea menos eficiente en F #. Aquí está todo en un solo lugar.

makeRow filter i = zipWith (*) (repeat i) (reverse filter)
combine (front:combinable) rest =
    front : zipWith (+) combinable combinable' ++ previous
    where (combinable',previous) = splitAt (length combinable) rest
convolve signal filter = foldr1 combine (map (makeRow filter) signal)

Editar:

Como se prometió, aquí hay una versión F #. Esto fue escrito usando una versión seriamente antigua (1.9.2.9) en VS2005, así que ten cuidado. Además, no pude encontrar splitAt en la biblioteca estándar, pero tampoco conozco F # tan bien.

open List
let gen value = map (fun _ -> value)
let splitAt n l = 
  let rec splitter n l acc =
    match n,l with
    | 0,_ -> rev acc,l
    | _,[] -> rev acc,[]
    | n,x::xs -> splitter (n - 1) xs (x :: acc)
  splitter n l [] 
let makeRow filter i = map2 ( * ) (gen i filter) (rev filter)
let combine (front::combinable) rest =
  let combinable',previous = splitAt (length combinable) rest
  front :: map2 (+) combinable combinable' @ previous
let convolve signal filter = 
  fold1_right combine (map (makeRow filter) signal)

Answer 3

De hecho, generalmente se quieren evitar los bucles (simples, anidados, lo que sea) y cualquier cosa que se pueda modificar en la programación funcional.

Resulta que hay una solución muy simple en F # (y probablemente en casi todos los demás lenguajes funcionales):

let convolution = Seq.zip seq1 seq2

La función zip simplemente combina las dos secuencias en una de las parejas que contienen el elemento de seq1 y el elemento de seq2 . Como nota, también existen funciones zip similares para los módulos List y Array , así como variantes para combinar tres listas en triples ( zip3 ). Si desea que tom ore generalmente zip (o " convolute ") n se incluya en una lista de n-tuplas, entonces deberá escribir su propia función, pero es bastante sencillo.

(He estado yendo por esta descripción de convolución por cierto - Dime si te refieres a otra cosa.

Answer 4

En principio, debería ser posible utilizar la Transformada de Fourier (Rápida), o la Transformada de Coseno (Discreta) relacionada, para calcular la convolución de dos funciones de manera razonablemente eficiente. Calcula la FFT para ambas funciones, multiplícalas y aplica la FFT inversa en el resultado.

antecedentes matemáticos

Esa es la teoría. En la práctica, probablemente sea mejor que encuentres una biblioteca matemática que la implemente por ti.