Всплески Ингрид Добеши

Тридцать лет назад имя Ингрид Добеши было на устах у всех, кто соприкасался с теорией функций и теорией приближений. Молодая женщина, профессор Принстонского университета, сумела завершить труд нескольких поколений математиков и построить систему функций, с успехом заменяющую систему синусов и косинусов (систему Фурье), для преобразования функций и разложений их в ряды. О чудодейственных свойствах новой системы, получившей название wavelets, вейвлеты (дословно — «волночки», в отличие от «волн» — синусов и косинусов), постоянно заходила речь и на семинарах и в университетских кулуарах. Теоретики сразу применили «волночки» к нескольким известным задачам функционального анализа, физики с их помощью строили решения уравнений в частных производных, а вычислители усовершенствовали метод Галеркина, получив знаменитый теперь вейвлет-Галеркин метод. Всё это было, так сказать, побочными результатами. Главное же предназначение новой системы функций — в тео­рии обработки и хранения сигналов. Именно там они совершили настоящую революцию, позволяя сжимать информацию в ­100–150 раз без существенной потери качества. Разработанный впоследствии формат JPEG 2000 был основан на функциях Добеши.

В русскоязычной литературе прижился термин «всплески», предложенный К. И. Осколковым. В середине 1990-х в России литературы по этой теме сильно не хватало даже специалистам: русскоязычной еще не было, англо­язычная была недоступна. Книга Добеши “Ten lectures on wavelets” («Десять лекций по всплескам») была на руках в двух-трех экземплярах, но их владельцы неохотно давали их даже на копирование. Еще один экземпляр видели в «Букинисте» на Кузнецком мосту за сто долларов — нереальные по тем временам деньги (это и сейчас недешево для книги). Поэтому уже в 1994 году профессор мехмата МГУ С. Б. Стечкин объявил спецкурс «Введение в теорию всплесков». Первую лекцию он начал, обратившись к аудитории:

«Откройте тетрадки и запишите:

Теорема 1. Всплески очень важны в науке и в жизни.

Все записали теорему?»

Слушатели со скрытым недоумением переглянулись. Стечкин невозмутимо продолжал:

«Доказательство. На Всемирных математических конгрессах, проводимых раз в четыре года, самым выдающимся математикам предлагается сделать пленарный доклад. Продолжительность — ровно один час, исключений нет. На последнем конгрессе в Цюрихе Добеши было дано два часа. Теорема доказана».

Что же сделала Ингрид Добеши, и почему это вызвало такой резонанс? Сначала нам необходимо напомнить основные положения теории обработки сигналов (signal processing). Сигналы бывают непрерывные — это функции (для определенности — на отрезке [0, 1]) — и дискретные — это просто наборы из N чисел, или вектора в пространстве RN. Можно переходить от одной формы к другой: функцию f (t) заменить на дискретный сигнал, сняв ее значения на равномерной сетке xk = f (k/N), k = 0,…, N–1; либо, наоборот, из дискретного сигнала x = (x0,…, xN–1) сделать непрерывную функцию, задав значения в узлах разбиения f (k/N) = xk и соединив их, например, ломаной. Размерность сигнала N может быть достаточно велика. Для хранения фотографии среднего качества, если хранить ее «по точкам», нужно N порядка 107. Конечно, столь огромные массивы данных неудобны для хранения и передачи. Как обойтись меньшим числом? Основная идея заключается в том, что нам нужны, как правило, не все сигналы, а только какой-то определенный класс, и его можно описать значительно меньшим, чем N, числом параметров. Представим себе, например, что мы имеем дело только с квадратичными функциями f (t) = at2 + bt + c. Тогда для хранения сигнала нужны всего три числа — a, b и c. В реальности, имея дело, скажем, с аудио- или с видеосигналами, нам нужен класс гладких или кусочно-гладких функций. Гладкие функции могут быть хорошо приближены небольшим числом базисных «простых» функций. Выбор базисных функций для сигналов определенного класса — одна из главных задач теории обработки сигналов. Можно в качестве базиса выбрать степенные функции 1, t, t2, … и приближать сигнал полиномами. Но технически это неудобно: высокие степени становятся исчезающе малыми на всем интервале (0, 1), за исключением маленькой окрестности единицы. Гораздо лучше приближать тригонометрическими полиномами и использовать тригонометрические базисные функции cos 2πkt и sin 2πkt. Таким образом, для хранения гладких сигналов берется следующая схема: дискретный сигнал заменяется непрерывным, раскладывается в ряд Фурье, после чего оставляют только первые k коэффициентов ряда, остальные выбрасываются. Число k зависит от предполагаемой гладкости сигнала и от точности приближения. Так, при N = 107, для приближения сигнала класса C1 (с непрерывной производной) с максимальной ошибкой ε = 10–3 понадобится хранить порядка 106 коэффициентов. Таким образом, объем информации сжат в 10 раз без существенной потери качества. Неплохо! Кроме того, для вычисления коэффициентов Фурье был разработан алгоритм быстрого преобразования Фурье, который затрачивает порядка N ln N операций (для вычисления N коэффициентов). Метод Фурье служит верой и правдой более двух столетий, однако, с развитием компьютерной техники и увеличением объемов данных проявился ряд его недостатков. Главный: разложение в ряд Фурье неустойчиво к шумам. Шум — это функция с маленьким носителем и большим значением. Это щелчок, треск. Наличие шумов при переписывании с магнитных носителей и передаче сигналов неизбежно. Прибавление шума меняет сразу все коэффициенты Фурье равномерно. После сохранения конечного числа коэффициентов и выполнения обратного преобразования Фурье мы получаем равномерно испорченный сигнал. После этого шум трудно локализовать и устранить. Причиной такого поведения служит то обстоятельство, что преобразование Фурье не сохраняет компактность носителя функций. Например, преобразование Фурье δ-функции Дирака — тождественная единица. Это не удивительно, поскольку система Фурье состоит из тригонометрических функций, которые сами не локализованы на прямой: они не только не финитны (не имеют компактных носителей), но и не убывают на бесконечности. Поэтому выход может быть только один: предъявить новую систему функций, которая состояла бы из быстро убывающих функций (в идеале — из финитных) и, хорошо бы, была ортогональной, как тригонометрическая. Одна такая система уже была в наличии! Это базис Хаара, построенный еще в 1909 году. Каждая функция системы Хаара принимает только значения 1 и –1 на маленьких интервалах, а за их пределами равна нулю. Более того, особая структура системы Хаара, когда все функции получаются из одной «материнской» функции с помощью целых сдвигов и двоичных сжатий, позволяет быстро вычислять все коэффициенты разложения с помощью так называемого каскадного алгоритма. Он работает быстрее быстрого преобразования Фурье — тратит порядка N операций! Но функции Хаара разрывны, и ряды разложения по этой системе сходятся медленно. Можно ли построить систему гладких функций, обладающих свойствами системы Хаара? Локализованностью и двоичной структурой?

Существует ли «гладкий Хаар»? Этот вопрос в той или иной форме стоял десятилетия. Решался он постепенно. В 1930–1940-х годах была построена система Шеннона — Котельникова, основанная на сдвигах с сжатием функции sinc t = (sin t) / t. Нашли ее скорее инженеры, чем математики, поскольку эти функции естественно возникают в электронике.

Как видим, они медленно убывают на бесконечности, как 1/t при t → ∞. Таким образом, всплески Шеннона — Котельникова, обладая хорошей гладкостью, имеют плохую локализацию (хотя и лучшую, чем у Фурье). Далее были базисы Малла, Баттла — Лемарье и др. Прорывом в 1986 году стали всплески Ива Мейера, которые, наряду с гладкостью, быстро убывали. Фактически Мейер «подправил» материнскую функцию Шеннона — Котельникова, но эта поправка потребовала новой и весьма сложной конструкции. В отличие от последних, всплески Мейера не были ­взяты «из жизни», а были полностью рукотворными. В 2017 году Ив Мейер получил за них премию Абеля. Однако всплески Мейера — это не гладкий Хаар, это скорее «быстро убывающий Шеннон — Котельников», поскольку функции Хаара не являются финитными. За задачу построения гладкого Хаара взялась Ингрид Добеши, 42-летняя сотрудница научного центра AT&T Bell Laboratory в Нью Джерси (США), только что приехавшая из Бельгии. Ее профессией была математическая физика и квантовая механика, в которой она весьма успешно себя зарекомендовала. Но на новом месте она занялась проблемами обработки сигналов и, конечно, сразу вышла на теорию всплесков. Построение финитных всплесков потребовало фактически новой теории. Вначале Добеши показала, что нужно решить масштабирующее уравнение ϕ(t) = Σnk=0 ckϕ(2t – k) — разностное уравнение на функцию ϕ с двоичными сжатиями аргумента. Коэффициенты уравнения {ck}nk=0 могут быть найдены с помощью специального соотношения на алгебраические полиномы. Добеши полностью классифицировала соответствующие полиномы, выбрав из них оптимальные. Оказалось, что для каждого n можно найти один набор коэффициентов {ck}nk=0 (на самом деле, много эквивалентных наборов, но мы здесь несколько упрощаем дело). Теперь, имея коэффициенты ck, нужно решить масштабирующее уравнение. Это оказалось чрезвычайно сложной задачей. Совместно с коллегой по AT&T Bell Lab Дж. Лагарисом она разработала матричный метод решения — линейный итерационный процесс, сходящийся к определенной самоподобной кривой. Таким образом, решения масштабирующих уравнений являются фрактальными функциями. Соответственно, и финитные всплески, кроме хааровского, являются фрактальными функциями. Они всегда имеют ограниченную гладкость на любом интервале и, следовательно, не выражаются через аналитические функции. В результате для каждого n было получено решение ϕn, а из него уже и материнская функция всплесков ψn. Эта функция так и называется — n-й всплеск Добеши. В программистской литературе она обозначается db n. Она сосредоточена на отрезке [0, 2n — 1]. Функция ψ1 — это функция Хаара. А функция ψ2 уже будет непрерывной! Напомним, что Хаар — это 1909 год, а ψ2 — 1988-й. Таким образом, путь от первого до второго всплеска Добеши длился 79 лет! Гладкость всплесков увеличивается с ростом n. Замечательная теорема, доказанная Добеши, базируясь на результатах А. Коэна, гласит, что гладкость ψn не менее 0,19n. Таким образом, ­существуют всплески сколь угодно большой гладкости! В настоящее время точные значения показателей гладкости вычислены для n ≤ 40.

Говоря о Добеши, нельзя не упомянуть и еще один аспект — человеческий. Она удивительный человек, это отмечает каждый, кто имел с ней дело! Мне довелось встречаться с ней в 1998 году в Принстоне, где Добеши была профессором математики и возглавляла лабораторию обработки сигналов. Вначале я пробовал найти кого-либо из ее учеников, чтобы показать им свои результаты, но мои друзья настоятельно советовали обратиться напрямую к ней. «Это неудобно, — возражал я, — я студент из России, она всемирно известный ученый, наверняка занятой». В конце концов я написал ей электронное письмо, ожидая в лучшем случае ответа: «Как-нибудь, недельки через две, три…» Но ответ пришел быстро: «Завтра в 15:00 вам удобно?» Потом мы встречались еженедельно, я мучил ее своими результатами и своим ужасающим английским по 1–2 часа. Она всё внимательно слушала, записывала, вникала в каждую мелочь. Мне нынешнему ее корректность и доброжелательность по отношению ко мне кажутся неправдоподобными. В конце каждой встречи она решительно пресекала все мои попытки извинений: «Было очень интересно, спасибо! Теперь давайте в понедельник, вам будет удобно? Извините, раньше я не смогу».

Один философ сказал, что философией нужно заболеть, но самому этого сделать нельзя — можно только заразиться от другого человека. Думаю, что от Добеши многие заразились теорией всплесков на всю жизнь.

Владимир Протасов,
профессор, чл.-корр. РАН