Blog Khoa Học Máy Tính

Tiếp theo bài trước, lần này ta bàn sơ qua về DFT. Tôi học DFT lần đầu tiên vào khoảng năm 1993. Học xong thấy nó rất bí hiểm, theo kiểu: nếu lấy vector này, tính toán thế này, thì ra các hệ số thế kia, nhưng không hiểu ý tưởng nằm sau các công thức đó. Sau này tôi mới khám phá ra là DFT chẳng qua là một phép thay đổi cơ sở (basis) trong không gian tuyến tính. Từ đó thấy mọi thứ rõ ràng, dễ hiểu hẳn ra.

Một trong những thước đo độ sâu và tầm quan trọng của một ý tưởng hay một nhánh nghiên cứu là ứng dụng của nó vào nhiều nơi (kể cả những chỗ mà ta không ngờ trước được là ý tưởng có thể có ứng dụng). Harmonic analysis nói chung và Discrete Fourier Transform nói riêng là một trong những nhánh như vậy. Ứng dụng của Fourier transforms có ở hầu hết tất cả mọi ngóc ngách của toán học, vật lý, khoa học máy tính, điện/điện tử, xác suất thống kê, vân vân. Ví dụ: Hastad đã dùng Fourier analysis để chứng minh một định lý rất quan trọng trong hệ thống PCP, các phân tích tốt nhất về expansion rate của một vài phép xây dựng expander graphs đều dùng Fourier analysis, v.v. Bạn có thể xem thêm vài lecture notes của giáo sư Nathan Linial về một số ứng dụng của Fourier analysis trong toán rời rạc, và master thesis này có thảo luận vài ứng dụng trong lý thuyết tính toán. (Các links đã dẫn chỉ là chóp đỉnh của tảng băng harmonic analysis khổng lồ!)

Về căn bản, DFT không có gì ghê gớm lắm. Căn bản đại số tuyến tính các bạn có thể xem một lecture note tôi tóm tắt vài thứ cần thiết. Hãy xét một ví dụ (tương đối) đơn giản sau đây. Xét một tập hữu hạn và tập . Dễ thấy rằng nếu thì có thể xem như (nói chính xác hơn thì và isomorphic với nhau). Giả sử ta có một orthonormal basis (hệ cơ sở trực chuẩn) của không gian , thì mọi vector đều có thể viết được dưới dạng:

(Ở đây ta ngầm hiểu các vectors đều là vectors cột.) Các hệ số cũng tạo thành một vector mà ta gọi là . Vector này chính là DFT của , ký hiệu là . Cái DFT mà ta thường gặp trong xử lý tín hiệu số tương ứng với một trường hợp đặc biệt khi mà

Trong đó là th root of unity.

Trong miền số phức, ta thường dùng hermitian form (hiểu nôm na là tích vô hướng của hai vectors) sau đây:

Vì các vectors là một orthonormal basis (nghĩa là chúng vuông góc với nhau và đều có chiều dài bằng , dễ thấy rằng

Đẳng thức này thường được gọi là đẳng thức Parseval. Đôi khi người ta gọi trường hợp đặc biệt khi là đẳng thức Parseval, hoặc đẳng thức Plancherel:

Nói cách khác: đổi hệ cơ sở của một vector space sang một hệ cơ sở trực chuẩn khác thì không thay đổi độ dài của các vectors.

Tập trong phân tích ở trên không nhất thiết là phải hữu hạn, miễn là bilinear form được chọn tốt là ta có thể xây dựng các hệ cơ sở trực chuẩn cho không gian tuyến tính tương ứng. Việc chọn hệ cơ sở như thế nào tùy thuộc rất nhiều vào ứng dụng đang xét. Ý tưởng chính của Fourier analysis là làm thế nào ta có thể phân tích các đặc tính của thông qua và ngược lại. Ví dụ: nếu chọn thì ta có thể dùng Fourier transform này để phân tích influence of variables on boolean functions (Hastad đã dùng ý tưởng này cho hệ thống PCP của ông).

Lần tới tôi sẽ nói thêm về trường hợp khi là một nhóm (thường là nhóm Abel) và cách chọn hệ cơ sở trực chuẩn là các characters của nhóm.

Chủ đề: Thuật Toán |