• matrix multiply
• y⁢n=∑K=0N−1 y n K 0 N 1

  (2)
  where each y⁢n y n involves coupling all x⁢k x k via A n , k A n , k
• cost: O⁢N2 O N 2 in general
• one-step procedure

1. α=VH⁢x α V x This computes the coefficients α α that build up x x in terms of eigenbasis v i 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 000 0 λ 1 00 00 ... ... 0 00... λ 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. α=fft⁢x α fft x
2. α ~ =λ⁢α α ~ λ α where λ λis diagonal of eigen matrix Λ Λ
3. y=ifft⁢ α ~ y ifft α ~

• Step 1: O⁢N⁢logN O N N
• Step 2: O⁢N O N
• Step 3: O⁢N⁢logN O N N
• total: O⁢N⁢logN O N N