Подход рандомизации в задачах восстановления сигналов по результатам непрямых измерений
Предложен подход к устойчивому решению задачи преобразования выхода, основанный на использовании случайных проекций и QR-разложения, проведено экспериментальное исследование поведения зависимости ошибки и ее составляющих от размерности матрицы проектора. Для рандомизированного метода решения дискрет...
Saved in:
| Published in: | Кибернетика и вычислительная техника |
|---|---|
| Date: | 2013 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН України та МОН України
2013
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/84481 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Подход рандомизации в задачах восстановления сигналов по результатам непрямых измерений / Е.Г. Ревунова // Кибернетика и вычислительная техника. — 2013. — Вип. 173. — С. 35-46. — Бібліогр.: 17 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860163903724453888 |
|---|---|
| author | Ревунова, Е.Г. |
| author_facet | Ревунова, Е.Г. |
| citation_txt | Подход рандомизации в задачах восстановления сигналов по результатам непрямых измерений / Е.Г. Ревунова // Кибернетика и вычислительная техника. — 2013. — Вип. 173. — С. 35-46. — Бібліогр.: 17 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и вычислительная техника |
| description | Предложен подход к устойчивому решению задачи преобразования выхода, основанный на использовании случайных проекций и QR-разложения, проведено экспериментальное исследование поведения зависимости ошибки и ее составляющих от размерности матрицы проектора. Для рандомизированного метода решения дискретной некорректной задачи приведены выражения для ошибки восстановления сигнала выхода, проведено исследование зависимости ошибки от размерности матрицы проектора.
Запропоновано підхід до стійкого вирішення завдання перетворення виходу, заснований на використанні випадкових проекцій і QR-розкладання, проведено експериментальне дослідження поведінки залежності помилки і її складових від розмірності матриці проектора. Для рандомізованого методу розв'язання дискретної некоректної задачі наведено вирази для помилки відновлення сигналу виходу, проведено експериментальне дослідження залежності помилки від розмірності матриці проектора.
The purpose is to develop approaches to regularization that provide solution accuracy at the level of Tikhonov regularization, but with less computational complexity.
|
| first_indexed | 2025-12-07T17:55:59Z |
| format | Article |
| fulltext |
35
УДК 004.942+623.454.862
ПОДХОД РАНДОМИЗАЦИИ В ЗАДАЧАХ
ВОССТАНОВЛЕНИЯ СИГНАЛОВ
ПО РЕЗУЛЬТАТАМ НЕПРЯМЫХ ИЗМЕРЕНИЙ
Е.Г. Ревунова
Международный научно-учебный центр информационных технологий
и систем НАН Украины и Министерства образования и науки Украины
Предложен подход к устойчивому решению задачи преобразования
выхода, основанный на использовании случайных проекций и QR-разложения, проведено
экспериментальное исследование поведения зависимости ошибки и ее составляющих от
размерности матрицы проектора. Для рандомизированного метода решения дискретной
некорректной задачи приведены выражения для ошибки восстановления сигнала выхода,
проведено исследование зависимости ошибки от размерности матрицы проектора.
Запропоновано підхід до стійкого вирішення завдання перетворення
виходу, заснований на використанні випадкових проекцій і QR-розкладання, проведено
експериментальне дослідження поведінки залежності помилки і її складових від
розмірності матриці проектора. Для рандомізованого методу розв'язання дискретної
некоректної задачі наведено вирази для помилки відновлення сигналу виходу, проведено
експериментальне дослідження залежності помилки від розмірності матриці проектора.
ВВЕДЕНИЕ
В настоящей работе развивается подход к повышению эффективности
решения задач восстановления сигналов по результатам непрямых измерений
на основе одного типа нейросетевого распределенного представления
информации [1, 2], построенного по аналогии с представлением информации
в мозге. Подход является развитием идей Николая Михайловича Амосова и
его научной школы [3–6]. В последнее время исследователи, работающие в
области численных методов линейной алгебры, применяют подобные идеи
для получения быстрых рандомизированных алгоритмов (см. обзор в [1] и
[2]). Этот подход позволил нам разработать вычислительно эффективные
методы решения дискретной некорректной задачи [7, 8].
Цель работы:
— разработать метод устойчивого решения задачи преобразования
выхода, основанный на случайных проекциях, используемых для получения
распределенных представлений [1, 2];
— для рандомизированного метода решения дискретной некорректной
задачи [8] получить выражения для ошибки восстановления вектора выхода и
провести экспериментальное исследование зависимости ошибки от
размерности матрицы проектора.
ЛИНЕЙНЫЕ ЗАДАЧИ НАИМЕНЬШИХ КВАДРАТОВ И ДИСКРЕТНЫЕ
НЕКОРРЕКТНЫЕ ЗАДАЧИ
Многие приложения математики, физики, анализа данных и др. требуют
нахождения приближенного решения системы линейных уравнений:
Ах ≈ y, (1)
Е.Г. Ревунова, 2013
ISSN 0452-9910. Кибернетика и вычисл. техника. 2013. Вып. 173
36
где матрица А∈ℜN×N и вектор у∈ℜN, искаженный аддитивным шумом
ε∈ℜN y = y0 + ε, известны и требуется оценить вектор сигнала х∈ℜN.
Метод наименьших квадратов минимизирует сумму квадратов
компонентов вектора невязки путем решения оптимизационной задачи
2minarg yAxx
x
−=′ . (2)
Если матрица A имеет полный ранг и хорошо обусловлена, x′ можно
получить путем решения системы нормальных уравнений, например с
помощью разложения Холецкого. В случае когда матрица A имеет
неполный ранг или плохо обусловлена, для решения задачи (2) может
использоваться решение на основе QR-разложения. В случае когда матрица
A очень плохо обусловлена, для решения используют разложение по
сингулярным значениям (SVD). Решение на основе сингулярного разложения
получают следующим образом: yAyUVSx +Τ− ==′ 1 , где +A —
псевдообратная матрица.
Метод SVD является наиболее вычислительно сложным среди
упомянутых выше методов, но при очень плохо обусловленной матрице его
использование предпочтительно, т.к. он позволяет избежать неустойчивости
и, как следствие, неточности решения. Проявлением неустойчивости является
тот факт, что небольшим изменениям вектора y (например, из-за шума)
соответствуют большие изменения решения x′ и возрастание ошибки
решения. Причина возникновения неустойчивости состоит в том, что при
очень большом числе обусловленности в конце ряда сингулярных значений
наблюдаются очень малые величины. Соответственно обратные сингулярные
значения в матрице 1−S становятся очень большими, и поэтому значения
компонент x′ также становятся очень большими. Идея преодоления
неустойчивости при решении задачи (2) на основе сингулярного разложения
состоит в следующем: если в спектре сингулярных значений имеется резкий
перепад, а сингулярные значения после него очень малы, они могут
рассматриваться как шумовые и устраняются применением порога.
Однако такой прием не работает в т.н. дискретных некорректных задачах
[9], т.е. в случае, когда у содержит шум, А имеет высокое число
обусловленности σmax / σmin, ряд сингулярных чисел σi матрицы А плавно
спадает к нулю. В этом случае нет разрывов в ряду сингулярных значений и
численный ранг А не определен.
Для преодоления неустойчивости и повышения точности решения
используют регуляризацию [9, 10]. Регуляризация накладывает некоторые
ограничения на решение, позволяющие повысить его устойчивость —
например, малость l2-нормы решения ||x'||2. Классическим методом
регуляризации является регуляризация Тихонова стандартного вида [10]:
( )22reg minarg xyAxx
x
λ+−= , (3)
где λ — параметр регуляризации.
Е.Г. Ревунова, 2013
ISSN 0452-9910. Кибернетика и вычисл. техника. 2013. Вып. 173
37
Решение задачи (3) получают, например, методом фильтрованного
сингулярного разложения [9]: yUVx Τ= )/(diagreg iif σ , где )(/ 222 λ+σσ= iiif
— так называемые фильтрующие множители. Одной из проблем решения
дискретной некорректной задачи методом фильтрованного сингулярного
разложения является использование SVD-разложения A , так как оно имеет
большую вычислительную сложность }),min{( nmmnO . Еще одной
проблемой, которая может оказаться даже более важной, является выбор
надлежащего параметра регуляризации λ . Это требует дополнительных
вычислений и не всегда позволяет достичь необходимого результата, т.е. не
всегда обеспечивает устойчивое и точное решение x′ . Для выбора параметра
регуляризации был предложен ряд методов: метод
L -кривой [9], принцип невязки [10], метод обобщенной перекрестной
проверки [9], однако указанные методы не всегда дают устойчивые
результаты. Поэтому при неверных значениях параметра регуляризации
ошибка решения может быть значительной.
В последнее время исследователи, работающие в области численных
методов линейной алгебры, применяют идею рандомизации для получения
быстрых алгоритмов решения задач наименьших квадратов, факторизации
матриц, анализа главных компонент и др. Подход рандомизации может быть
использован и для решения дискретных некорректных задач. Хотя в
существующих подходах рандомизация направлена на ускорение
вычислений, она может быть также использована для стабилизации решения
дискретных некорректных задач.
Рассмотрим подход к устойчивому решению дискретных некорректных
задач, использующий идеи нейросетевого распределенного представления
информации и случайных проекций.
РЕШЕНИЕ ДИСКРЕТНОЙ НЕКОРРЕКТНОЙ ОБРАТНОЙ ЗАДАЧИ МЕТОДОМ
СЛУЧАЙНЫХ ПРОЕКЦИЙ
Нами разрабатывается подход к решению дискретной некорректной
обратной задачи, использующий проекционную версию рандомизированных
алгоритмов приближения матриц [11]. В качестве проектора G∈ℜk×N
используется матрица с элементами, сформированными реализациями
случайной величины [12]. Случайные проекционные матрицы с k < N
используются также в теории и практике вложений векторных пространств
для сокращения размерности векторов и ускорения оценки их сходства [2].
Для решения обратной задачи с использованием проекционного подхода
умножим обе части исходного уравнения (1) на матрицу G ∈ ℜk×N, k ≤ N,
элементы которой — реализации случайной величины с нормальным
распределением, нулевым средним и единичной дисперсией. Число столбцов
N матрицы G определяется размерностью исходной матрицы A, число строк
k априори не фиксировано.
Получим уравнение
Е.Г. Ревунова, 2013
ISSN 0452-9910. Кибернетика и вычисл. техника. 2013. Вып. 173
38
Fx = b, где F = GА, F∈ℜk×N, b = G у, b∈ℜk. (4)
Тогда задача наименьших квадратов (2) записывается в виде
х' = arg minх ||Fх–b||2. (5)
Восстановленный сигнал х на основе псевдообращения получим, как
х'G = F+b. (6)
Восстановленный сигнал на основе псевдообращения с использованием QR-
разложения матрицы GА получаем следующим образом:
х'Q= (QTA)+QTy, (7)
где Q , R получаются QR-разложением матрицы QRGAF == .
Точность решения обратной задачи будем оценивать с помощью ошибки
e восстановления истинного сигнала х, вычисляемой как e = ||х–х'|| = ||e||,
где х' — вектор восстановленного сигнала.
Существующие рандомизированные алгоритмы решения задачи
наименьших квадратов разрабатывались их авторами для случая, когда
вектор правой части не искажен шумом, матрица является хорошо
обусловленной и имеет полный ранг. Именно для этого случая доказывают,
что решение с использованием случайного проецирования с ростом
размерности проектора приближается к решению с помощью обычного
псевдообращения, ошибка e уменьшается. Однако для рассматриваемого
нами случая дискретной некорректной задачи решение с проектором
максимально возможной размерности неустойчиво и имеет недопустимо
низкую точность. Для нашей задачи нужна не близость решения,
полученного с использованием случайной проекции, к решению на основе
псевдоинверсии, а поиск оптимальной размерности проектора,
обеспечивающей минимальную ошибку решения.
Рассмотрим составляющие ошибки восстановления истинного сигнала.
Вектор ошибки e решения задачи (2) представляют [13, 14] в виде суммы
двух составляющих — смещения и дисперсии. Составляющие вычисляются
следующим образом. Пусть P — оператор, преобразующий y в х': х' = P y,
тогда с учетом y = y0 + ε выражение для оценки x можно представить в виде
х' = P (y0 + ε) = P y0 + P ε = P Aх + P ε; y0 = Aх. (8)
Используя выражение для х', получаем выражение для e:
e = х' – x = P Aх – x + P ε = (P A – I)x + P ε. (9)
Таким образом,
e = e1 + e2, где e1, e2∈ℜN, e1= (P A – I)x, e2 = P ε. (10)
e1 называют смещением, e2 — дисперсией [13, 14].
Е.Г. Ревунова, 2013
ISSN 0452-9910. Кибернетика и вычисл. техника. 2013. Вып. 173
39
В результате проецирования случайной матрицей G, составляющие
ошибки решения принимают следующий вид:
ex G = х'G – x = F+Gy – x = F+G(Ax + ε) – x = (F+ F – I)x + F+Gε. (11)
Составляющие ошибки
e1x G = (F+A – I)x, e2x G = F+G ε, (12)
где exG — ошибка решения для оценки вектора сигнала на основе
псевдообращения с использованием случайных проекций.
Запишем выражение для среднеквадратичной ошибки восстановления
истинного сигнала при проецировании случайной G (E — усреднение):
ex G = E ||(F+F – I)x ||2 + E ||F+Gε||2 + 2 E 〈(F+F – I)x, F+Gε||〉. (13)
Так как 2 E 〈(F+F – I)x, F+Gε||〉 = 0, и E ||F+Gε||2 = σ2 trace (GTF+TF+G)
ex G = ||(F+F – I)x ||2 + σ2 trace (GGT F+TF+). (14)
Рассмотрим ошибку восстановления вектора выхода в случае, когда в
качестве проектора используется матрица G:
ey G = y'G – y0 = A F+G y0 + A F+G ε – y0 = (A F+G – I)y0+ A F+G ε; (15)
Таким образом,
e1y G = (AF+G – I) y0, e2y G = AF+G ε. (16)
Выражение для среднеквадратичной ошибки восстановления выхода
выглядит следующим образом:
ey G = E ||(AF+G – I)y0||2 + E ||AF+Gε||2 + 2 E 〈(AF+G – I)y0, AF+Gε〉. (17)
Так как 2E〈(AF+G – I)y0, AF+Gε〉 = 0 и E||AF+Gε||2 = σ2trace((AF+G)TAF+G),
ey G = ||(AF+G – I)y0||2 + σ2 trace((AF+G)TAF+G). (18)
Рассмотрим случай, когда в качестве проектора используется матрица Q.
В результате проецирования ошибка решения принимают следующий вид:
ex Q = х'Q – x = (QTA)+QTy – x = (QTA)+QT(Ax + ε) – x =
= ((QTA)+QTA – I)x + (QTA)+QTε.
(19)
Составляющие ошибки:
e1x Q = ((QTA)+QTA – I)x, e2x Q = (QTA)+QTε. (20)
Запишем выражение для среднеквадратичной ошибки восстановления
истинного сигнала. Учитывая, что Е(||e2x Q||) = σ2trace(Q(QTA)+T(QTA)+QT)) =
= σ2trace((QTA)+T(QTA)+), выражение для среднеквадратичной ошибки
восстановления истинного сигнала следующее:
Е.Г. Ревунова, 2013
ISSN 0452-9910. Кибернетика и вычисл. техника. 2013. Вып. 173
40
ex Q = ||((QTA)+QTA – I)x ||2 + σ2 trace((QTA)+T(QTA)+). (21)
Рассмотрим ошибку восстановления вектора выхода в случае, когда в
качестве проектора используется матрица Q:
ey = y'Q – y0 = A(QTA)+QTy0 + A(QTA)+QTε – y0 =
= (A(QTA)+QT – I)y0 + A(QTA)+QTε.
(22)
Таким образом,
ey1= (A(QTA)+QT – I)y0, ey2 = A(QTA)+QTε. (23)
Запишем среднеквадратичную ошибку восстановления выхода. С учетом
E(QTA)+QTε) = σ2 trace ((A(QTA)+QT)T A(QTA)+QT), выражение для
среднеквадратичной ошибки восстановления выхода выглядит следующим
образом:
ey Q = || (A(QTA)+QT – I)y0||2 + σ2 trace ((QTA)+TATA(QTA)+). (24)
Для ошибки восстановления истинного сигнала, полученной с
использованием проекционной матрицы (G или Q), можно построить
зависимость от размерности матрицы k нормы смещения и дисперсии, а
также суммарной ошибки. Пример этих зависимостей для дискретной
некорректной задачи Phillips [15] при уровнях шума 1е–2, 1е–3, 1е–4
приведен на рис. 1, 2.
При возрастании k норма смещения уменьшается, а норма дисперсии
возрастает, и суммарная норма ошибки имеет минимум. Такое поведение
этих зависимостей характерно для задач выбора модели, где модель
оптимальной сложности обеспечивает минимум ошибки. Такой характер
поведения ошибки имел место для всех исследованных нами некорректных
обратных задач при уровне шума выше некоторого минимального [8].
Таким образом, для получения решения с минимальной ошибкой
необходимо использовать проекционную матрицу с размерностью k, близкой
к оптимальной. Однако определение оптимального значения k по графикам
зависимости ошибки восстановления истинного сигнала от k представляет
только теоретический интерес, т.к. выражение включает вектор истинного
решения, который при решении практических задач неизвестен. Чтобы
выбрать размерность k проекционной матрицы, при которой ошибка решения
близка к минимальной в реальных условиях, т.е. когда точное решение
неизвестно, мы предлагаем [8] использовать различные типы критериев
выбора k. При этом размерность k выбирается такой, при которой значение
критерия минимально.
Пример зависимостей нормы смещения, дисперсии и суммарной ошибки
от размерности матрицы k для ошибки восстановления сигнала выхода,
полученных с использованием проекционных матриц G и Q приведен
на рис. 3, 4. При использовании G норма смещения монотонно убывает с
возрастанием k. Норма дисперсии сигнала выхода для малых значений k
возрастает, а затем начинает убывать (рис. 3). Суммарная ошибка
Е.Г. Ревунова, 2013
ISSN 0452-9910. Кибернетика и вычисл. техника. 2013. Вып. 173
41
восстановления сигнала выхода с использованием G минимальна при k = N.
При использовании Q норма смещения монотонно убывает с возрастанием k
и норма дисперсии возрастает, а суммарная норма ошибки имеет минимум
при k < N (рис. 4). С ростом уровня шума положение минимума ошибки
восстановления сигнала выхода смещается в сторону меньших значений k.
Значения ошибки восстановления сигнала выхода с использованием
проекционной матрицы Q в точке минимума меньше минимальных значений
ошибки для проекционной матрицы G, поэтому для восстановления сигнала
выхода использование проекционной матрицы Q предпочтительно.
В практике часто встречается ситуация, когда наблюдаемый сигнал
выхода не отвечает требованиям пользователя, либо не совместим с
методами дальнейшей обработки. В этом случае может ставиться задача
преобразования вектора выхода к выходу требуемой линейной системы.
Рассмотрим задачу и метод преобразования выхода.
1.E-09
1.E-08
1.E-07
1.E-06
1.E-05
1.E-04
1.E-03
1.E-02
1.E-01
1.E+00
1.E+01
1.E+02
1.E+03
1.E+04
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39
k
e_
x
G
e_x G 1e-2 e_x G_1 e_x G_2
e_x G 1e-3 e_x G_1 e_x G_2
e_x G 1e-4 e_x G_1 e_x G_2
1.E-09
1.E-08
1.E-07
1.E-06
1.E-05
1.E-04
1.E-03
1.E-02
1.E-01
1.E+00
1.E+01
1.E+02
1.E+03
1.E+04
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39
k
e_
x
Q
e_x Q 1e-2 e_x Q_1 e_x Q_2
e_x Q 1e-3 e_x Q_1 e_x Q_2
e_x Q 1e-4 e_x Q_1 e_x Q_2
Рис. 1. Зависимость ошибки решения
ex G и ее составляющих от k
Рис. 2. Зависимость ошибки решения
ex Q и ее составляющих от k
1.E-10
1.E-09
1.E-08
1.E-07
1.E-06
1.E-05
1.E-04
1.E-03
1.E-02
1.E-01
1.E+00
1.E+01
1.E+02
1.E+03
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39
k
e_
y
G
e_y G 1e-2 e_y G_1 e_y G_2
e_y G 1e-3 e_y G_1 e_y G_2
e_y G 1e-4 e_y G_1 e_y G_2
1.E-10
1.E-09
1.E-08
1.E-07
1.E-06
1.E-05
1.E-04
1.E-03
1.E-02
1.E-01
1.E+00
1.E+01
1.E+02
1.E+03
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39
k
e_
y
Q
e_y Q 1e-2 e_y Q_1 e_y Q_2
e_y Q 1e-3 e_y Q_1 e_y Q_2
e_y Q 1e-4 e_y Q_1 e_y Q_2
Рис. 3. Зависимость ошибки
восстановления выхода ey G и ее
составляющих от k
Рис. 4. Зависимость ошибки
восстановления выхода ey Q и ее
составляющих от k
Е.Г. Ревунова, 2013
ISSN 0452-9910. Кибернетика и вычисл. техника. 2013. Вып. 173
42
ЗАДАЧА ПРЕОБРАЗОВАНИЯ ВЫХОДА
Пусть имеется линейная система, вектор выхода которой b формируется
путем линейного преобразования входного вектора (входа) х и добавления
аддитивного шума: Ax + ε = b. Например, это может быть измерительная
система, где дискретно заданный сигнал объекта измерения x неизвестен,
b — наблюдаемый выход («сигнальный образ» x), матрица A описывает
взаимодействие сигнала со средой и/или особенности измерительных средств
(детектора, преобразователя сигнала и т.п.). Столбцы A можно рассматривать
как отсчеты дискретно заданных базисных функций линейной системы.
Например, это могут быть функции отклика детектора спектрометра [16].
Набор базисных функций A отражает свойства конкретной
измерительной системы, т.е. не может быть произвольным. Поэтому
наблюдаемый выход b, который определяется базисными функциями A,
может не соответствовать требованиям пользователя, либо может быть
несовместимым с методами последующей обработки. С другой стороны, если
известен набор базисных функций C, которые дали бы выход с требуемыми
свойствами, можно поставить задачу нахождения преобразования
наблюдаемого выхода b в выход системы С с базисом C.
Будем искать преобразование выхода как линейное преобразование. Для
случая, когда известен вектор шума и его ковариационная матрица не
вырождена, а также не вырождена матрица базисных функций A, взвешенная
ковариационной матрицей шума, в [17] предлагается получать искомое
преобразование с использованием обращения A. Однако, если А имеет
высокое число обусловленности и ряд ее сингулярных чисел плавно спадает
к нулю, получаемое с использованием обратной матрицы решение (результат
преобразования в выход системы С) является неустойчивым. Поэтому
актуальной задачей является разработка устойчивых и вычислительно
эффективных методов преобразования выхода линейной системы в выход
системы с заданным базисом.
Матрицы базисных функций с указанными свойствами часто
встречаются на практике в задачах обработки сигналов в геофизической
разведке (электроразведка, магниторазведка, сейсморазведка, гравиразведка),
спектрометрии (например, гамма-спектрометрия), медицинской диагностике
(визуализация, томография) и др. Для получения устойчивого решения в этих
случаях требуется использовать регуляризацию [10]. В данной статье
предлагается подход к устойчивому решению задачи преобразования выхода,
основанный на использовании случайных проекций и QR-разложения.
Пусть сигнал b получен с выхода линейной системы А, выполняющей
преобразование
Ax + ε = b, (25)
где A∈ ℜm×n, x∈ℜn, b ∈ℜm, и
Ax = b0. (26)
Е.Г. Ревунова, 2013
ISSN 0452-9910. Кибернетика и вычисл. техника. 2013. Вып. 173
43
Выход линейной системы С обозначим как d0
Cx = d0. (27)
Для получения решения — оценки выхода системы С по b — сначала
получим оценку х' входа х, решив обратную задачу:
х' = P b, (28)
где P — оператор (матрица), преобразующий выход b в х'.
Затем получим оценку выхода системы C:
d' = C х' = C P b = Tb (29)
Таким образом, оператор CP преобразует b в d'. Матрицу
преобразования T = CP называют матрицей редукции в [17].
Конкретный вид P зависит от свойств матрицы А. Если ряд собственных
чисел А спадает монотонно и число обусловленности велико, то задачу
относят к классу дискретных некорректных задач, рассмотренных выше.
ПРЕОБРАЗОВАНИЕ ВЕКТОРА ВЫХОДА С ИСПОЛЬЗОВАНИЕМ СЛУЧАЙНОГО
ПРОЕКТОРА
Используя предложенный нами подход к устойчивому решению
дискретной некорректной задачи на основе рандомизации [8] Получим
оценку сигнала входа х'. Умножим обе части (25) на матрицу G ∈ ℜk×n, nk ≤ ,
элементы которой являются реализациями случайной величины с гауссовым
распределением с нулевым средним и единичной дисперсией. Таким образом
осуществляется преобразование (проекция) в пространство, координатные
оси которого являются случайными векторами. Эта операция имеет простую
нейросетевую реализацию посредством однослойного персептрона со
связями, веса которых – реализации случайной величины (рис. 5).
Рис. 5. Однослойный персептрон со случайными связями
Получаем выражение
GAx = Gb, (30)
Е.Г. Ревунова, 2013
ISSN 0452-9910. Кибернетика и вычисл. техника. 2013. Вып. 173
...
1 n
R
...
1 k
...
44
где GA ∈ ℜk×n, Gb∈ ℜk. Число столбцов n определяется размерностью
матрицы A, число строк k априорно неизвестно. Решение задачи наименьших
квадратов получим с помощью псевдообратной матрицы (GA)+:
х' = (GA)+ Gb. (31)
С учетом (31), получим оценку выхода d' системы С в виде:
d' = C х' = C (GA)+ Gb = Tb, (32)
где T = C (GA)+ G.
Запишем выражение для ошибки преобразования вектора выхода:
d' – d0 = C (GA)+ G(b0 + ε) – C х = C (GA)+ Gb0 – C х + C (GA)+ Gε. (33)
Составляющие ошибки преобразования вектора выхода:
e1 = C (GA)+ Gb0 – C х, e1 = C (GA)+ Gε. (34)
Усредним норму ошибки по реализациям шума:
e = E ||C(GA)+Gb0 – Cх||2 + E ||C(GA)+Gε||2 +
+ 2 E〈C(GA)+Gb0 – Cх, C(GA)+Gε〉.
(35)
Учитывая, что 2E〈C(GA)+Gb0 – Cх, C(GA)+Gε〉 = 0, E||C(GA)+Gε||2 =
= σ2trace(GT(GA)+ТCT C(GA)+G), получим следующее выражение для
среднеквадратичной ошибки преобразования вектора выхода:
e = E ||C(GA)+ Gb0 – Cх ||2 + σ2 trace(GT(GA)+ТCTC(GA)+G). (36)
Запишем выражение для вектора ошибки преобразования выхода в
случае проецирования матрицей Q, для этого при вычислении d' используем
в качестве х' оценку по (7):
d' – d0 = C (QTA)+QT (b0 + ε) – C х =
= C((QTA)+QTb0 – I)х + C (QTA)+ QT ε.
(37)
Учитывая, что 2E < C((QTA)+QTb0 – I)х, C(QTA)+QTε > = 0,
Е(C(QTA)+QTε) = σ2trace(Q(QTA)+ТCT C(QTA)+QT), QQT = I, получим
следующее выражение для среднеквадратичной ошибки преобразования
вектора выхода при проецировании матрицей Q:
e = E || C ((QTA)+ QT A – I) х ||2 + σ2 trace((QTA)+ТCTC(QTA)+). (38)
Для ошибки преобразования выхода, полученной в случае использования
проекционной матрицы (G или Q), построим зависимость нормы смещения,
дисперсии и суммарной ошибки от размерности матрицы k.
Для проведения численного эксперимента сформируем матрицы А и С
так, что столбцы содержат N отсчетов радиальных базисных функций:
fn(z) = exp(–g(z–с)2), с = dn + b, (d = 5, b = 20), z = {1, …, 100}, n — номер
базисной функции. Для исходной линейной системы g = 0,05, для системы С
значение g = 0,3. Компоненты вектора x назначим следующими: x5 = 1,
Е.Г. Ревунова, 2013
ISSN 0452-9910. Кибернетика и вычисл. техника. 2013. Вып. 173
45
x6 = 0,5, x10 = 1, x11 = 0,26, x12 = 0,25, другие компоненты вектора
x — нулевые. Векторы b0, d0, получим, как Ax, Cx соответственно. В
качестве шума будем использовать случайную величину с гауссовым
распределением и среднеквадратичным отклонением {5е-4, 5е-6, 5е-8}.
Пример зависимостей для проецирования матрицами G и Q приведен на
рис.6, 7.
Как видно из рисунков, для преобразования выхода с использованием
проецирования матрицами G и Q зависимость e от k имеет минимум при
k < N. С ростом уровня шума положение минимума смещается в область
меньших значений k, а ошибка в точке минимума растет. Оптимальным
числом строк k проекционной матрицы следует считать такое, при котором
минимальна среднеквадратичная ошибка преобразования выхода.
ВЫВОДЫ
Предложенный подход к преобразованию выхода обеспечивает
достаточно точное и устойчивое преобразование выхода линейной системы в
выход системы с заданным базисом для случая, когда матрица A базисных
функций исходной линейной системы имеет высокое число обусловленности
и ряд ее сингулярных чисел плавно спадает к нулю.
Для рандомизированного метода решения дискретной некорректной
задачи получены выражения для ошибки восстановления сигнала выхода и
проведено экспериментальное исследование зависимости ошибки от
размерности матрицы проектора. Численный эксперимент показал, что
значения ошибки восстановления сигнала выхода с использованием
проекционной матрицы Q в точке минимума меньше минимальных значений
ошибки для проекционной матрицы G, поэтому для восстановления сигнала
выхода предпочтительно использование проекционной матрицы Q.
1. Revunova E.G., Rachkovskij D.A. Using randomized algorithms for solving discrete
ill-posed problems. Information Theories and Applications, 2009, no. 2, pp. 176–192.
2. Рачковский Д.А. Рандомизированные проекционные методы формирования бинарных
разреженных векторных представлений / Д.А. Рачковский, И.С. Мисуно,
С.В. Слипченко // Кибернетика и системный анализ. — 2012. — № 1. — С. 176–188.
1.E-18
1.E-16
1.E-14
1.E-12
1.E-10
1.E-08
1.E-06
1.E-04
1.E-02
1.E+00
1.E+02
1.E+04
1.E+06
1.E+08
1.E+10
1.E+12
1 6 11 16 21 26 31 36 41 46 51 56 61 66 71 76 81 86 91 96
k
e
G
e G 5e-4 e_1 G e_2 G
e G 5e-6 e_1 G e_2 G
e G 5e-8 e_1 G e_2 G
1.0E-18
1.0E-16
1.0E-14
1.0E-12
1.0E-10
1.0E-08
1.0E-06
1.0E-04
1.0E-02
1.0E+00
1.0E+02
1.0E+04
1.0E+06
1.0E+08
1.0E+10
1.0E+12
1 6 11 16 21 26 31 36 41 46 51 56 61 66 71 76 81 86 91 96
k
e
Q
e Q 5e-4 e_1 Q e_2 Q
e Q 5e-6 e_1 Q e_2 Q
e Q 5e-8 e_1 Q e_2 Q
Рис. 6. Зависимость ошибки e от
размерности k для метода с
использованием проектора G
Рис. 7. Зависимость ошибки e от
размерности k для метода с
использованием проектора Q
Е.Г. Ревунова, 2013
ISSN 0452-9910. Кибернетика и вычисл. техника. 2013. Вып. 173
46
Rachkovskij D.A., Misuno I.S., Slipchenko S.V. Randomized projective methods for the
construction of binary sparse vector representations. Cybernetics and Systems Analysis, 2012,
vol. 48, no. 1, pp. 146–156.
3. Амосов Н.М. Моделирование мышления и психики / Н.М. Амосов. — К. : Наукова
думка, 1965. — 304 с.
Amosov N. M. Modelling of thinking and the mind. New York: Spartan Books, 1967., 304 p.
4. Нейрокомпьютеры и интеллектуальные роботы / Н.M. Амосов, T.Н. Байдык,
A.Д. Гольцев и др. — К. : Наукова думка, 1991. — 269 c.
Amosov N.M., Baidyk T.N., Goltsev A.D., Kasatkin A.M., Kasatkina L.M., Kussul T.M.,
Rachkovskij D.A. Neurocomputers and intelligent robots. Kiev: Naukova dumka, 1991.
269 p.
5. Куссуль Э.M. Ассоциативные нейроподобные структуры / Э.M. Куссуль. — К. :
Наукова думка, 1992. — 144 с.
Kussul E.M. Associative neuron-like structures. Kiev: Naukova Dumka, 1992. 144 p.
6. Kussul E.M., Baidyk T.N., Wunsch D.C. Neural Networks and Micro Mechanics. New York:
Springer, 2009. 210 p.
7. Ревунова Е.Г. Исследование составляющих ошибки для решения обратной задачи с
использованием случайных проекций / Е.Г. Ревунова. — Математические машины и
системы. — 2010. — № 4. — С. 33–42.
Revunova E.G. Study error components for solving the inverse problem using random
projections. Mathematical Machines and Systems, 2010, no. 4, pp. 33–42.
8. Рачковский Д.А. Рандомизированный метод решения дискретных некорректных задач
/ Д.А. Рачковский, Е.Г. Ревунова // Кибернетика и системный анализ. — 2012. — № 4.
— С. 163–181.
Rachkovskij D.A., Revunova E.G. Randomized method for solving discrete ill-posed
problems. Cybernetics and Systems Analysis, 2012, vol. 48, no. 4, pp. 621–635.
9. Hansen P.C. Rank-deficient and discrete ill-posed problems. Numerical Aspects of Linear
Inversion. Philadelphia: SIAM, 1998. 247 p.
10. Tikhonov A.N., Arsenin V.Y., Winston V.H. Solution of ill-posed problems. Washington,
DC, 1977.
11. Halko N., Martinsson P.G., Tropp J.A. Finding structure with randomness: Stochastic
algorithms for constructing approximate matrix decompositions. ACM Report, Caltech, 2009,
no. 2009-5, pp. 1–82.
12. Drineas P., Mahoney M.W., Muthukrishnan S. Sampling algorithms for l2 regression and
applications. Proc. of the 17th ACM-SIAM Symposium on Discrete Algorithms (SODA),
2006, pp.1127–1136.
13. Vogel C.R. Computational methods for inverse problems. Philadelphia: SIAM, 2002. 183 p.
14. Goldenshluger A., Pereverzev S.V. Adaptive estimation of linear functionals in Hilbert scales
from indirect white noise observations. Probab. Theory Relat. Fields, 2000, no. 118,
pp. 169–186.
15. Hansen P.C. Regularization Tools: A Matlab package for analysis and solution of discrete ill-
posed problems. Numer. Algorithms, 1994, vol. 6, pp. 1–35.
16. Rachkovskij D.A., Revunova E.G. Intelligent gamma-ray data processing for environmental
monitoring. Intelligent Data Processing in Global Monitoring for Environment and Security.
Kiev-Sofia: ITHEA, 2011. pp. 136–157.
17. Пытьев Ю.П. Математические методы интерпретации эксперимента / Ю.П. Пытьев. —
М : Высшая школа. — 1989. — 351 с.
Pytyev Yy.P. Mathematical methods of interpretation of the experiment. Moscow: High
school. 1989. 351 p.
Получено 18.04.2013
Е.Г. Ревунова, 2013
ISSN 0452-9910. Кибернетика и вычисл. техника. 2013. Вып. 173
|
| id | nasplib_isofts_kiev_ua-123456789-84481 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0452-9910 |
| language | Russian |
| last_indexed | 2025-12-07T17:55:59Z |
| publishDate | 2013 |
| publisher | Міжнародний науково-навчальний центр інформаційних технологій і систем НАН України та МОН України |
| record_format | dspace |
| spelling | Ревунова, Е.Г. 2015-07-08T18:45:58Z 2015-07-08T18:45:58Z 2013 Подход рандомизации в задачах восстановления сигналов по результатам непрямых измерений / Е.Г. Ревунова // Кибернетика и вычислительная техника. — 2013. — Вип. 173. — С. 35-46. — Бібліогр.: 17 назв. — рос. 0452-9910 https://nasplib.isofts.kiev.ua/handle/123456789/84481 004.942+623.454.862 Предложен подход к устойчивому решению задачи преобразования выхода, основанный на использовании случайных проекций и QR-разложения, проведено экспериментальное исследование поведения зависимости ошибки и ее составляющих от размерности матрицы проектора. Для рандомизированного метода решения дискретной некорректной задачи приведены выражения для ошибки восстановления сигнала выхода, проведено исследование зависимости ошибки от размерности матрицы проектора. Запропоновано підхід до стійкого вирішення завдання перетворення виходу, заснований на використанні випадкових проекцій і QR-розкладання, проведено експериментальне дослідження поведінки залежності помилки і її складових від розмірності матриці проектора. Для рандомізованого методу розв'язання дискретної некоректної задачі наведено вирази для помилки відновлення сигналу виходу, проведено експериментальне дослідження залежності помилки від розмірності матриці проектора. The purpose is to develop approaches to regularization that provide solution accuracy at the level of Tikhonov regularization, but with less computational complexity. ru Міжнародний науково-навчальний центр інформаційних технологій і систем НАН України та МОН України Кибернетика и вычислительная техника Информационные технологии и системы Подход рандомизации в задачах восстановления сигналов по результатам непрямых измерений Підхід рандомізації в задачах відновлення сигналів за результатами непрямих вимірювань Randomization approach to the recovery of signals resulted from indirect measurements Article published earlier |
| spellingShingle | Подход рандомизации в задачах восстановления сигналов по результатам непрямых измерений Ревунова, Е.Г. Информационные технологии и системы |
| title | Подход рандомизации в задачах восстановления сигналов по результатам непрямых измерений |
| title_alt | Підхід рандомізації в задачах відновлення сигналів за результатами непрямих вимірювань Randomization approach to the recovery of signals resulted from indirect measurements |
| title_full | Подход рандомизации в задачах восстановления сигналов по результатам непрямых измерений |
| title_fullStr | Подход рандомизации в задачах восстановления сигналов по результатам непрямых измерений |
| title_full_unstemmed | Подход рандомизации в задачах восстановления сигналов по результатам непрямых измерений |
| title_short | Подход рандомизации в задачах восстановления сигналов по результатам непрямых измерений |
| title_sort | подход рандомизации в задачах восстановления сигналов по результатам непрямых измерений |
| topic | Информационные технологии и системы |
| topic_facet | Информационные технологии и системы |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84481 |
| work_keys_str_mv | AT revunovaeg podhodrandomizaciivzadačahvosstanovleniâsignalovporezulʹtatamneprâmyhizmerenii AT revunovaeg pídhídrandomízacíívzadačahvídnovlennâsignalívzarezulʹtatamineprâmihvimírûvanʹ AT revunovaeg randomizationapproachtotherecoveryofsignalsresultedfromindirectmeasurements |