找回密码
 注册
关于网站域名变更的通知
查看: 226|回复: 1
打印 上一主题 下一主题

MATLAB的帮助文档中是怎样对 MP 算法以及 OMP 算法进行解释的(英文版)

[复制链接]

该用户从未签到

跳转到指定楼层
1#
发表于 2019-12-30 10:15 | 只看该作者 |只看大图 回帖奖励 |倒序浏览 |阅读模式

EDA365欢迎您登录!

您需要 登录 才可以下载或查看,没有帐号?注册

x

0 r( Z, |6 U  v目录9 V5 G1 v/ R2 b/ |% s0 P* R

5 V4 B; l5 ~( L. L4 ^1 t: ZMatching Pursuit Algorithms
1 k* [( t$ m" z6 n; M* |9 v" g# |3 Z* @% ]8 n8 X3 x; a; {3 a
       Redundant Dictionaries and Sparsity0 n/ Z% p0 o& T8 @

+ C. b) |( E6 u& k% e       Nonlinear Approximation in Dictionaries2 ^+ S6 g5 h9 e, y2 `/ I3 c1 U

* m/ d0 s* I/ t& M* M* c       Basic Matching Pursuit9 L) s% X; C3 s& Z; ?+ L5 X

3 o+ K% G- s; v2 G) n       Orthogonal Matching Pursuit- b3 h* F3 M/ }6 T; m  M

1 _1 u+ h- G0 |
+ t+ E9 f4 A9 B4 o9 `4 RMatching Pursuit Algorithms Redundant Dictionaries and Sparsity9 J1 v* Y; \! K# V) R; U7 X8 b3 ]
Representing a signal in a particular basis involves finding the unique set of expansion coefficients in that basis. While there are many advantages to signal representation in a basis, particularly an orthogonal basis, there are also disadvantages.$ v1 v* r5 C4 m9 J, F: S

) p9 i% E+ ~- ?( F" X+ c) VThe ability of a basis to provide a sparse representation depends on how well the signal characteristics match the characteristics of the basis vectors. For example, smooth continuous signals are sparsely represented in a Fourier basis, while impulses are not. A smooth signal with isolated discontinuities is sparsely represented in a wavelet basis. However, a wavelet basis is not efficient at representing a signal whose Fourier transform has narrow high frequency support.
/ U+ C. @2 A4 Q7 W0 U& Q  z3 {$ Q& M! r0 H. j( m8 n+ Q0 H/ Z
Real-world signals often contain features that prohibit sparse representation in any single basis. For these signals, you want the ability to choose vectors from a set not limited to a single basis. Because you want to ensure that you can represent every vector in the space, the dictionary of vectors you choose from must span the space. However, because the set is not limited to a single basis, the dictionary is not linearly independent.
, Q# V2 s; x: B0 B% e* [# _- J# }2 Z/ Q& d$ k
Because the vectors in the dictionary are not a linearly independent set, the signal representation in the dictionary is not unique. However, by creating a redundant dictionary, you can expand your signal in a set of vectors that adapt to the time-frequency or time-scale characteristics of your signal. You are free to create a dictionary consisting of the union of several bases. For example, you can form a basis for the space of square-integrable functions consisting of a wavelet packet basis and a local cosine basis. A wavelet packet basis is well adapted to signals with different behavior in different frequency intervals. A local cosine basis is well adapted to signals with different behavior in different time intervals. The ability to choose vectors from each of these bases greatly increases your ability to sparsely represent signals with varying characteristics." f) E$ V1 ~9 C6 z9 u
  }" h4 Y9 Q5 A; M6 S. F
' g) H8 @/ ~2 j+ W$ H9 ~
Nonlinear Approximation in Dictionaries
4 a, C$ @# @( S& o: d6 }7 B$ {3 b) t8 g# ]; @' `) u3 I5 c
Define a dictionary as a collection of unit-norm elementary building blocks for your signal space. These unit-norm vectors are called atoms. If the atoms of the dictionary span the entire signal space, the dictionary is complete.
6 A* v4 d, e( I: ^, _- o& u0 L0 r* q# h
If the dictionary atoms form a linearly-dependent set, the dictionary is redundant. In most applications of matching pursuit, the dictionary is complete and redundant.2 C* ?% }+ `' M( P/ }5 O3 T! h- H, R

9 v3 D/ k' O; }7 _% Y# }Let {φk} denote the atoms of a dictionary. Assume the dictionary is complete and redundant. There is no unique way to represent a signal from the space as a linear combination of the atoms.) `: R( {. A+ j$ n2 R
5 i/ q& @/ I) ^% }: M* `  I3 e7 |
7 H+ o6 W& _; `: J' l. \+ Y4 q
" `; V0 F; l( f9 E
An important question is whether there exists a best way. An intuitively satisfying way to choose the best representation is to select the φk yielding the largest inner products (in absolute value) with the signal. For example, the best single φkis9 j4 z, @& ~/ Q: W4 d/ g
. `8 k$ L. E3 I6 ]5 E' ]- q4 p

1 M( ?. x$ Y$ u9 Z7 s! U/ r6 [3 U  B7 E/ r) Y, P& u* D. H
which for a unit-norm atom is the magnitude of the scalar projection onto the subspace spanned by φk.
/ o3 |! n7 g- P7 P3 F# e3 `5 `1 w7 p
The central problem in matching pursuit is how you choose the optimal M-term expansion of your signal in a dictionary.
' z2 D8 ^0 m, [- v4 R* \
1 L& o2 l3 ^# s- t* R: R: T  k. J$ k1 V
Basic Matching Pursuit
6 X& U% P/ i& C# J
' a8 ~0 Z7 v6 @7 t

8 r- r( m1 t4 l! ]" W- W) ~Let Φ denote the dictionary of atoms as a N-by-M matrix with M>N. If the complete, redundant dictionary forms a frame for the signal space, you can obtain the minimum L2 norm expansion coefficient vector by using the frame operator.# A) S' y5 T( C( V! ~
. S& R' I7 s8 Z' ]9 u. u9 v3 b
( A0 {+ m; p- V3 u& ?

1 t: J+ K- M2 ]/ v7 s* MHowever, the coefficient vector returned by the frame operator does not preserve sparsity. If the signal is sparse in the dictionary, the expansion coefficients obtained with the canonical frame operator generally do not reflect that sparsity. Sparsity of your signal in the dictionary is a trait that you typically want to preserve. Matching pursuit addresses sparsity preservation directly.
" r0 g/ q7 T- Y  p* T6 W: c& h; g6 c* y
Matching pursuit is a greedy algorithm that computes the best nonlinear approximation to a signal in a complete, redundant dictionary. Matching pursuit builds a sequence of sparse approximations to the signal stepwise. Let Φ= {φk} denote a dictionary of unit-norm atoms. Let f be your signal.3 ~- V! e1 `; _" t5 S: H2 T: Z

& m2 \+ h* t( @( f0 ~
" Z4 W9 h$ K! t$ ], d' ~) ]
  B* \9 i( X2 h) h7 R# |In nonorthogonal (or basic) matching pursuit, the dictionary atoms are not mutually orthogonal vectors. Therefore, subtracting subsequent residuals from the previous one can introduce components that are not orthogonal to the span of previously included atoms.. X* }; S* @# D+ i0 E: G

* z. n2 ]* w( u3 p; Q: ITo illustrate this, consider the following example. The example is not intended to present a working matching pursuit algorithm.3 l3 V0 a5 B1 q
) a: A7 \2 r0 d" w+ l$ `

! d" m6 z6 _2 i0 `! n6 L: Q# Q4 S, B

4 s* n5 k6 d  q! Y3 a
) \* e5 W2 ~4 _$ E1 Z
& {3 i% ~1 P" g" M% Q8 O+ }Construct this dictionary and signal in MATLAB®.
4 \/ x9 @9 z& L8 N
9 W, R- c: _' h- Jdictionary = [1 0; 1/2 sqrt(3)/2; -1/sqrt(2) -1/sqrt(2)]';9 y: W: h4 r/ G+ r! C  Q% }
x = [1 1/2]';& J' o9 K2 k; e. o
9 i' a; m5 v5 R
Compute the inner (scalar) products between the signal and the dictionary atoms.# q" q8 u# Q$ t# a, f) [
0 f0 z' `1 N7 l) z$ M% g) N+ ]) j
scalarproducts = dictionary'*x;" c: _, r$ Y/ h/ k
; x' |: E2 Q; o! k. x5 r
The largest scalar product in absolute value occurs between the signal and [-1/sqrt(2); -1/sqrt(2)]. This is clear because the angle between the two vectors is almost π radians.
5 j( H9 }+ N! O) c3 s3 Y' q; e# O& T$ ^+ R
Form the residual by subtracting the orthogonal projection of the signal onto [-1/sqrt(2); -1/sqrt(2)] from the signal. Next, compute the inner products of the residual (new signal) with the remaining dictionary atoms. It is not necessary to include [-1/sqrt(2); -1/sqrt(2)] because the residual is orthogonal to that vector by construction.8 q$ ], Y& {9 F) a

5 K% l( n2 Q! v# w7 C4 o( C9 ]& q* rresidual = x-scalarproducts(3)*dictionary(:,3);
1 Z+ l5 U4 m6 ?6 q: iscalarproducts = dictionary(:,1:2)'*residual;
) e" M# c3 l# B: D/ W* e0 d( }, z" {8 I0 M' b
The largest scalar product in absolute value is obtained with [1;0]. The best two atoms in the dictionary from two iterations are [-1/sqrt(2); -1/sqrt(2)] and [1;0]. If you iterate on the residual, you see that the output is no longer orthogonal to the first atom chosen. In other words, the algorithm has introduced a component that is not orthogonal to the span of the first atom selected. This fact and the associated complications with convergence argues in favor ofOrthogonal Matching Pursuit (OMP).
) O4 P' p' q- U& L7 U
, l9 G& S4 x# G; S0 f- ]5 y' c5 M
9 o* P4 P7 Y6 V! C- H, |  [+ ?0 kOrthogonal Matching Pursuit
* r' l9 N9 U: L
. e7 E7 A$ g; ~: l  o' sIn orthogonal matching pursuit (OMP), the residual is always orthogonal to the span of the atoms already selected. This results in convergence for a d-dimensional vector after at most d steps.
7 t* s) A7 W% z, A- B& r0 ?9 @% f5 M; s0 e0 l$ ~
conceptually, you can do this by using Gram-Schmidt to create an orthonormal set of atoms. With an orthonormal set of atoms, you see that for a d-dimensional vector, you can find at most dorthogonal directions.
! V; s2 R, c, `. P8 E
+ K. o0 C0 K  {9 Z ( z0 L# G( [4 u; E" ]/ m

4 X+ C, i: Q: W. z) i8 A ) x7 t1 a( d) a) b5 q
3 a; E' V; {; A4 h, z" |
1 s6 B# K; r+ M* ]1 c0 {3 F

该用户从未签到

2#
发表于 2019-12-30 19:02 | 只看该作者
这个我得好好翻译一下
您需要登录后才可以回帖 登录 | 注册

本版积分规则

关闭

推荐内容上一条 /1 下一条

EDA365公众号

关于我们|手机版|EDA365电子论坛网 ( 粤ICP备18020198号-1 )

GMT+8, 2025-6-12 22:41 , Processed in 0.093750 second(s), 26 queries , Gzip On.

深圳市墨知创新科技有限公司

地址:深圳市南山区科技生态园2栋A座805 电话:19926409050

快速回复 返回顶部 返回列表