Compressive sensing

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

История[править | править вики-текст]

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

Метод[править | править вики-текст]

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

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

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

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

Ссылки[править | править вики-текст]

  1. Donoho, D. L., Compressed Sensing, IEEE Transactions on Information Theory, V. 52(4), 1289—1306, 2006 [1]
  2. Hayes, Brian, The Best Bits, American Scientist, July 2009
  3. Candès, E.J., & Wakin, M.B., An Introduction To Compressive Sampling, IEEE Signal Processing Magazine, V.21, March 2008 [2]

Для дальнейшего чтения[править | править вики-текст]