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

[ded_maxim]

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

Comments

[ygam.livejournal.com]

А мне кажется полезным. Ведь если сжатие такое lossy, что от данных ничего не остается, то сложность результата равна нулю. Можно построить график потери сложности относительно степени сжатия.

[scriptum.livejournal.com]

Почему бесполезно? Зная максимально допустимую потерю информации, можно подобрать секретаршу, измеряя ее череп. См. здесь (http://www.livejournal.com/users/bo_ba/109398.html?nc=4)