Compressive sensing

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

История

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

Метод

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

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

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

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

Ссылки
  1. Donoho, D. L., Compressed Sensing, IEEE Transactions on Information Theory, V. 52(4), 1289—1306, 2006
  2. Hayes, Brian, The Best Bits, American Scientist, July 2009 Архивировано 12 апреля 2010 года.
  3. Candès, E.J., & Wakin, M.B., An Introduction To Compressive Sampling, IEEE Signal Processing Magazine, V.21, March 2008

Для дальнейшего чтения
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.