Добеши: всплеск, у которого есть и гладкость, и место

Развилка

К середине XX века выбор выглядел так.

Тригонометрическая система: базисные функции бесконечно гладкие, коэффициент означает точную частоту — но не говорит ничего о месте. Система Хаара: коэффициент точно указывает место — но базисные функции разрывны, и гладкую функцию приходится описывать множеством ступенек.

И взять всё сразу нельзя — это запрещено принципом неопределённости: функция и её преобразование ФурьеЖозеф Фурьефранцузский математик, физик и префект Изера · 1768–1830Утверждал, что любую функцию можно сложить из синусов, — и был не прав ровно настолько, чтобы математике понадобилось сто лет и три новые теории, чтобы разобраться. не могут быть одновременно сосредоточены, произведение «ширины по времени» на «ширину по частоте» ограничено снизу. Неравенство буквально то же самое, что у Гейзенберга; в теории сигналов его сформулировал Габор в 1946 году.

Значит, вопрос не «как получить всё», а «каков наилучший компромисс — и может ли он быть ортонормированным базисом».

Что было к 1988 году

Морле (геофизик, искавший нефть) в конце 1970-х придумал раскладывать сейсмические записи по сжатым и сдвинутым копиям одного «всплеска»; вместе с Гроссманом они построили непрерывное вейвлет-преобразование.

Мейер (1986) построил гладкий ортонормированный вейвлет-базис — но его функции, хоть и быстро убывают, нигде не обращаются в нуль тождественно.

Малла (1988) придумал кратномасштабный анализ — общую машинку для построения таких базисов.

Не хватало последнего: гладкий и ортонормированный и с конечным носителем, то есть строго равный нулю вне отрезка. Без этого алгоритм не будет конечным.

Ответ

Ингрид Добеши в 1988 году показала, что такие базисы существуют, и предъявила целое семейство: носитель длины $2N-1$, $N$ нулевых моментов, гладкость растёт с $N$. При $N=1$ получается система ХаараАльфред Хаарвенгерский математик · 1885–1933Построил базис из ступенек, у которого коэффициент говорит не обо всей функции, а о месте, — вейвлет за семьдесят лет до вейвлетов. А через двадцать три года придумал меру на группе, из которой немедленно….

Приём — не писать функцию, а писать фильтр. Масштабирующая функция задаётся уравнением

$$\varphi(x)=\sqrt{2}\,\sum_{k}h_{k}\,\varphi(2x-k),$$

в котором она стоит в обеих частях: функция определена через саму себя, а конечный набор чисел $h_{k}$ подбирается так, чтобы решение было ортонормированным и достаточно гладким. Для четырёхкоэффициентного случая

$$h=\frac{1}{4\sqrt{2}}\Big(1+\sqrt{3},\ \ 3+\sqrt{3},\ \ 3-\sqrt{3},\ \ 1-\sqrt{3}\Big).$$

У этих функций нет формулы. Они существуют, непрерывны, ортонормированы — а нарисовать их можно только итерациями, и получается изломанный самоподобный график. Отметим перекличку: пространство Цирельсона, точка на этой же линии, тоже определено через себя и тоже не имеет формулы. XX век научился строить объекты, которые можно задать только рекуррентно.

Зачем это

Быстрое вейвлет-преобразование требует $O(N)$ операций — быстрее, чем $O(N\log N)$ у БПФ, и это, между прочим, соседний коридор той же лаборатории.

Из приложений: стандарт сжатия изображений JPEG 2000; архив отпечатков пальцев ФБР, переведённый на вейвлетное сжатие в 1993 году; подавление шума пороговой обработкой коэффициентов; медицинская томография. Сама Добеши позже применила вейвлет-анализ мазков к атрибуции живописи.

Мюррей-Хилл

Небольшой городок в Нью-Джерси на нашей карте встречается уже в четвёртый раз: Шеннон с теорией информации, БПФ, скетчи — и вейвлеты. Bell Labs полвека была местом, где математика попадала в технику быстрее, чем в журналы.

Человек

Ингрид Добеши (род. 1954, Хаутхален, Бельгия) — физик по образованию, защитилась в Брюссельском свободном университете в 1980-м. В Bell Labs работала с 1987 по 1994 год, затем стала первой женщиной — полным профессором математики в Принстоне, с 2011 года работает в Дьюкском университете. В 2011–2014 годах — первый президент-женщина Международного математического союза за всю его историю.

Её «Ten Lectures on Wavelets» (1992) — одна из самых цитируемых математических книг конца XX века.

Чем кончается линия

От притяжения сфероида в 1782 году до базиса, у которого нет формулы, — двести шесть лет. Всё это время речь шла об одном: разложить сложное по простому. Менялось только то, что считать простым — многочлены, синусы, ступеньки, всплески, — и что считать разложением: сначала удобную выкладку, потом ортогональную проекцию в бесконечномерном пространстве, потом алгоритм, работающий за линейное время.

Функциональный анализ и есть тот язык, на котором видно, что это один сюжет. Функция стала точкой; множество функций — пространством с длиной, углом и размерностью; ортогональная система — системой координат в нём. А вопрос «какие координаты выбрать» перестал быть математическим и стал инженерным — и на ответе, найденном в Мюррей-Хилле, держится изрядная часть того, что лежит у вас в кармане.