تبدیل فوریه تنک ۲۰۱۸
The Sparse Fourier Transform 2018

تبدیل فوریه یکی از اساسی‌ترین ابزارها برای محاسبه‌ی نمایش فرکانسی سیگنال‌ها است. این تبدیل، نقشی محوری در پردازش سیگنال، ارتباطات، فشرده‌سازی صوتی و تصویری، تصویربرداری پزشکی، ژنومیکس، نجوم و بسیاری از زمینه‌های دیگر ایفا می‌کند. به دلیل کاربرد گسترده‌ی آن، الگوریتم‌های سریع برای محاسبه‌ی تبدیل فوریه می‌توانند به تعداد زیادی از برنامه‌ها و کاربردها کمک کنند. سریع‌ترین الگوریتم برای محاسبه‌ی تبدیل فوریه، تبدیل فوریه سریع (FFT) است که تقریباً در زمان خطی اجرا می‌شود و آن را به ابزاری ضروری برای بسیاری از کاربردها تبدیل کرده است. با این حال، امروزه، زمان اجرای الگوریتم FFT دیگر به اندازه‌ی کافی سریع نیست، به ویژه برای مسائل کلان داده که هر مجموعه داده می‌تواند چند ترابایت باشد. از این رو، الگوریتم‌های سریع‌تری که در زمان زیرخطی اجرا می‌شوند، یعنی حتی از تمام نقاط داده نمونه‌برداری نمی‌کنند، ضروری شده‌اند.

این کتاب با توسعه‌ی الگوریتم‌های تبدیل فوریه خلوت (Sparse Fourier Transform) و ساخت سیستم‌های کاربردی که از این الگوریتم‌ها برای حل مسائل کلیدی در شش کاربرد مختلف استفاده می‌کنند به این مشکل می‌پردازد: شبکه‌های بی‌سیم، سیستم‌های موبایل، گرافیک کامپیوتری، تصویربرداری پزشکی، بیوشیمی و مدارهای دیجیتال.

این کتاب نسخه ویرایش شده‌ی رساله‌ای است که برنده‌ی جایزه‌ی رساله‌ی دکتری ACM در سال 2016 شد.

The Fourier transform is one of the most fundamental tools for computing the frequency representation of signals. It plays a central role in signal processing, communications, audio and video compression, medical imaging, genomics, astronomy, as well as many other areas. Because of its widespread use, fast algorithms for computing the Fourier transform can benefit a large number of applications. The fastest algorithm for computing the Fourier transform is the Fast Fourier Transform (FFT), which runs in near-linear time making it an indispensable tool for many applications. However, today, the runtime of the FFT algorithm is no longer fast enough especially for big data problems where each dataset can be few terabytes. Hence, faster algorithms that run in sublinear time, i.e., do not even sample all the data points, have become necessary.

This book addresses the above problem by developing the Sparse Fourier Transform algorithms and building practical systems that use these algorithms to solve key problems in six different applications: wireless networks; mobile systems; computer graphics; medical imaging; biochemistry; and digital circuits.

This is a revised version of the thesis that won the 2016 ACM Doctoral Dissertation Award.