現假設有一組基元
b
0
(
t
)
,
b
1
(
t
)
,
b
2
(
t
)
,
b
3
(
t
)
.
.
.
.
.
.
b
N
(
t
)
{\displaystyle b_{0}(t),b_{1}(t),b_{2}(t),b_{3}(t)......b_{N}(t)}
D
{\displaystyle D}
b
n
(
t
)
{\displaystyle b_{n}(t)}
完備性 (Over-complete)、非正交集合。
壓縮感知的問題在此即為：
能不能找到最小的
|
|
a
|
|
0
{\displaystyle ||a||_{0}}
a
k
{\displaystyle a_{k}}
∀
k
=
{
1
,
2
,
.
.
.
,
N
}
{\displaystyle \forall k=\{1,2,...,N\}}
f
^
{\displaystyle {\hat {f}}}
f
{\displaystyle f}
f
(
t
)
=
∑
m
a
m
b
m
(
t
)
{\displaystyle f(t)=\sum _{m}a_{m}b_{m}(t)}
很明顯的，自然界中訊號大多只能以近似方式逼近，因此改為求
min
|
|
a
|
|
0
∫
|
|
f
(
t
)
−
∑
m
a
m
b
m
(
t
)
|
|
2
d
t
<
t
h
r
e
s
h
o
l
d
{\displaystyle \min _{||a||_{0}}\int ||f(t)-\sum _{m}a_{m}b_{m}(t)||^{2}dt<threshold}
然而，這個最佳化問題是NP困難 ，無法在線性多項式時間內找到解答，因此使用匹配追求的近似解來求解。
min
∫
|
|
f
(
t
)
−
∑
m
a
m
b
m
(
t
)
|
|
2
d
t
, such that
|
|
a
|
|
0
≤
N
{\displaystyle \min \int ||f(t)-\sum _{m}a_{m}b_{m}(t)||^{2}dt{\text{ , such that }}||a||_{0}\leq N}
輸入： 原訊號
f
(
t
)
{\displaystyle f(t)}
a
n
{\displaystyle a_{n}}
b
n
{\displaystyle b_{n}}
n
←
0
{\displaystyle n\leftarrow 0}
f
^
(
t
)
←
f
(
t
)
{\displaystyle {\hat {f}}(t)\leftarrow f(t)}
m
{\displaystyle m}
∫
f
^
(
t
)
b
m
∗
(
t
)
d
t
{\displaystyle \int {\hat {f}}(t)b_{m}^{*}(t)dt}
ϕ
n
(
t
)
←
b
m
(
t
)
{\displaystyle \phi _{n}(t)\leftarrow b_{m}(t)}
μ
n
←
∫
f
^
(
t
)
b
m
∗
(
t
)
d
t
{\displaystyle \mu _{n}\leftarrow \int {\hat {f}}(t)b_{m}^{*}(t)dt}
f
^
(
t
)
←
f
^
(
t
)
−
μ
n
ϕ
n
(
t
)
{\displaystyle {\hat {f}}(t)\leftarrow {\hat {f}}(t)-\mu _{n}\phi _{n}(t)}
n
←
n
+
1
{\displaystyle n\leftarrow n+1}
f
^
(
t
)
=
0
{\displaystyle {\hat {f}}(t)=0}
∫
f
^
(
t
)
2
(
t
)
d
t
<
t
h
r
e
s
h
o
l
d
{\displaystyle \int {\hat {f}}(t)^{2}(t)dt<threshold}
n
=
N
{\displaystyle n=N}
f
(
t
)
≈
f
^
(
t
)
=
∑
a
t
0
,
f
0
,
σ
φ
t
0
,
f
0
,
σ
(
t
)
{\displaystyle f(t)\approx {\hat {f}}(t)=\sum a_{t_{0},f_{0},\sigma }\varphi _{t_{0},f_{0},\sigma }(t)}
where
φ
t
0
,
f
0
,
σ
(
t
)
=
2
1
/
4
σ
1
/
2
e
j
2
π
f
0
t
−
π
(
t
−
t
0
)
2
σ
2
{\displaystyle \varphi _{t_{0},f_{0},\sigma }(t)={\frac {2^{1/4}}{\sigma ^{1/2}}}e^{j2\pi f_{0}t-{\frac {\pi (t-t_{0})^{2}}{\sigma ^{2}}}}}
近似訊號
f
^
{\displaystyle {\hat {f}}}
N
=
3
{\displaystyle N=3}
t
0
{\displaystyle t_{0}}
f
0
{\displaystyle f_{0}}
σ
{\displaystyle \sigma }
由於
φ
t
0
,
f
0
,
σ
{\displaystyle \varphi _{t_{0},f_{0},\sigma }}
a
t
0
,
f
0
,
σ
{\displaystyle a_{t_{0},f_{0},\sigma }}
[ 2]
編輯
f
(
t
)
≈
f
^
(
t
)
=
∑
a
t
0
,
f
0
,
σ
,
η
⋅
φ
t
0
,
f
0
,
σ
,
η
(
t
)
{\displaystyle f(t)\approx {\hat {f}}(t)=\sum a_{t_{0},f_{0},\sigma ,\eta }\cdot \varphi _{t_{0},f_{0},\sigma ,\eta }(t)}
where
φ
t
0
,
f
0
,
σ
,
η
(
t
)
=
2
1
/
4
σ
1
/
2
e
j
2
π
(
f
0
t
+
η
2
t
2
)
−
π
(
t
−
t
0
)
2
σ
2
{\displaystyle \varphi _{t_{0},f_{0},\sigma ,\eta }(t)={\frac {2^{1/4}}{\sigma ^{1/2}}}e^{j2\pi (f_{0}t+{\frac {\eta }{2t^{2}}})-{\frac {\pi (t-t_{0})^{2}}{\sigma ^{2}}}}}
近似訊號
f
^
{\displaystyle {\hat {f}}}
N
=
4
{\displaystyle N=4}
t
0
{\displaystyle t_{0}}
f
0
{\displaystyle f_{0}}
σ
{\displaystyle \sigma }
η
{\displaystyle \eta }
同理，由於
φ
t
0
,
f
0
,
σ
,
η
{\displaystyle \varphi _{t_{0},f_{0},\sigma ,\eta }}
a
t
0
,
f
0
,
σ
,
η
{\displaystyle a_{t_{0},f_{0},\sigma ,\eta }}
1. Jian-Jiun Ding, Time frequency analysis and wavelet transform class note, Department of Electrical Engineering, National Taiwan University (NTU), Taipei, Taiwan, 2017.
^ Chen, S. S.; Donoho, D. L.; Saunders, M. A. Atomic Decomposition by Basis Pursuit. SIAM Journal on Scientific Computing. 1998, 20 (1): 33–61. doi:10.1137/S003614450037906X ^ Bultan, A. A four-parameter atomic decomposition of chirplets. IEEE Transactions on Signal Processing. 1999, 47 (3): 731–745. doi:10.1109/78.747779
