• matrix multiply
• yn=∑K=0N-1 y n K 0 N 1 (2)
  where each yn y n involves coupling all xk x k via A n , k A n , k
• cost: ON2 O N 2 in general
• one-step procedure

1. α=VHx α V x This computes the coefficients α α that build up x x in terms of eigenbasis vi v i : x=Vα x V α (ie: VH V takes x x from the "time-domain" to the "eigenbasis domain".
2. Λα Λ α with Λ Λ a diagonal matrix Λ= λ 0 0000 λ 1 0000 ... ... 000... λ N - 1 Λ λ 0 0 0 0 0 λ 1 0 0 0 0 ... ... 0 0 0 ... λ N - 1 ie: we just do element-wise multiplication λ i α i λ i α i (super easy and no coupling between α i α i 's)
3. VΛα=y V Λ α y takes the vector Λα Λ α back to the time-domain.

Hallmarks

• Once we transform x x to the eigenbasis domain of A A, we can perform an operation equivalent to A A but independently on each α i α i .
• This works for any normal matrix A A.
• Most of the systems studied in DSP are "linear shift-invariant":
  • all correspond to normal matrices
  • all share the same V V: DFT basis

1. α=fftx α fft x
2. α ~ =λα α ~ λ α where λ λis diagonal of eigen matrix Λ Λ
3. y=ifft α ~ y ifft α ~

• Step 1: ONlogN O N N
• Step 2: ON O N
• Step 3: ONlogN O N N
• total: ONlogN O N N