Interested Article - Compressive sensing

Compressed sensing , также известное как compressive sensing , compressive sampling и sparse sampling — это методика получения и восстановления сигнала, используя знания о его предыдущих значениях, которые разрежены или сжаты. Эта область обработки сигналов существует на протяжении 40 лет, но только недавно получила широкое признание, в том числе благодаря нескольким важным результатам, сделанным Дэвидом Донохо , , и Теренсом Тао .

История

Идеи, описывающие compressive sensing , появились в 2004 году, когда Эмануель Канде, математик из Caltech , работал над проблемами изображений магнитного резонанса . Он открыл, что тестовое изображение могло быть восстановлено точно даже с данными, которые считаются недостаточными в соответствии с критерием Найквист-Шеннона . Кроме того, предшественник compressed sensing был замечен в 1970-х годах, когда сейсмологи построили изображения рефлексивных уровней в пределах земли, основанные на данных, которые, казалось, не удовлетворяли критерию Найквиста — Шеннона .

Метод

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

Compressed sensing обычно начинается с принятия ограниченного (возможно, случайного) числа выборок в базис , отличный от базиса, в котором сигнал является разреженным. Так как число выборок ограниченно, задача преобразования изображения назад в намеченную область повлекла бы за собой решение недоопределённого — то есть, есть огромное число различных изображений-кандидатов, который могут быть результатом для данной выборки, так как число выборок меньше, чем число коэффициентов в полном изображении. Таким образом, нужно ввести некоторое дополнительное ограничение, чтобы выбрать «лучшего» кандидата.

Классическое решение для таких проблем — минимизация нормы $L_{2}$ — то есть, минимизировать количество энергии в системе. Это обычно простая математика (включающая только перемножение матриц с помощью псевдообратного базиса выборки). Однако это приводит к плохим результатам для большинства практических приложений, так как неизвестные (отсутствующие в выборке) коэффициенты редко имеют нулевую энергию.

Более привлекательным решением было бы минимизировать норму $L_{0}$ , или эквивалентно максимизировать число нулевых коэффициентов в новом базисе. Однако это NP-сложная задача (она включает ) и также в вычислительном отношении неосуществима для всех, кроме самых крошечных наборов данных. Таким образом, согласно идеям Тао Теренса et al., принято минимизировать аппроксимирующую $L_{1}$ -норму, или сумму в абсолютных значениях. Задача минимума $L_{1}$ -нормы формулируется в виде задачи линейного программирования , для которой существуют эффективные методы решения. Это приводит к сопоставимым результатам использования $L_{0}$ нормы, часто приводя к результатам, когда многие коэффициенты равны нулю.

Ссылки

Donoho, D. L., Compressed Sensing , IEEE Transactions on Information Theory, V. 52(4), 1289—1306, 2006 от 26 июня 2010 на Wayback Machine
12 апреля 2010 года.
Candès, E.J., & Wakin, M.B., An Introduction To Compressive Sampling , IEEE Signal Processing Magazine, V.21, March 2008

Для дальнейшего чтения

Wired Magazine article
at Rice University .
— article in the AMS What’s Happening in the Mathematical Sciences series
A blog on Compressive Sensing featuring the most recent information on the subject (preprints, presentations, Q/As)