4.2. Алгоритм быстрого преобразования Хаара
Согласно табл. 3.5 матрица преобразования Хаара может быть записана так:
Пользуясь теоремами § 4.1, преобразуем эту матрицу в произведение слабо заполненных матриц.
Прежде всего заметим, что из суммы матриц (4.19) можно вынести диагональную матрицу
где 
— номер старшего равного единице разряда в двоичном представлении номера строки матрицы
так что
Для упрощения дальнейших выкладок обозначим сумму в правой части (4.22) HAR. Выделим в этой сумме последнее слагаемое с номером 
и преобразуем оставшуюся сумму:
Воспользовавшись теоремой 3 § 4.1 для кронекеровских подматриц в (4.27) и заменив 
получим
и далее по теореме 1 § 4.1
Формула (4.25) является рекуррентным выражением матрицы Хаара. Воспользовавшись ею для выражения матрицы 
через матрицу 
получим
Для дальнейших преобразований используем свойство (4.5) прямой суммы матриц, из которого в данном случае вытекает, что
или, поскольку 
Поступая и далее таким же образом, окончательно получаем
Таким образом, матрица Хаара представлена в виде произведения 
слабо заполненных матриц. В каждой 
матрице такого произведения 
строк с только двумя отличными от нуля элементами и 
строк с только одним отличным от нуля элементом.
Рис. 4.2.
Поэтому умножение матрицы-столбца на такую матрицу требует 
операций сложения или вычитания. Общее число операций сложения — вычитания, очевидно, равно
Кроме того, умножение на диагональную матрицу
требует 
операций умножения. Таким образом, количество операций, требуемых для быстрого преобразования Хаара, пропорционально длине преобразуемой последовательности. Быстрое преобразование Хаара — самое быстрое из используемых.
Для наглядности алгоритмы быстрых преобразований удобно представлять в виде графа, в узлах которого располагаются исходные отсчеты сигнала и результаты вычислений, а ребра связывают суммируемые величины и результат суммирования. Числа при ребрах указывают коэффициент, на который умножается величина в узле, из которого исходит данное ребро (единица не показывается). Такой граф быстрого преобразования Хаара, соответствующий формуле (4.29), показан на рис. 4.2 для 
Обратное преобразование Хаара можно представить как произведение транспонированной матрицы Хаара на матрицу-столбец:
Поскольку для транспонирования произведения матриц выполняется соотношение [4]
а для прямой суммы — соотношение (4.6), то
