Presentation #003 (Live Form University of Michigan)

The Walsh-Hadamard Transform (WHT) is one of the most important linear transformations in signal processing, with applications in image and video compression and quantum computing. As with the Discrete Fourier Transform, a divide-and-conquer approach can compute the N-dimensional WHT in time O(N log N). In many applications in signal processing, however, it is expected that the transformed signal is roughly sparse, in the sense that all but up to k of the coefficients are nearly zero. Our algorithm can estimate the sparse transform in time close to the optimal O(k log N) and can be made deterministic. To design the algorithm, techniques from compressed sensing have been used, such as bipartite expander graphs obtained from linear list decodable codes. This talk is based on joint work with Piotr Indyk.

Bio: Mahdi Cheraghchi is an Assistant Professor of Computer Science and Engineering at the University of Michigan, Ann Arbor. Before joining U of M, he was on the faculty of Imperial College London, UK, where he maintains an honorary position. He held post-doctoral appointments at UC Berkeley, MIT, CMU, and the University of Texas at Austin. He obtained his B.Sc. degree from the Sharif University of Technology and M.Sc. and Ph.D. degrees from EPFL. He is broadly interested in all theoretical aspects of computer science, especially the role of information and coding theory in cryptography, complexity, algorithms, and high-dimensional geometry. He is a senior member of the ACM and IEEE.

تبدیل والش-فوریه یا هادامارد از مهم‌ترین تبدیل‌های خطی در پردازش سیگنال است، با کاربردهایی از قبیل فشرده‌سازی تصویر و الگوریتمهای کوانتومی. همانند تبدیل فوریه، یک الگوریتم «تقسیم و حل» می‌تواند تبدیل یک بردار N بعدی را در زمان متناسب با N log N محاسبه کند. در بسیاری از کاربردها مانند فشرده‌سازی سیگنال، انتظار می‌رود که داده‌ها در فضای فرکانس نزدیک به تُنُک باشد، به این مفهموم که به جز حداکثر k درایه، باقی درایه‌ها نزدیک به صفر هستند. الگوریتم داده شده در این تحقیق قادر است در چنین شرایطی تخمینی از تبدیل را در زمان تقریبا متناسب با k log N به دست آورد. برای ساخت این الگوریتم از تکنیک‌های «سنجش فشرده» استفاده می‌کنیم، به همراه گراف‌هایی که از کُدهای خطی با قابلیت تصحیح بالای خطا به دست می‌آیند. این تحقیق مشترک با Piotr Indyk است.

سخنران: مهدی چراغچی استادیار علوم و مهندسی کامپیوتر در دانشگاه میشیگان است. پیشتر او در هیات علمی همین رشته در کالج سلطنتی لندن بود. دوره‌ی لیسانس را در دانشکده‌ی مهندسی کامپیوتر صنعتی شریف، فوق لیسانس و دکتری را در موسسه پلی‌تکنیک فدرال لوزان و دوران پسادکتری را در دانشگاه‌ تگزاس در آستین، کارنگی ملون، انستیتو تکنولوژی ماساچوست، و دانشگاه کالیفرنیا، برکلی گذراند. او عضو ارشد IEEE و ACM است.