Глава 5. Сжатие, быстрое преобразование, свёртка

Где стоит глава

Применения и закрытие Части VII

Глава 7.4 дала конечное ядро контроля усечений: ошибка усечения равна отброшенной хвостовой энергии, не возрастает при добавлении коэффициентов и зануляется при Парсевале. Настоящая глава снимает с этого ядра три применения — те самые, ради которых преобразование Фурье ценят на практике,— и показывает, что для Уолша каждое из них чисто рационально: сжатие (выбросить малозначимые коэффициенты), быстрое преобразование (вычислить спектр за $O(N\log N)$ вместо $O(N^2)$) и свёртка (превратить свёртку сигналов в поточечное произведение спектров). После них Часть VII закрывается: рациональный гармонический анализ построен от коэффициентов до свёртки, а трансцендентная тригонометрия оставлена честной границей.

Что доказано — и что граница

Доказано над ℚ, без аксиом.¹ Ошибка усечения по первым $K$ коэффициентам равна сумме квадратов отброшенных и монотонна по $K$; для Уолша она контролируется равенством Планшереля; полосно-ограниченный сигнал (спектр в первых $K$ модах) восстанавливается без потерь. Быстрый Уолш — рекурсивная бабочка — даёт в точности то же, что матричное преобразование, для всех $N=2^k$. И теорема о свёртке $H(f\ast g)=(Hf)\cdot (Hg)$ доказана для всех $2^k$.

Чего глава не утверждает. Сложность $O(N\log N)$ сама по себе — операционное свойство (счёт шагов), а не равенственное тождество; доказано равенство быстрого и матричного преобразований, а не оценка стоимости. Оптимальное $K$-членное сжатие — отбор $K$ наибольших по величине коэффициентов — требует слоя сравнения и сортировки; доказанное ядро — усечение по первым $K$. Непрерывная и комплексная свёртки — честная граница Главы 7.3.

E/R/R-каркас главы

Каркас в порождающем порядке Rules $\to$ Roles $\to$ Elements; полный разбор — в § «Постановка и разбор».

Rules (Правила, $\leftrightarrow$ L5). Ошибка сжатия = сумма квадратов отброшенных коэффициентов (монотонна); полосно-ограниченный сигнал даёт нулевой хвост; быстрый Уолш $=$ матричное преобразование; $H(f\ast g)=(Hf)\cdot (Hg)$.

Roles (Роли, $\leftrightarrow$ L4). Сжатие — роль-усечение; быстрый Уолш — роль-алгоритм; свёртка — роль-произведение; $O(N\log N)$ — роль-стоимость (операционная); отбор по величине — роль, требующая сортировки.

Elements (Элементы, $\leftrightarrow$ L1$+$P4). Рациональные коэффициенты $c_i$, амплитуды $f,g$, XOR-индексы, конечные суммы, $N=2^k$; завершённый спектр и стоимость как метаобъект — вне элементов (P4).

Сжатие как спектральное усечение

Ошибка сжатия есть отброшенная энергия

Сжатие спектрального типа просто: вычислить спектр, оставить первые $K$ коэффициентов, отбросить остальные. Качество сжатия — это ошибка восстановления, и она в точности есть отброшенная хвостовая энергия:

$$\text{norm}{f}^2=\underset{\text{сохранено}}{\underbrace{\sum _{i<K}{c}_i^2}}+\underset{\text{отброшено}}{\underbrace{\sum _{K\le i<N}{c}_i^2}},$$

так что ошибка равна второй сумме — ровно тому, что усечение выкинуло.² Захваченная энергия монотонно растёт с $K$ (а ошибка убывает) — то же свойство, что несло конечное ядро сходимости в Главе 7.4. Для Уолша всё это точно над ℚ: и коэффициенты, и энергии — рациональные конечные суммы. Оговорка о шкале: здесь $c_i$ — коэффициенты в нормированной ортонормированной шкале (Глава 7.1); для сырого спектра Уолша $(Hf{)}_i$ та же формула читается с масштабом $N$, ибо ${\sum }_i(Hf{)}_i^2=N\text{norm}{f}^2$ (Планшерель, Глава 7.2).

Полосно-ограниченный сигнал: сжатие без потерь

Особый случай делает смысл сжатия предельно ясным. Если спектр сигнала сосредоточен на первых $K$ модах (относительно выбранного порядка Уолша) — то есть $c_i=0$ при $i\ge K$,— то отброшенная энергия равна нулю, и первые $K$ коэффициентов восстанавливают сигнал без потерь: захваченная энергия совпадает с полной.³ Это и есть точная компактизация: где сигнал беднее полного спектра, там сжатие даром.

Честная граница: первые $K$ против лучших $K$

Здесь проходит важная граница, которую легко не заметить. Доказанное ядро — усечение по первым $K$ коэффициентам (индексы $0,\dots ,K-1$): оно точно, рационально и конечно. Оптимальное же сжатие в $K$ слагаемых — удержать $K$ наибольших по модулю коэффициентов, где бы они ни стояли,— требует их сравнить и отсортировать, то есть добавить слой сравнения/выбора. Этого слоя доказанное ядро не строит; смешивать <<первые $K$>> и <<лучшие $K$>> — ошибка.

Ошибка сжатия = отброшенная энергия — точное рациональное тождество (для Уолша), а полосно-ограниченный сигнал сжимается без потерь. Доказанное ядро — усечение по первым $K$; отбор лучших $K$ по величине — отдельный слой сортировки, честная граница.

Быстрое преобразование: алгоритм равен матрице

Матричное преобразование Уолша считает $N$ коэффициентов, каждый — сумма из $N$ слагаемых: $O(N^2)$ операций. Но рекурсивная структура Сильвестра (Глава 7.2) даёт бабочку: преобразование размера $2N$ собирается из двух преобразований половин сложениями и вычитаниями ($\text{lo}+\text{hi}$ и $\text{lo}-\text{hi}$), а это — $O(N\log N)$ операций. Так устроен быстрый Уолш (аналог быстрого преобразования Фурье).

Доказано главное: быстрая бабочка даёт в точности то же, что матричное преобразование, для всех $N=2^k$.⁴ То есть оптимизация не меняет результата: процесс-алгоритм и матрица-определение совпадают как функции.

Быстрый Уолш — процесс-алгоритм, доказанно равный матричному преобразованию (точно над ℚ, все $2^k$). Сама оценка $O(N\log N)$ — операционное свойство (счёт шагов), читается поверх доказанного равенства, но не входит в равенственное ядро.

Свёртка: печать Фурье

Венчает применения теорема о свёртке — та самая <<печать Фурье>>, ради которой преобразования и применяют к сигналам: свёртка переходит в поточечное произведение. Для Уолша это диадическая (XOR-) свёртка

$$(f\ast g)(n)=\sum _{m<N}f(m)g(n\oplus m),$$

а теорема утверждает, что её спектр есть поточечное произведение спектров:

$$H(f\ast g)=(Hf)\cdot (Hg),$$

и это доказано для всех $N=2^k$ над ℚ.⁵ Практический смысл прямой: свёртку — операцию квадратичной стоимости — можно посчитать как преобразование, поточечное умножение и обратное преобразование. Поскольку ненормированный Уолш удовлетворяет $H^2=N\cdot I$, обратный шаг есть $H/N$: преобразовать $f,g$, перемножить спектры, применить $H$ и разделить на $N$; с быстрым Уолшем всё это — $O(N\log N)$.

Доказательство и есть кульминация группового взгляда Главы 7.2: свёртка переходит в произведение потому, что функции Уолша — характеры группы $(Z_2^n,\oplus )$, а характеры превращают групповую операцию $\oplus$ в умножение. Печать Фурье у Уолша — рациональная.

Теорема о свёртке $H(f\ast g)=(Hf)\cdot (Hg)$ — печать настоящего Фурье — у Уолша выполнена точно над ℚ для всех $2^k$. Её источник — характерное свойство группы; её следствие — быстрая свёртка через быстрое преобразование.

E/R/R-разбор: применения как роли над преобразованием

Постановка и разбор

Разберём систему применений — сжатие, быстрое преобразование, свёртку — в терминах E/R/R. Оговорка об уровне: это содержательная интерпретация трёх конструкций над уже построенным преобразованием Уолша, а не объект System в коде; разбор читает шапки опорных файлов, а не приписывает им новых утверждений.

Rules (Правила, $\leftrightarrow$ L5). Правила применений надстроены над преобразованием: ошибка сжатия $=$ отброшенная энергия (монотонна по $K$); полосно-ограниченный сигнал $\Rightarrow$ нулевой хвост; быстрый Уолш $=$ матричное преобразование; $H(f\ast g)=(Hf)\cdot (Hg)$. Универсальный слой — L1–L5; конкретный — рекурсия Сильвестра и групповой характер.

Roles (Роли, $\leftrightarrow$ L4). Сжатие — роль-усечение (удержать первые $K$); быстрый Уолш — роль-алгоритм (тот же результат, меньшая стоимость); свёртка — роль-произношение групповой операции через умножение. $O(N\log N)$ — роль-стоимость (операционная, поверх равенства); <<лучшие $K$>> — роль, требующая сортировки. Завершённый спектр — роль-предел.

Elements (Элементы, $\leftrightarrow$ L1$+$P4). Носители конечны и рациональны: коэффициенты $c_i\in Q$, амплитуды $f,g$, XOR-индексы, конечные суммы, $N=2^k$. Под P4 стоимость как метаобъект и завершённый спектр не суть элементы: актуальны лишь конечные данные и конечные операции.

Компонент	Что фиксирует	E/R/R
ошибка $=$ отброшенная энергия; полосно-огр. $\Rightarrow$ хвост$=0$; быстрый $=$ матричный; $H(f\ast g)=(Hf)\cdot (Hg)$	КАК устроены применения над преобразованием	Rules ($L5$)
сжатие-усечение; быстрый Уолш-алгоритм; свёртка-произведение; $O(N\log N)$-стоимость; лучшие-$K$	ЗАЧЕМ значимы носители; что операционно/граница	Roles ($L4$)
$c_i\in Q$; $f,g$; XOR-индексы; конечные суммы; $N=2^k$	ЧТО есть на каждой стадии (конечно, P4)	Elements ($L1$, P4)

{ Система сформирована корректно: каждый компонент — в одной E/R/R-категории, нет самоотнесения (P1). Существенно, что стоимость $O(N\log N)$ и отбор <<лучших $K$>> не подменяют Элементов: первое — операционная роль поверх доказанного равенства, второе — роль, требующая отдельного слоя сортировки. Доказанное ядро — равенства над конечными рациональными данными.}

Закрытие Части VII: рациональный гармонический анализ

Дуга части

Часть VII прошла гармонический анализ насквозь — и провела его, держа разделение доказанного ядра и честной границы. Глава 7.1 переформулировала L²-аппарат Части VI как теорию коэффициентов Фурье: ортонормированная система, проекция, Бессель, Парсеваль, наилучшее приближение. Глава 7.2 предъявила конкретную рациональную систему — Уолша–Адамара — с ортогональностью $H^{\mathsf{T}}H=N\cdot I$, сохранением энергии и характерами булева куба: <<Фурье без трансцендентностей>>. Глава 7.3 провела границу: тригонометрический и комплексный Фурье трансцендентны не идеей, а выбором группы. Глава 7.4 дала конечное ядро контроля усечений: ошибка усечения равна хвостовой энергии и монотонно не возрастает. Глава 7.5 сняла применения: сжатие, быстрое преобразование, свёртку.

Что доказано рационально и где граница

Доказанное рациональное ядро Части VII — над ℚ, без новых аксиом: ортогональность Уолша для всех $2^k$, дискретное сохранение энергии (Планшерель), характерное свойство ${\mathrm{w}}_i(a\oplus b)={\mathrm{w}}_i(a){\mathrm{w}}_i(b)$, неравенство Бесселя и критерий Парсеваля, наилучшее приближение, конечное ядро контроля усечений, сжатие с точной ошибкой, быстрый Уолш $=$ матричный и теорема о свёртке. Честные P4-границы, помеченные и не выданные за большее: нормировка $1/\sqrt{N}$ (рациональна лишь при чётном $k$), комплексный DFT (корни единицы, $i$), непрерывная тригонометрия, завершённый бесконечный ряд, поточечная сходимость и Гиббс, сложность $O(N\log N)$ как метаоценка, отбор лучших $K$ сортировкой.

Рациональный гармонический анализ — это анализ Фурье на булевом кубе: характеры, ортогональность, сохранение энергии, наилучшее приближение, конечное ядро контроля усечений, сжатие, быстрый алгоритм и свёртка — всё точно над ℚ. Трансцендентность входит при нормировке $1/\sqrt{N}$ и особенно при выборе группы окружности — и честно оставлена границей.

Мост к спектральным методам и физике

Часть VII не самоцель: она готовит спектральный язык для дальнейшего. Вентиль Адамара (Глава 7.2) уже есть мост в квантовые вычисления; преобразование как самосопряжённый оператор с сохранением энергии (Часть VI) ведёт к спектральным методам физического тома, где собственные значения, эволюция и наблюдаемые читаются на том же процессно-конечном языке. Уолш дал образец: настоящий гармонический анализ возможен без единой трансцендентности, если носитель выбран рационально. Тот же приём — держать конечное и рациональное ядро, а трансцендентное метить границей,— понесёт и физика.

На этом Часть VII закрыта. Следующая часть выходит за пределы гармонического анализа — к дифференциальным уравнениям на процессах,— сохраняя сквозной метод тома: всякий аналитический объект есть процесс, доводимый до любой точности, а не завершённый объект.

---

---

Часть: Часть VII. Гармонический анализ · Том: «Математика»

Навигация: ← Глава 4. Сходимость рядов Фурье в L2 · Глава 1. Задача Коши и решение как процесс — Часть VIII →

Footnotes

1. Опорные файлы (каталог src/process/): ProcessFourierCompression.v (6 утверждений), ProcessWalshCompaction.v (1), ProcessFastWalsh.v (2), ProcessWalshConvolutionGeneral.v (7); все 0 Admitted, 0 аксиом. ↩

2. В ProcessFourierCompression.v: captured$(c,K)={\sum }_{i<K}{c}_i^2$; truncation_error_eq даёт баланс captured$(c,N)=$captured$(c,K)+$хвост; captured_mono — монотонность по $K$. Для Уолша полная энергия есть $N\text{norm}{f}^2$ (Планшерель), так что ошибка контролируется Парсевалем — walsh_captured_le_energy. 0 аксиом. ↩

3. walsh_compaction в ProcessWalshCompaction.v: при $c_i=0$ для $K\le i<N$ выполнено captured$(c,N)=$captured$(c,K)$ — хвост нулевой. 0 аксиом. Точное рациональное сжатие полосно-ограниченного сигнала. ↩

4. fwht_correct в ProcessFastWalsh.v: fwht$kfi=$op_apply$(‘had‘k)f(2^k)i$ для $i<2^k$, индукцией по $k$ через блочную структуру Сильвестра. 0 аксиом. <<Быстрый $=$ матричный>> — алгоритм как процесс, равный преобразованию. ↩

5. walsh_convolution в ProcessWalshConvolutionGeneral.v: $H(f\ast g)=(Hf)\cdot (Hg)$ для всех $2^k$. Доказательство опирается на характерное свойство Уолша (had_character, Глава 7.2) и на переиндексацию конечной суммы под XOR-биекцией (`xor_perm_q_sum`, доказанную блочной рекурсией Сильвестра). 0 аксиом. ↩