Теория информации
Сжатые измерения и RIP
Цели урока
- Сформулировать задачу compressive sensing и условие RIP
- Объяснить почему l1-релаксация работает при выполнении RIP
- Описать алгоритмы ISTA/FISTA и concept algorithm unrolling
- Связать CS с теорией информации через информационную нижнюю границу
Предварительные знания
- Теория скорость-искажение
- Теория кодирования источника
Как за O(k log n/k) случайных измерений - намного меньше Найквиста - восстановить k-разреженный сигнал из n элементов? Что гарантирует RIP?
- CS-МРТ (Siemens, GE): время сканирования сокращено с 30 до 8-15 минут
- THz одно-пиксельные камеры: CS делает ИК-детекторы в 1000 раз дешевле
- LISTA: нейросетевой CS-декодер в 20-50 раз быстрее итерационного ISTA
- Случайные проекции в ML: Johnson-Lindenstrauss + CS как теоретическая основа
CS: революция сжатия 2006 года
2006 год: Candes, Romberg, Tao публикуют 'Robust Uncertainty Principles' и 'Stable Signal Recovery from Incomplete and Inaccurate Measurements'. В том же году Donoho публикует 'Compressed Sensing'. Одновременное открытие двух групп - сигнал, что идея назрела. Основа в более ранних работах: Basis Pursuit (Chen, Donoho, Saunders 1998), Uncertainty Principle в сигнальной обработке (Donoho-Stark 1989). Первое применение: CS-МРТ Lustig et al. (2007) - революция в медицинской визуализации. 2010: LISTA - нейросетевой CS. 2012: CS в радарах (DARPA, MIT LL). Сегодня CS - часть стандартной программы по теории информации.
Compressive Sensing: меньше измерений, чем Найквист
Теорема Найквиста-Котельникова говорит: чтобы восстановить сигнал с полосой B, нужно 2B измерений в секунду. Compressive Sensing (CS) говорит: если сигнал разреженный, можно обойтись в 5-10 раз меньшим числом случайных измерений. Кандес, Ромберг и Тао доказали это в 2006 году. В том же году Дона публикует аналогичные результаты. Начинается новая область.
MRI (магнитно-резонансная томография) - практическое применение CS в медицине. МРТ-сигнал разреженен в пространстве частот. Стандартное МРТ: сканирование 30 минут. CS-МРТ (Lustig et al., 2007): 8-15 минут при том же качестве. Для пациентов с клаустрофобией или детей это принципиально. Сегодня CS-МРТ встроено в аппараты Siemens, GE, Philips.
CS и теорема Шеннона: CS не противоречит теореме Найквиста. Найквист предполагает полосоограниченные сигналы без дополнительной структуры. CS использует разреженность как дополнительную структуру - это другой класс сигналов. Shannon R(D) для k-разреженного сигнала: R(D) ~ k/2 * log(sigma^2/D), а не n/2 * log(sigma^2/D).
Почему CS не противоречит теореме Найквиста-Котельникова?
Найквист: для сигнала с полосой B нужно 2B отсчётов - точная теорема для полосоограниченных сигналов. CS: для k-разреженного сигнала из n элементов достаточно O(k log n) случайных измерений - теорема для разреженных сигналов. Разные классы сигналов, разные теоремы.
Restricted Isometry Property (RIP)
RIP - математическое условие на матрицу измерений Phi, гарантирующее точное восстановление через l1-минимизацию. Кандес и Тао ввели RIP в 2005 году. Интуиция: Phi почти сохраняет расстояния между разреженными векторами. Это значит, что разреженные векторы можно различить по их сжатым образам.
Матрицы измерений: практические варианты
Гауссова случайная матрица: Phi_{ij} ~ N(0, 1/m). Удовлетворяет RIP с вероятностью >= 1 - exp(-cm). Недостаток: хранить n*m чисел дорого. Частичная матрица DFT: выбрать m случайных строк из n-точечного ДПФ. Используется в CS-МРТ: k-space траектория вместо равномерной. Адамаровская матрица: быстрое преобразование Walsh-Hadamard, O(n log n). Применяется в CS-спектроскопии.
Что гарантирует RIP с delta_{2k} < sqrt(2) - 1?
RIP с delta_{2k} < sqrt(2)-1 гарантирует: l1-минимизация (LASSO/basis pursuit) восстанавливает x с ошибкой <= C*sigma_k(x)/sqrt(k) + D*noise. Здесь sigma_k(x) - ошибка лучшего k-разреженного приближения. Если x точно k-разреженный и шума нет - точное восстановление.
Алгоритмы восстановления и связь с ML
Basis pursuit (l1-минимизация) - выпуклая задача, решаемая через LP или ADMM. Для больших n (изображения MRI) итерационные алгоритмы быстрее. ISTA/FISTA - проксимальные методы для LASSO. OMP (Orthogonal Matching Pursuit) - жадный алгоритм. Нейросетевые развёртки (LISTA, ISTA-Net) обучают 'ускоренный' ISTA.
LISTA (Learned ISTA, Gregor & LeCun, 2010): развернуть K шагов ISTA в нейросеть и обучить. Каждый слой: W_e * y + W_s * x + S_theta. Обучение: минимизировать восстановление на тренировочных парах (x, y). Результат: 20-50x ускорение по сравнению с ISTA при том же качестве. Это ранний пример 'algorithm unrolling' - сейчас широко применяется в MRI, sEEG, радарах.
CS в одно-пиксельной камере
Rice University, 2006: 'Single Pixel Camera'. Вместо матрицы CCD - один фотодетектор и управляемое зеркало DMD. Каждое измерение: случайная +/-1 маска на изображение, интегрированная на детектор. m=10000 измерений из n=65536 пикселей (16%). LASSO восстанавливает изображение. Применение: ИК и THz камеры, где большие матрицы CCD дорогие. Каждый пиксель CCD для терагерца стоит 10000 долларов - одно-пиксельная камера с CS в 1000 раз дешевле.
Что такое 'algorithm unrolling' в контексте LISTA?
Algorithm unrolling: итерационный алгоритм (ISTA, AMP, ADMM) разворачивается в конечное число слоёв нейросети. Параметры (матрицы весов, пороги) обучаются градиентным спуском. LISTA (10 слоёв) восстанавливает качество 50-100 итераций ISTA за счёт адаптации к распределению данных.
CS через призму теории информации
Compressive sensing и теория информации - глубоко связаны. CS - это задача кодирования источника с особой структурой разреженности. Число измерений m = O(k log n/k) - это в точности количество информации, необходимое для описания k-разреженного вектора из n элементов при отсутствии шума.
Approximate Message Passing (AMP, Donoho-Maleki-Montanari, 2009): алгоритм CS, оптимальный при гауссовых матрицах измерений. State evolution AMP - аналог density evolution для LDPC: точно предсказывает ошибку восстановления при любом m, n, k. AMP работает в разы быстрее ISTA и достигает информационно-оптимальной границы m = O(k log n/k) для гауссовых Phi.
Почему информационно оптимальное число CS-измерений равно O(k log n/k)?
log C(n,k) ~ k*log(n/k) - это энтропия равномерного распределения на k-разреженных паттернах. Меньшее число измерений не даёт достаточно информации для однозначного определения поддержки сигнала. CS при m = C*k*log(n/k) информационно оптимален.
Связь с другими темами
Compressive sensing объединяет: теорию информации (нижняя граница k*log(n/k)), выпуклую оптимизацию (l1-задача, ADMM, FISTA), вероятностные методы (RIP для случайных матриц, AMP state evolution). В ML: LASSO = l1-регуляризация = feature selection; Johnson-Lindenstrauss = случайные проекции для dimensionality reduction; algorithm unrolling = LISTA, ISTA-Net. Phase transition CS - аналог порогового SNR в LDPC density evolution.
- Information Theory — Связанная тема
Итоги
- CS: m = O(k log n/k) случайных измерений достаточно для восстановления k-разреженного x из n
- RIP delta_{2k} < sqrt(2)-1 гарантирует точное восстановление через l1-минимизацию
- Случайные матрицы (гауссовы, берн.) удовлетворяют RIP с высокой вероятностью при m >= Ck*log(n/k)
- ISTA: мягкий порог + градиентный шаг; LISTA ускоряет его в 20-50x через обучение
Вопросы для размышления
- Почему замена l0 на l1 в CS-задаче работает, если это разные нормы?
- Чем phase transition в CS похожа на пороговый SNR в density evolution для LDPC?
- Как LISTA нарушает разделение 'алгоритм' и 'данные', и почему это работает?