Ссылки за день.

[thesz]

На слешдоте, что ли, вечерком наткнулся на Сжатые Измерения.

Буквально, в статьях по ссылкам из странички на Википедии выне приводится пример, как можно передать всего 1/40 точек изображения и получить практически полное восстановление.

Пока шёл домой, кое-что из этого понял. Правда, не могу сказать, что до конца и хорошо, но понял. ;)

Плюс,

Comments

[thedeemon]

Странная штука эти compressed sensing. Ссылаются в основном сами на себя, в статьях много восторгов (та, что по первой ссылке на wired.com - вообще нечто), при этом, как я понимаю, речь идет всего-лишь об интерполяции с помощью регуляризации.

[thesz]

Странная. Но интересная.

До меня, например, по прочтению дошло, как же можно однопиксельной камерой что-либо снимать.

[thedeemon]

Если для получения одной картинки они делают тысячи однопиксельных снимков в разных направлениях, то это похоже на один снимок с тысячами пикселей. Дальше данные интерполируются их методом и получается размазня.

Местами они упоминают, что их подход напоминает сжатие JPEG, когда передается лишь часть данных в частотном домене, потому что они якобы sparse. Но ведь это неправда, там исходные данные вовсе не sparse, а просто енкодер их делает таковыми, сильно загрубляя высокие частоты, просто потому что человек их потерю плохо замечает. Т.е. сравнение некорректно, потому и получается, что восстанавливая картинку по 10% точек, они получают намного худший результат, чем при сжатии в 10 раз JPEG'ом. Поэтому "практически полное восстановление по 1/40 точек" возможно лишь для очень небольшого класса изображений (вроде известной картины Малевича) и невозможно для обычных фотографий (см. картинку с обезьяной).

[ext_8865]

Данные правда sparse в определенном базисе, в смысле большая часть энергии в нижних частотах, а верхние близки к 0 в основном.

А у этих чуваков идея в том, что в обычном случае мы действуем немного глупо -- получаем 100000 измерений, а потом оставляем от них 1000 вейвлет-коэффициентов, тогда как можно снять 3000 картинок однопиксельной камерой со случайной маской, и из них эту 1000 коэффициентов можно очень точно найти линейным программированием.