Этот грубый перевод с неуказанного языка требуется улучшить (см. Рекомендации по переводу). Статья, целиком являющаяся машинным переводом, может быть удалена на основании критерия быстрого удаления С2.

Вы можете помочь улучшить перевод.
Оригинал не указан. Пожалуйста, укажите его. (11 октября 2011)

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

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

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

• Using Math to Turn Lo-Res Datasets Into Hi-Res Samples Wired Magazine article
• Compressive Sensing Resources at Rice University.
• Compressed Sensing: The Big Picture
• A list of different hardware implementation of Compressive Sensing
• Compressed Sensing 2.0
• Compressed Sensing Makes Every Pixel Count — article in the AMS What’s Happening in the Mathematical Sciences series
• Nuit Blanche A blog on Compressive Sensing featuring the most recent information on the subject (preprints, presentations, Q/As)
• Online Talks focused on Compressive Sensing