F＃で畳み込みを行うにはどうすればよいですか？

Question

コンボリューションを離散フィルターで離散信号にしたいです。信号とフィルターは、F＃のフロートのシーケンスです。

2つのネストされたforループと結果を格納する可変配列を使用する方法しかわかりませんが、あまり機能的ではありません。

これは私がそれを機能しないようにする方法です：

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

この関数を試してください：

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]))

これはおそらく最も優れた関数ソリューションではありませんが、仕事をするはずです。ただし、スピードの点で必須のソリューションと一致する純粋に機能的なソリューションは存在しないと思います。

役立つこと。

注：この関数は現在テストされていません（コンパイルを確認していますが）。期待どおりに動作しない場合はお知らせください。また、変数 i および j は元の投稿と同じものを参照していないことに注意してください。

Answer 2

私はF＃を知りませんが、Haskellをいくつか投稿します。 （私はVS 2005とF＃の古代バージョンしか持っていないので、自分のマシンで動作するものを投稿するのはもっと混乱すると思います）

まず、擬似コードのPython実装を投稿して、正しい答えが得られるようにします：

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

Now convolve（[1,1,1]、[1,2,3]）は、 [3、5、6、3、1] を返します。これが間違っている場合は、教えてください。

最初にできることは、内側のループをzipWithに変えることです。上記の例では、基本的に特別な方法で一連の行を追加しています： [[3,2,1]、[3,2,1]、[3,2,1]] 。各行を生成するために、 signal の各 i を逆フィルターで圧縮します：

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

（注：クイックグーグルによると、 zipWith はF＃では map2 です。 repeat の代わりにリストの内包表記を使用する必要がある場合があります。 ） 今：

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

すべての i でこれを取得するには、信号をマッピングする必要があります：

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

良い。ここで、行を適切に結合する方法が必要です。これを行うには、最初の要素を除いて、結合により既存の配列に新しい行が追加されることに注意してください。例：

[[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]

だから、一般的な場合にこれを行うコードを書く必要があります：

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

すべての行を生成する方法と、新しい行を既存の配列と結合する方法が用意できたので、必要なのは2つを折り畳むだけです：

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

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

これは機能的なバージョンです。 folder と zipWith を理解している限り、それはかなり明確だと思います。しかし、少なくとも命令型バージョンや他のコメンターが言ったように、おそらくF＃では効率が劣ります。ここにすべてが1か所にあります。

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)

編集：

約束どおり、ここにF＃バージョンがあります。これは、VS2005の非常に古いバージョン（1.9.2.9）を使用して記述されたため、注意してください。また、標準ライブラリで splitAt を見つけることができませんでしたが、F＃についてはよくわかりません。

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

実際には、通常、ループ（プレーン、ネスト、何でも）や関数型プログラミングで変更可能なものは避けたいと思います。

F＃には非常に簡単な解決策があります（そしておそらく他のほとんどすべての関数型言語）：

let convolution = Seq.zip seq1 seq2

zip 関数は、2つのシーケンスを単に seq1 の要素と seq2 の要素を含むペアの1つに結合します。メモとして、 List および Array モジュール用の同様のzip関数、および3つのリストをトリプルに結合するためのバリアント（ zip3 ）。 tom oreが一般にn個のリストをnタプルのリストにzip（または＆quot; convolute＆quot;）したい場合、独自の関数を記述する必要がありますが、それは非常に簡単です。

（私はこの説明でたたみ込んでいます-他に何か意味があるか教えてください。）

Answer 4

原則として、（高速）フーリエ変換または関連する（離散）コサイン変換を使用して、2つの関数の畳み込みを合理的に効率的に計算できる必要があります。両方の関数のFFTを計算し、乗算して、結果に逆FFTを適用します。

数学的な背景

それが理論です。実際には、おそらくそれを実装する数学ライブラリを見つけるのが一番いいでしょう。