Сжатые измерения¶

Сжатые измерения (англ. compressed sensing, compressive sensing, compressive sampling) — это метод цифровой обработки сигналов, позволяющий восстанавливать исходный сигнал или изображение из меньшего числа измерений, чем это требуется согласно классической теореме Котельникова — Найквиста. В основе метода лежит предположение о том, что сигнал является разреженным (sparse) в некотором базисе, то есть может быть представлен малым числом ненулевых коэффициентов. Сжатые измерения находят применение в таких областях, как медицинская визуализация (МРТ, КТ), астрономия, радиолокация, сейсморазведка и цифровая фотография.

¶История

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

В 2004 году математики Эммануэль Кандес (Калифорнийский технологический институт), Джастин Ромберг (Калифорнийский технологический институт) и Теренс Тао (Калифорнийский университет в Лос-Анджелесе) опубликовали серию работ, заложивших теоретические основы сжатых измерений. В 2006 году Дэвид Донохо (Стэнфордский университет) ввёл термин «compressed sensing» и сформулировал ключевые принципы. В 2007 году Кандес и Ромберг доказали, что при определённых условиях сигнал можно точно восстановить из случайных линейных измерений, решая задачу минимизации L1-нормы.

В последующие годы метод активно развивался, появились алгоритмы реконструкции (например, итеративные алгоритмы на основе пороговой обработки, метод ортогонального преследования), а также практические реализации в медицинских сканерах и камерах с одной матрицей (single-pixel camera).

¶Основные принципы

¶Разреженность сигнала

Ключевое условие применимости сжатых измерений — разреженность сигнала в некотором базисе. Сигнал \( x \in \mathbb{R}^n \) называется \( k \)-разреженным, если он имеет не более \( k \) ненулевых коэффициентов в некотором ортонормированном базисе \( \Psi \) (например, в базисе вейвлетов, дискретного косинусного преобразования или Фурье). Реальные сигналы (изображения, аудиозаписи) часто являются приближённо разреженными: большинство коэффициентов малы, и их можно отбросить без существенной потери информации.

¶Измерения

Вместо того чтобы измерять все \( n \) отсчётов сигнала, сжатые измерения используют \( m \) линейных проекций, где \( m \ll n \). Каждое измерение представляет собой взвешенную сумму всех отсчётов сигнала. Математически это записывается как:

\[ y = \Phi x \]

где \( y \in \mathbb{R}^m \) — вектор измерений, \( \Phi \) — матрица измерений размером \( m \times n \), \( x \) — исходный сигнал. Матрица \( \Phi \) обычно выбирается случайной (например, с элементами из нормального распределения или случайными знаками ±1), что обеспечивает выполнение свойства ограниченной изометрии (restricted isometry property, RIP).

¶Восстановление

Задача восстановления сигнала \( x \) по измерениям \( y \) является недоопределённой (число уравнений меньше числа неизвестных). Однако благодаря разреженности сигнала её можно решить, минимизируя L1-норму коэффициентов в разрежающем базисе:

\[ \min_{\alpha} \|\alpha\|_1 \quad \text{при условии} \quad y = \Phi \Psi \alpha \]

где \( \alpha \) — коэффициенты сигнала в базисе \( \Psi \), \( \|\alpha\|_1 = \sum |\alpha_i| \) — L1-норма. Эта задача выпуклой оптимизации может быть решена методами линейного программирования (например, симплекс-методом) или специализированными алгоритмами (алгоритм базисного преследования, итеративный алгоритм пороговой обработки). При выполнении определённых условий (например, если матрица \( \Phi \Psi \) удовлетворяет свойству ограниченной изометрии) решение L1-минимизации совпадает с истинным разреженным сигналом.

¶Классификация методов

¶По типу измерений

Случайные измерения — матрица \( \Phi \) состоит из случайных чисел (гауссовские, бернуллиевские). Наиболее распространённый подход, обеспечивающий хорошие теоретические гарантии.
Структурированные измерения — матрица \( \Phi \) имеет специальную структуру (например, измерения на основе преобразования Фурье или Хаара). Используются в приложениях, где случайные измерения технически сложны (например, в МРТ — измерения в частотной области).
Детерминированные измерения — матрица \( \Phi \) строится на основе кодов с коррекцией ошибок или других математических конструкций. Обеспечивают гарантии восстановления, но часто требуют большего числа измерений.

¶По алгоритму восстановления

Выпуклая оптимизация — решение задачи минимизации L1-нормы (базисное преследование). Точный, но вычислительно затратный метод.
Жадные алгоритмы — последовательное выделение ненулевых коэффициентов (ортогональное преследование, метод сопряжённых градиентов). Быстрее, но могут давать субоптимальные решения.
Итеративные алгоритмы пороговой обработки — чередование проекции на множество измерений и пороговой обработки коэффициентов (ISTA, FISTA). Компромисс между точностью и скоростью.
Байесовские методы — учитывают априорное распределение коэффициентов (например, лапласовское). Используются в задачах с шумом.

¶Применение

¶Медицинская визуализация

Сжатые измерения наиболее широко применяются в магнитно-резонансной томографии (МРТ). В традиционной МРТ время сканирования пропорционально числу измерений в частотной области (k-пространство). Использование сжатых измерений позволяет сократить число измерений в 2–4 раза, что уменьшает время процедуры и снижает дискомфорт пациента. В 2007 году группа исследователей под руководством Майкла Люстига (Стэнфордский университет) впервые продемонстрировала реконструкцию МРТ-изображений с использованием сжатых измерений. В 2010-х годах метод был внедрён в коммерческие МРТ-сканеры (например, Siemens, GE Healthcare).

В компьютерной томографии (КТ) сжатые измерения позволяют снизить дозу рентгеновского излучения за счёт уменьшения числа проекций. Однако из-за особенностей геометрии КТ-сканера (измерения вдоль линий) применение метода требует адаптации.

¶Астрономия

В радиоастрономии сжатые измерения используются для восстановления изображений небесных объектов по данным интерферометров (например, ALMA, LOFAR). Традиционные методы требуют большого числа антенн и длительного времени наблюдения; сжатые измерения позволяют получать изображения высокого разрешения при меньшем числе измерений.

¶Радиолокация

В радиолокационных системах (SAR, синтезированная апертура) сжатые измерения применяются для уменьшения объёма передаваемых данных и повышения разрешающей способности. Метод позволяет восстанавливать радиолокационные изображения из разреженных отсчётов, что особенно важно для бортовых систем с ограниченной пропускной способностью канала связи.

¶Цифровая фотография

В 2008 году исследователи из Университета Райса (США) создали камеру с одной матрицей (single-pixel camera), которая использует сжатые измерения. Вместо матрицы из миллионов пикселей она содержит один фотодетектор и массив микрозеркал (DMD), которые проецируют случайные маски на сцену. Каждое измерение — это суммарная интенсивность света, прошедшего через маску. Изображение восстанавливается по нескольким сотням или тысячам таких измерений. Такая камера может работать в инфракрасном или терагерцовом диапазоне, где создание матричных сенсоров дорого.

¶Сейсморазведка

В геофизике сжатые измерения используются для восстановления сейсмических данных по разреженной сети датчиков. Это позволяет снизить стоимость полевых работ и повысить разрешающую способность сейсмических изображений.

¶Ограничения и критика

Несмотря на теоретические преимущества, сжатые измерения имеют ряд ограничений:

Вычислительная сложность — восстановление сигнала требует решения задач оптимизации, что может быть медленным для больших объёмов данных (например, трёхмерные изображения).
Чувствительность к шуму — при наличии шума в измерениях качество восстановления снижается, особенно при малом числе измерений.
Требование разреженности — метод эффективен только для сигналов, которые являются разреженными в некотором базисе. Для сигналов с низкой разреженностью (например, текстурированные изображения) качество восстановления может быть неудовлетворительным.
Практическая реализация — создание случайных измерительных матриц в аппаратном обеспечении (например, в МРТ-сканерах) технически сложно и требует калибровки.

Критика метода связана с тем, что в некоторых приложениях (например, в МРТ) традиционные методы сжатия (JPEG, MPEG) уже обеспечивают высокую степень сжатия, и сжатые измерения не всегда дают существенный выигрыш. Кроме того, для многих задач существуют более эффективные специализированные алгоритмы, не требующие решения L1-минимизации.

¶Интересные факты

В 2012 году журнал IEEE Signal Processing Magazine назвал сжатые измерения одним из 10 наиболее значимых достижений в области обработки сигналов за последние 20 лет.
В 2017 году группа исследователей из Массачусетского технологического института (MIT) разработала камеру, которая использует сжатые измерения для получения трёхмерных изображений в реальном времени (с частотой 30 кадров в секунду).
Сжатые измерения лежат в основе некоторых алгоритмов машинного обучения, в частности, для восстановления данных по разреженным выборкам (например, в рекомендательных системах).

¶Источники

Candès, E. J., Romberg, J., & Tao, T. (2006). Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information. IEEE Transactions on Information Theory, 52(2), 489–509.
Donoho, D. L. (2006). Compressed sensing. IEEE Transactions on Information Theory, 52(4), 1289–1306.
Lustig, M., Donoho, D. L., & Pauly, J. M. (2007). Sparse MRI: The application of compressed sensing for rapid MR imaging. Magnetic Resonance in Medicine, 58(6), 1182–1195.
Baraniuk, R. G. (2007). Compressive sensing. IEEE Signal Processing Magazine, 24(4), 118–121.
Foucart, S., & Rauhut, H. (2013). A Mathematical Introduction to Compressive Sensing. Birkhäuser.
Duarte, M. F., et al. (2008). Single-pixel imaging via compressive sampling. IEEE Signal Processing Magazine, 25(2), 83–91.