колмогоровская сложность для сжатия с потерями

[ded_maxim]

А вот, оказывается, японцы Мурамацу и Каная придумали обобщение сложности по Колмогорову для lossy compression! Определяется для данной последовательности X^n = (X_1,...,X_n) и для заданного уровня потерь D как минимальная длина программы для универсальной машины Тьюринга, с помощью которой можно получить аппроксимацию X^n с точностью D. Если X^n это кусок стационарного эргодического процесса, то эта сложность равна примерно nR(D), где R(D) -- функция зависимости скорости передачи от искажения по Шеннону. (Связь с эпсилон-энтропией etc.) Круто (хотя и совершенно бесполезно с практической точки зрения)!

Comments

[http://users.livejournal.com/_qwerty/]

Причем тут оптимальность? Нигде в дискуссии выше оптимальность не фигурировала.

[ded-maxim.livejournal.com]

В самом посте фигурирует функция R(D), предписывающая минимальное число уровней квантования при заданном среднем значении функции потерь.

[http://users.livejournal.com/_qwerty/]

Кстати, а каково определение оптимальности для потерьного сжатия? Оно должно быть асимпотически точное и асимпотитически же с нулевой избыточностью?

И чем вам интересны именно оптимальные алгоритмы?

[ded-maxim.livejournal.com]

Нет, потерьное сжатие в общем случае не может быть асимптотически точным. Оптимальность определяется так: пусть k заданное число уровней квантования, пусть P распределение входного сигнала X, и пусть d(x,y) - функция потерь при передаче входного символа x выходным символом y. Тогда оптимальное k-уровневое квантование X определяется как любая функция q, отображающая множество всех X в некоторое подмножество всех Y, состоящее из k выходных символов, так что мат. ожидание d(X,q(X)) по P достигает минимума. Теперь рассмотрим ситуацию когда мы берем n-блоки входных символов и отображаем их в n-блоки выходных символов; берем предел минимума (1/n) E[d(X^n,q(X^n))] по всем квантованиям с k уровнями на входной символ при n стремящемся к бесконечности. Доказано, что этот предел будет равен шенноновской функции D(R) зависимости среднего уровня потерь от скорости передачи, где R = log k это объем квантования в битах на входной символ. Еще можно рассмотреть случай квантования с переменной скоростью передачи.

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

[http://users.livejournal.com/_qwerty/]

А действительно ли хороша эта модель на практике? Насколько я помню свои упражнения, по крайней мере для беспотерьного сжатия асимптотическая оптимальность алгоритма вовсе не означает, что он выдающимся образом жмет конечные последовательности. А модель источника и кодирования можно и другую построить.