Достижимые компромиссы между сложностью и эффективностью при сжатии данных с потерями

Представлено несколько результатов об оптимальном соотношении между сложностью и эффективностью при сжатии данных с потерями. Первый из них показывает, что для источника без памяти со скоростью как функцией искажения $R(D)$ и ограниченной мерой искажения можно достичь точки $(R(D)+\gamma,D+\varepsilon)$ на кривой скорости как функции искажения при постоянном времени декодирования на символ и времени кодирования на символ, пропорциональном $(\lambda_1/\varepsilon)^{\lambda_2/\gamma^2}$, где $\lambda_1$ и $\lambda_2$ – константы, зависящие от источника. Второй результат состоит в том, что эта же точка достигается при постоянном времени декодирования и времени кодирования на символ, пропорциональном $(\rho_1/\gamma)^{\rho_2/\varepsilon^2}$. Из этих результатов вытекает, что для любой сколь угодно медленно возрастающей, но неограниченной функции $g(n)$ существует последовательность схем сжатия с потерями с длиной блока $n$, сложностью кодирования $O(ng(n))$ и сложностью декодирования $O(n)$, асимптотически достигающая точки $(R(D),D)$ при растущей длине блока. Также показано, что если алфавит воспроизведения конечен, то для любого заданного $R$ существует универсальная схема сжатия с потерями со сложностью кодирования $O(ng(n))$ и сложностью декодирования $O(n)$, асимптотически достигающая точки $(R,D(R))$ для любого стационарного эргодического источника с искажением как функцией скорости $D(\cdot)$.