ПОВЫШЕНИЕ ТОЧНОСТИ РЕШЕНИЯ ОБРАТНОЙ ЗАДАЧИ С ИСПОЛЬЗОВАНИЕМ СЛУЧАЙНЫХ ПРОЕКЦИЙ

ПОВЫШЕНИЕ ТОЧНОСТИ РЕШЕНИЯ ОБРАТНОЙ ЗАДАЧИ С ИСПОЛЬЗОВАНИЕМ СЛУЧАЙНЫХ ПРОЕКЦИЙ

Авторы: Елена Ревунова, Дмитрий Рачковский
Аннотация: Приводятся результаты исследования разрабатываемого подхода к решению дискретной некорректной обратной задачи с использованием методов псевдообращения и случайных проекций. В известных обратных задачах Филипса и Барта получена относительная ошибка восстановления сигнала не хуже, чем для методов регуляризации Тихонова.
Ключевые слова: обратная задача, устойчивое решение, случайные проекции, регуляризация Тихонова
ACM Classification Keywords: I.5.4 Signal processing, I.6 Simulation and Modeling, G.1.9 Integral Equations
Conference: The paper is selected from XVth International Conference “Knowledge-Dialogue-Solution” KDS-2 2009, Kyiv, Ukraine, October, 2009.

Введение
Решение обратной задачи актуально для целого ряда приложений. К ним относятся интерпретация данных физических экспериментов в задачах исследования различных полей и сред, а также многие другие задачи. В практических приложениях требуется решать дискретную обратную задачу вида: Фх=у, (1) где матрица Ф??N?N и вектор у??N известны и получены в результате оцифровки методом Галеркина уравнения Фредгольма первого рода [1, 2, 3, 4]; требуется оценить вектора сигнала х??N.
В случае, когда у содержит аддитивный шум, Ф имеет высокое число обусловленности ||Ф-1|| ||Ф||, ряд сингулярных чисел Ф плавно спадает к нулю, – задачу оценки х называют [1] дискретной некорректной обратной задачей. Такие свойства Ф характерны для задач оптики, спектрометрии, электроразведки.
Решение дискретной некорректной обратной задачи как задачи наименьших квадратов х'=argminх ||у? Фх||2 (2) в виде решения минимальной нормы [5] на основе псевдообращения х'=Ф+у (3) является неустойчивым [1, 3]. Признаком неустойчивости является то, что малым изменениям вектора y соответствуют большие изменения решения х'; при этом велико значение ошибки решения.
Для преодоления неустойчивости и, соответственно, повышения точности решения в условиях шума используют подход регуляризации [1, 2, 3, 4], состоящий в учете априорной информации – о том, что l2- норма решения ||x||2 мала [5]; либо что решение является разреженным [6], т.е. ||x||0 мало; либо о точности аппроксимации [6].
При наличии априорной информации о малости l2-нормы решения для получения устойчивого решения используют решение минимальной нормы (3) либо регуляризацию Тихонова [1]. В случае регуляризации Тихонова задачу формулируют следующим образом х'=argminх ( ||у? Фх||2+?||х||2 ), (4) где? – параметр регуляризации.
Недостатком, присущим методам решения дискретных некорректных обратных задач на основе регуляризации Тихонова, является необходимость подбора ?-параметра регуляризации, от правильности которого в значительной мере зависит устойчивость решения. Методы подбора параметра регуляризации имеют высокую вычислительную сложность. Методы на основе псевдообращения не требуют подбора параметров, однако они не обеспечивают [1, 3] устойчивости и точности решения. Поэтому востребованными являются подходы к устойчивому решению дискретной некорректной обратной задачи на основе псевдообращения, но с точностью на уровне регуляризации Тихонова.
В данной работе приводятся результаты исследования разрабатываемого нами подхода к решению дискретной некорректной обратной задачи с использованием методов псевдообращения и случайных проекций на двух известных обратных задачах — Филипса и Барта [7], [8].

Решение дискретной некорректной обратной задачи
Нами предлагается подход к решению дискретной некорректной обратной задачи, использующий аналогию с современными работами в области Compressed Sensing («сжатого зондирования») [9], [10], [11]. Здесь для высокоточного восстановление x по Rx в качестве проектора R используют матрицу с элементами, сформированными реализациями случайной величины с нормальным законом распределения [11], [12]. Такого рода случайные проекционные матрицы с k<N используются также в теории [11], [13] и практике [14] вложений векторных пространств (vector space embeddings) для сокращения размерности векторов с целью ускорения оценки их сходства.
Для решения обратной задачи с использованием проекционного подхода умножим обе части исходного уравнения (1) на матрицу R??k?N, k?N, элементы которой – реализации случайной величины с нормальным распределением, нулевым средним и единичной дисперсией. Число столбцов N матрицы R фиксировано и определяется размерностью исходной матрицы Ф: число строк k может выбираться произвольно. Получаем уравнение RФх=Rу, RФ=А, А??k?N, Rу=b, b??k. (5)
Восстановление сигнала методом наименьших квадратов х'=argminх ||Rу?RФх||2. (6)
Тогда восстановление сигнала х на основе псевдообращения получим как х'= (RФ)+Rу, х'=(A)+b, (7) либо как х'=((RФ)ТRФ)+(RФ)ТRу, х'=(АТА)+АТb. (8)
Восстановление сигнала методом регуляризации Тихонова получим как х'=argminх ( ||Rу? RФх||2+?||х||2 ). (9)
Точность решения обратной задачи будем оценивать с помощью относительной ошибки d восстановления истинного сигнала х, вычисляемой как d=||х–х'||/||х||=||? х||/||х||, (10) где? х – ошибка решения, х' – вектор восстановленного сигнала.
Экспериментально исследуем поведение зависимости относительной ошибки восстановления сигнала от уровня аддитивного собственного шума в векторе сигнала у (1).
Экспериментальное исследование

Исследовались примеры дискретных некорректных обратных задач Филипса и Барта


Рис. Матрица Ф оцифровки ядра в задаче Филипса


Рис. Матрица Ф оцифровки ядра в задаче Барта

В обеих задачах матрица Ф, полученная при оцифровке ядра, имела размерность 200?200, высокое число обусловленности (||Ф-1|| ||Ф||>>1), и ряд сингулярных чисел, плавно спадающий к нулю. Вектор правой части уравнения (2) после оцифровки искажался аддитивным шумом? c нормальным распределением. Исследовалось поведение зависимости относительной ошибки восстановления сигнала от уровня аддитивного собственного шума в сигнале у. Сравнивались зависимости d(?) для методов на основе псевдообращения и регуляризации без применения проецирования с аналогичными зависимостями после применения проецирования. Размерность k для псевдообращения с проецированием выбиралась экспериментально по минимуму ошибки d.
Тестовая задача Филипса. Для задачи Филипса матрица Ф получается из аналитически заданной функции ядра K(s,t) = ?(s–t), ?(x) = 1+cos(?x/3) при |x|<3, ?(x) = 0 при |x|?3, y из g(s) = (6– |s|)(1+0.5cos(?s/3)) + 9/2? sin(?|s|/3) путем оцифровки по методу Галеркина [1].
Результаты зависимости относительной ошибки восстановления сигнала от уровня шума без умножения на матрицу-проектор (pinv1, pinv2, reg1, reg2, reg3) и результаты для экспериментов с умножением на матрицу R (pinv1r, pinv2r, reg1r, reg2r, reg3r) приведены на рис. 1 (расшифровка названий методов приведена далее).
Среди методов решения обратной задачи без проецирования наибольшую ошибку дают методы на основе псевдообращения матрицы Ф. При уровне шума nl 1e-7 относительная ошибка d (10) для pinv1 составляет 0.36, а для pinv2 – 0.14. При уровнях шума с 1e-5 и 1e-6 (для pinv1 и pinv2 соответственно) относительная ошибка d превышает 1.0, что свидетельствует о значительном искажении формы восстанавливаемого сигнала. Метод pinv2 во всем исследованном диапазоне шума дает ошибку меньшую, чем pinv1.


Для регуляризации Тихонова с подбором параметра регуляризации по методу L-кривой reg2 в диапазоне шума от 1e-7 до 1е-3 значение ошибки d изменяется в пределах от 0.14 до 0.35; при дальнейшем возрастании уровня шума ошибка d растет. Высокая относительная ошибка d этого метода связана с тем, что получаемые им значения параметра регуляризации? не оптимальны.
Наименьшие значения ошибки d демонстрирует метод основе регуляризации Тихонова с подбором? по методу кроссвалидации reg1. В диапазоне шумов 1е-7 – 1е-3 метод обеспечивает наименьшую ошибку среди всех исследованных нами методов регуляризации без проецирования. Низкие значения ошибки в указанном диапазоне шумов обеспечиваются благодаря удачному подбору параметра регуляризации.
Зависимость ошибки d от уровня шума, полученная методом регуляризации Тихонова с подбором? по методу обобщенной невязки reg3, аналогична зависимости для методов на основе псевдоинверсии: при уровнях шума 1e-7–1e-6 она составляет 0.1 – 0.86; а при уровнях шума выше 1e-5 d>1. Такое поведение относительной ошибки связано с тем, что выбор? методом обобщенной невязки осуществляется неверно (рис.2). Видно, что значения параметра регуляризации lmb3 для этого метода далеки от значений параметра регуляризации lmb1, полученных методом reg1, демонстрирующим лучшую точность.
Рассмотрим результаты методов решения обратной задачи с проецированием. При оптимальном k (в зависимости от шума k менялось от k=37 при nl=1e-7 до k=2 при nl=1e1) все они обеспечивают более устойчивое восстановление сигнала и более низкий уровень относительной ошибки, чем соответствующие методы без применения проецирования. Только для регуляризации с выбором? по методу кросс-валидации ошибка после проецирования reg1r и при уровнях шума 1е-6–1е-4 приближается к значениям ошибки до проецирования reg1. При дальнейшем нарастании уровня шума ошибка для reg1r становится намного меньшей, чем для reg1.
Среди методов регуляризации с проецированием reg1r, reg2r, reg3r наименьшую относительную ошибку d демонстрирует метод с выбором? по обобщенной невязке reg3r. Как видно из рис. 2, только для reg3r параметр регуляризации lmb3r растет с ростом шума, в то время как для методов reg1r, reg2r значения параметра регуляризации lmb1r, lmb2r имеют тенденцию к убыванию. Это свидетельствует о неправильном выборе параметра регуляризации для reg1r, reg2r, так как известно [1], что его значение должно возрастать с ростом уровня шума.
Отметим, что после проецирования методы, основанные на псевдообращении матрицы, обеспечивают относительную ошибку не хуже, чем методы регуляризации. Учитывая меньшие вычислительные затраты методов pinv1r, pinv2r, предпочтительно их использование.
Тестовая задача Барта. Для задачи Барта матрица Ф получается из аналитически заданной функции ядра K(s,t) = exp(s cos t), y из g(s) = 2 sin s /s путем оцифровки по методу Галеркина.

Вывод
Для дискретных некорректных обратных задач Филипса и Барта, полученных в результате оцифровки по методу Галеркина ядра и правой части уравнения Фредгольма первого рода, при решении методами псевдообращения с использованием проецирования снижается относительная ошибка восстановления сигнала. При этом, при оптимальном k, точность результатов не хуже, чем для методов на основе регуляризации Тихонова без проецирования. Это делает использование методов на основе псевдообращения матрицы предпочтительным в силу их большей устойчивости (проявляющейся в плавном изменении относительной ошибки восстановления сигнала с ростом шума); точности восстановления сигнала x, сравнимой или лучшей, чем у методов регуляризации Тихонова; и меньших вычислительных затрат. Направлением дальнейших исследований являются экспериментальные и теоретические методы вычислительно эффективного априорного выбора оптимального k.
  • +2
  • 3 ноября 2009, 17:52
  • yxom

Комментарии (0)

RSS свернуть / развернуть

Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.