Конференція Високопродуктивні обчислення, Київ, 13-15 жовтня 2014

Швидше за перетворення Фур’є

Перетворення Фур’є — одне з основних понять у інформаційних науках. Це метод представлення нерегулярного сигналу, такого як напруга у мережі, у вигляді комбінацій чистих частот. Алгоритм широко застосовується для перетворення сигналів, стиснення зображень та аудіо файлів, розв’язання диференціальних рівнянь, оцінок вартості акцій тощо.

Причина, чому перетворення Фур’є стало таким популярним — розробка у середині 60-х років минулого століття алгоритму швидкого перетворення Фур’є (FFT), який дозволив проводити перетворення Фур’є у реальному часі. З тих пір, як FFT був запропонований, люди не припиняли пошук ще швидшого алгоритма.

На Симпозіумі з дискретних алгоритмів (SODA) минулого тижня група дослідників з Массачусетського технологічного інституту запропонувала новий алгоритм, який для широкого кола важливих застосувань є швидшим за FFT. За певних обставин можна отримати десятикратне збільшення швидкості. Новий алгоритм може виявитись особливо корисним для стиснення зображень, наприклад, це може дозволити портативним пристроям швидко обмінюватись великими файлами через безпровідну мережу з меншими витратами енергії та мережевого трафіку.

Як і FFT, новий алгоритм працює з цифровим сигналом, він розкладає його у зважену суму набору частот. Частотами, які мають низьку вагу, нехтують без суттєвої втрати точності. Ось чому перетворення Фур’є таке корисне у стисненні інформації. Зображення 8х8 точок можна вважати вибіркою з 64 вимірювань, тобто сумою 64 різних частот. Але, як зазначають дослідники, емпіричні дані свідчать, що у середньому 57 частот можна відкинути з мінімальною втратою якості зображення.

Надважкий дивізіон

Сигнали, які перетворення Фур’є включає у відносно малу кількість частот з великою вагою, називаються «розсіяними». Новий алгоритм визначає вагу найбільш важливих частот. Чим більше розсіяний сигнал, тим більше прискорення досягає новий алгоритм. Дійсно, якщо сигнал досить розсіяний, алгоритм може зробити невелику вибірку з нього замість повної обробки.

«Більшість нормальних сигналів у природі розсіяні»,— стверджує Діна Катабі, одна з розробників нового алгоритму. Розглянемо, для прикладу, запис камерної музики. Сукупний сигнал у кожен момент часу складається лише зі звуків кількох інструментів, кожен грає по одній ноті. З іншого боку, запис усіх можливих інструментів, які грають усі можливі ноти одночасно, не буде розсіяним, але цей сигнал нікому не цікавий.

Новий алгоритм, розроблений професорами Катабі та Пьотром Індиком з МТІ, оснований на двох ключових ідеях. Перша — поділ сигналу на вужчі шматки так, щоб кожен шматок у загальному випадку містив лише одну частоту з великою вагою.

У обробці сигналів основним інструментом для ізоляції певних частот є фільтр. Але у фільтрів можуть бути розмиті межі. Одні частоти будуть проходити майже неушкодженими, частоти біля меж діапазону будуть трохи ослабленими, і так далі до повного зникнення сигналу.

Якщо так станеться, що одна з частот з великою вагою знаходиться на краю фільтра, може виникнути ситуація, що після ослаблення її неможливо буде розпізнати. Тому першим завданням дослідників став пошук ефективного обчислювального способу сполучення фільтрів так, щоб вони могли накладатись, гарантуючи, що жодна з частот у цільовому діапазоні не буде надмірно послаблюватись, але при цьому межі між шматками спектра залишаються досить чіткими.

Обнулення

Після відокремлення шматочків спектра необхідно визначити найбільш важливу частоту. Спочатку пропонувався спосіб повторного поділу спектра на все менші шматки, залишаючи лише ті, у яких максимальна концентрація сигналу. Пізніше було знайдено значно ефективнішу методику, яка схожа на спосіб обробки сигналів у стільникових мережах формату 4G.

Схожий алгоритм для покращення FFT для розріджених сигналів вже пропонувався двома вченими з Мічіганського університету, професорами Анною Гільберт та Мартіном Штрауссом. «Деякі попередні роботи, включаючи мою з Анною Гільберт, покращують перетворення FFT для випадків, коли коефіцієнт розрідження (кількість частот з великою вагою) значно менший за розмір вибірки»,— визнає Штраусс. — «Натомість алгоритм, запропонований у МТІ має значно ширше коло випадків, у яких він може перемогти звичайний FFT за швидкістю обробки. Навіть якщо коефіцієнт розрідження наближається до розміру вибірки, новий алгоритм дає невелике прискорення у порівнянні з FFT».

FFT Гумор

Теги: математика

Матеріали за темою:

Коментарі