signal - 演算法筆記

signal

signal（time series）

「訊號」就是一串數字。

數學家稱作數列（離散）、函數（連續）。

訊號學家稱作數位訊號（離散）、類比訊號（連續）。

常見的signal

合成波：正弦波、方波、三角波、脈衝波。

脈衝函數：Dirac函數、高斯函數、sinc函數。

成長速率：步進函數、sigmoid函數、logistic函數。

市場波動：Gaussian process、Wiener process。

雜訊：AGWN。

signal的性質

脈衝：忽然劇烈變化、迅速還原。

週期：特定片段重複無限多次。通常稱作波。

穩態：最終收斂於特定常數。

signal的指標

平均數、變異數、偏度、峰度、ANOVA、能量、訊噪比、頻率、週期、過零率、包絡線、……。

知名工具tsfresh。

signal quantization

signal sampling

訊號取樣。時間軸離散化。保留重點，刪除細節。

signal quantization

訊號量化。數值軸離散化。保留重點，刪除細節。

簡易的量化是四捨五入、無條件捨去、無條件進入。進階的量化是區分數量級。經典的量化是以圖表相較並沒有明顯差異。

演算法（vector quantization）（cluster analysis）

先分群，以群集中心作為量化結果。

再分類，以分界線決定量化結果。

演算法（location-allocation analysis）

加強版。直線距離改成了其他指標。

演算法（product quantization）

分段、各自量化、合併。

signal resampling

signal reconstruction

訊號重建。找到原本波形。找到內插函數。

一、訊號通常很長。如果採用多項式內插，那麼內插函數必須是非常高次的多項式，才能穿過所有訊號。然而，非常高次的多項式，劇烈震盪，無法平順的穿過訊號，稱作「Runge's phenomenon」。

二、訊號通常取自真實世界、源自物理現象。例如聲音訊號，是由不同頻率的波，疊加而成的。詳見「傅立葉轉換」。

由於上述兩點，因而衍生了其他內插演算法。

signal resampling

訊號重新取樣。改變疏密程度，重新設計訊號。

變密稱作upsampling、變疏稱作downsampling。也有人把變密稱作interpolation、變疏稱作decimation。

訊號重新取樣＝訊號重建＋函數求值。

演算法（triangle interpolation）（linear interpolation）

三角波，等價於一次內插。不切實際，但是算得快。

演算法（sinc interpolation）

方波函數，實施逆向傅立葉轉換，頻域轉時域（反過來也行），就是sinc函數。如果頻域只有特定幾個頻率有方波（理想中是無限薄的脈衝，但是實際上是有點厚的方波），那麼時域採用sinc函數，最理想不過了。算得極慢。

演算法（Lanczos interpolation）

加強版。自由調整胖瘦。砍掉綿延的小波，只留主要的部分。

演算法（Mitchell–Netravali filter）

加強版。改用三次多項式函數模擬之。算得快。

signal prediction

signal estimation（time series analysis）

訊號估計。找到訊號規律。找到迴歸函數。

迴歸函數是遞迴函數、週期函數等等具有規律的函數。

誤差設定成「均方誤差mean squared error」：平方誤差，再除以數列長度；平方誤差的平均數。如此一來，長度不同的數列，得以互相比較誤差大小。

signal prediction（time series forecasting）

訊號預測。訊號有某種規律，請預測接下來的訊號。

訊號預測＝訊號估計＋函數求值。

演算法（linear prediction）（linear predictive coding）

請見本站文件「filter」。

linear regression：用一次函數符合資料。linear prediction：用線性遞迴函數符合資料。

首先求得均方誤差最小的線性遞迴函數。時間複雜度O(N²)，在頻域計算可加速為O(NlogN)。

求得線性遞迴函數之後，欲預測下一個新訊號，直接代入最後K個舊訊號即可。時間複雜度O(K)，K是線性遞迴函數的項數。

求得線性遞迴函數之後，欲預測第M個新訊號，共有四種演算法。時間複雜度O(K²logM)，在頻域計算可加速為O(KlogKlogM)。

演算法（ARIMA）

加強版。遞迴關係式增加項次。

演算法（ARCH）

加強版。推廣成非線性，引入統計學。

演算法（Prophet）

signal classification🚧

signal detection

訊號偵測。判斷訊號是資訊或是雜訊。

signal classification

訊號分類。判斷訊號是哪種常見訊號。

演算法（MUSIC）

演算法（hidden Markov model）

signal separation🚧

signal overlapping

訊號疊加。數據軸加法。大量訊號疊合在一起。

signal separation

訊號分隔。數據軸分割。大量訊號疊合在一起，分隔每道訊號。

假定數據是關鍵因子的加權平均數。真實世界有許多自然現象是加權平均數，例如合力就是施力的加權平均數。

例如麥克風錄到一段演奏，嘗試分隔出每種樂器的聲音。

例如相機拍到一個場景，嘗試分隔出光線的來源與強度。

例如RFID收到一段訊號，嘗試分隔出訊號的原始波形。

演算法（independent component analysis）

演算法（wavelet analysis）

請參考「Fourier transform」。

signal segmentation🚧

signal concatenation

訊號銜接。時間軸銜接。大量訊號銜接在一起。

主要問題在於波形不連續。在於相位。淡入淡出也無法解決。

signal segmentation

訊號分段。時間軸分割。大量訊號銜接在一起，分割每段訊號。

signal representation🚧

signal transformation

訊號變換。訊號套用函數，改變訊號造型。

signal representation

訊號表示。訊號套用函數，換個視角呈現訊號。

演算法（Karhunen–Loève transform）（Hotelling transform）

即是principal component analysis。

演算法（sparse coding）