Why Eigenstuff Matters in DSP 1.1 2004/06/10 10:38:31 GMT-5 2004/07/06 10:48:07.515 GMT-5 Richard G. Baraniuk richb@rice.edu Richard G. Baraniuk richb@rice.edu Robert Ahlfinger ahlfing@rice.edu DSP Eig An explaination as to why eigenstuff matters in DSP Consider processing a signal x N with system represented by a normal matrix A

y A x matrix multiply y n K 0 N 1 where each y n involves coupling all x k via A n , k cost: O N 2 in general one-step procedure Now consider representation A V Λ V This is implemented by a three-step procedure: y A x V Λ V x α V x This computes the coefficients α that build up x in terms of eigenbasis v i : x V α (ie: V takes x from the "time-domain" to the "eigenbasis domain". Λ α with Λ a diagonal matrix Λ λ 0 0 0 0 0 λ 1 0 0 0 0 ... ... 0 0 0 ... λ N - 1 ie: we just do element-wise multiplication λ i α i (super easy and no coupling between α i 's) V Λ α y takes the vector Λ α back to the time-domain. Hallmarks Once we transform x to the eigenbasis domain of A , we can perform an operation equivalent to A but independently on each α i . This works for any normal matrix A . Most of the systems studied in DSP are "linear shift-invariant": all correspond to normal matrices all share the same V : DFT basis All LSI processing y A x can be done through: α fft x α ~ λ α where λ is diagonal of eigen matrix Λ y ifft α ~ The Cost: Step 1 O N N Step 2 O N Step 3 O N N total O N N O N N O N 2 ie: It is faster/more efficient than y A x directly!!!

Useful Formulas A V Λ V v 0 v 1 v 2 ... v N - 1 λ 0 0 0 0 0 λ 1 0 0 0 0 ... ... 0 0 0 ... λ N - 1 V 0 V 1 V 2 ... V N - 1