ФРЕЙМЫ ОБЩЕГО ПОЛОЖЕНИЯ ПРИ ОЦЕНКЕ ВРЕМЕНИ ВОССТАНОВЛЕНИЯ СИГНАЛОВ БЕЗ ФАЗ

Научная статья
DOI:
https://doi.org/10.23670/IRJ.2017.57.063
Выпуск: № 3 (57), 2017
Опубликована:
2017/03/17
PDF

Кулешова А.А.

Аспирант, Федеральное государственное автономное образовательное учреждение высшего образования «Самарский национальный исследовательский университет имени академика С.П. Королева» в г. Самара

ФРЕЙМЫ ОБЩЕГО ПОЛОЖЕНИЯ ПРИ ОЦЕНКЕ ВРЕМЕНИ ВОССТАНОВЛЕНИЯ СИГНАЛОВ БЕЗ ФАЗ

Аннотация

Поиск быстрых алгоритмов для восстановления сигнала без фазы актуален в настоящее время. Алгоритмы восстановления важны в обработке разнообразных сигналов, в особенности в технологии распознавания речи, в томографии. Главное свойство фреймов, которое делает их настолько полезными в прикладных задачах – их избыточность. Хорошо выбранный фрейм может обеспечить численную устойчивость для восстановления сигнала и получение важных характеристик сигнала. Семейство фреймов восстанавливает сигнал по абсолютному значению фреймовых коэффициентов в полиномиальное время.

Ключевые слова: фрейм, восстановление сигнала без фаз, равномерные фреймы.

Kuleshova A.A.

Postgraduate student, Samara University in Samara

GENERAL FRAMES AT THE ASSESSMENT OF THE TIME  OF FOR SIGNAL RECONSTRUCTION WITHOUT PHASE

Abstract

Search of fast algorithms for doing signal reconstruction without phase is actual now. Algo-rithms of signal reconstruction are important in handling of various signals, in particular from speech recognition technology , in a tomography. The main property of frames which makes them so useful in applied problems is their redundancy. In general, a carefully chosen frame can provide numerical stability for reconstruction and an ability to capture important signal characteristics. The family of frames signal reconstruction on absolute value of frame coefficients in polynomial time.

Keywords: frame, reconstruction without phase, uniform frames.

Дискретизация и квантование аналогового сигнала дают возможность рассматривать сигнал как элемент конечномерного пространства V [1, C. 280].

По ортонормированному базису 02-03-2017 16-30-09 «сигнал» 02-03-2017 16-30-15 единственным образом может быть записан как сумма:

02-03-2017 16-30-24

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

Последние годы большое количество работ посвящено решению следующей задачи: найти такие системы «измерительных» векторов 02-03-2017 16-30-30, которые позволяют восстановить произвольный сигнал  02-03-2017 16-30-36 по набору вещественных чисел 02-03-2017 16-30-45.

Была доказана теоретическая возможность точного восстановления сигнала, если в качестве системы представления используются полные избыточные системы [2, P. 354].

Определение 1: Семейство векторов 02-03-2017 16-30-52 называется фреймом гильбертового пространства HN, если существуют константы А, В: 0 < A ≤ B < ∞, такие, что для всех x ∈ H выполняются следующие неравенства:

02-03-2017 16-31-10

A и B называются границами фрейма. Если A=B, то фрейм называется А-жестким, а если A=B=1, то фреймом Парсеваля-Cтеклова.

Числа 02-03-2017 16-31-34 называются фреймовыми коэффициентами.

Определение 2: Пусть 02-03-2017 16-31-42 - фрейм, линейное отображение:

02-03-2017 16-31-49

называется оператором анализа.

Определение 3: Линейное отображение:

02-03-2017 16-31-58

называется оператором синтеза.

Композиция отображений 02-03-2017 16-32-15 и 02-03-2017 16-32-06 определяет фреймовый оператор – положительный, самосопряженный обратимый оператор:

02-03-2017 16-32-26

Оператор S обеспечивает точную формулу для восстановления:

02-03-2017 16-32-32

Рассмотрим P - такое нелинейное отображение, переводящее вектор в набор модулей фреймовых коэффициентов:

02-03-2017 16-32-40

Если необходимо связать P с некоторым фреймом 02-03-2017 16-32-48, то запишем: 02-03-2017 16-32-54.

Пусть 02-03-2017 16-33-04 - фактор-пространство, полученное отождествлением двух векторов, если они отличаются постоянным фазовым коэффициентом. Таким образом, x~y означает, что существует такая константа c: |c|=1 , что y=cx.

Для вещественных Гильбертовых пространств 02-03-2017 16-33-18, тогда 02-03-2017 16-33-26.

Для комплексных гильбертовых пространств 02-03-2017 16-33-33, тогда 02-03-2017 16-33-41, где 02-03-2017 16-33-56 - окружность единичного радиуса на комплексной плоскости.

Нелинейное отображение P на 02-03-2017 16-34-09 действует так:

02-03-2017 16-34-20

Если 02-03-2017 16-34-29, множество I состоит из М-элементов,  02-03-2017 16-34-45. Тогда 02-03-2017 16-34-55.

Рассмотрим множество 02-03-2017 16-35-04 – это множество N-мерных линейных подпространств в 02-03-2017 16-35-12, которое имеет структуру 02-03-2017 16-35-20-мерного множества.

Множество 02-03-2017 16-35-04называется многообразием Грассмана.

Для фрейма 02-03-2017 16-35-38 оператор анализа удовлетворяет:

02-03-2017 16-35-46

где 02-03-2017 16-35-54 – канонический базис в 02-03-2017 16-35-12.

Рассматриваемое нелинейное отображение в вещественном случае:

02-03-2017 16-36-10

Если 02-03-2017 16-36-20, то для M-элементов фрейма 02-03-2017 16-36-26 оператор анализа:

02-03-2017 16-36-33

Скалярное произведение по определению: 02-03-2017 16-36-41

Нелинейное отображение:

02-03-2017 16-36-49

где два вектора 02-03-2017 16-37-01, если существует такая константа 02-03-2017 16-37-08, такая что 02-03-2017 16-37-15.

         Фреймы общего положения восстанавливают сигналы без фаз [1] и это восстановление достигается за полиномиальное время.

Определение 4: Фрейм 02-03-2017 16-37-22 называется фреймом общего положения, если 02-03-2017 16-37-32, где U – открытое по Зарисскому множество и 02-03-2017 16-37-39.

Теорема 1: (Вещественный случай) [3] Если 02-03-2017 16-37-46, то для фрейма общего положения 02-03-2017 16-37-53, нелинейное отображение P инъективно.

Доказательство: Предположим, что 02-03-2017 16-38-04 и 02-03-2017 16-38-10 имеют одинаковый образ при нелинейном отображении P. Пусть 02-03-2017 16-38-23 – фреймовые коэффициенты для 02-03-2017 16-39-06 и 02-03-2017 16-39-12 – фреймовые коэффициенты для 02-03-2017 16-39-18. Тогда 02-03-2017 16-39-25 для каждого 02-03-2017 16-39-32.

В частности, существует подмножество индексов 02-03-2017 16-39-39 таких, что 02-03-2017 16-39-48. Тогда два вектора 02-03-2017 16-38-04 и 02-03-2017 16-38-10 имеют одинаковый образ при отображении P тогда и только тогда, когда существует подмножество 02-03-2017 16-39-55, такое что оба набора фреймовых коэффициентов 02-03-2017 16-38-23 и 02-03-2017 16-40-05 находятся в некотором множестве 02-03-2017 16-40-32.

Для завершения доказательства мы покажем, что при 02-03-2017 16-40-45 такое условие невозможно для подпространств общего положения 02-03-2017 16-41-00.

Это означает, что множество таких подпространств 02-03-2017 16-40-32 представляет собой плотное открытое по Зарискому множество на многообразии Грассмана Gr(N, M). В частности, вероятность того, что случайно выбранное 02-03-2017 16-40-32 будет удовлетворять этому условию, равна 0.

Для завершения доказательства теоремы нам понадобится следующая лемма.

Лемма 1: Если 02-03-2017 16-40-45, то справедливо следующее утверждение для N-мерного подпространства общего положения 02-03-2017 16-41-00: пусть 02-03-2017 16-41-07, тогда 02-03-2017 16-41-15 тогда и только тогда, когда 02-03-2017 16-41-22.

Доказательство: Предположим, что 02-03-2017 16-41-30.

Так как 02-03-2017 16-41-36 - инволюция, то 02-03-2017 16-41-42 фиксировано и отлично от нуля. Таким образом, 02-03-2017 16-41-52.

Аналогично

02-03-2017 16-41-59

Следовательно, 02-03-2017 16-42-06.

Тогда 02-03-2017 16-42-13 и 02-03-2017 16-42-39- фиксированные линейные подпространства размерности 02-03-2017 16-42-46 и 02-03-2017 16-42-53 соответственно. Если 02-03-2017 16-42-59, то одно из этих подпространств является подпространством коразмерности больше или равной 02-03-2017 16-43-06. Однако линейное подпространство общего положения 02-03-2017 16-40-32 размерности 02-03-2017 16-43-06 имеет нулевое пересечение с фиксированным линейным подпространством  коразмерности больше или равной    02-03-2017 16-43-06 02-03-2017 16-43-22.

Поэтому, если 02-03-2017 16-40-32 - подпространство общего положения и для 02-03-2017 16-43-31, тогда 02-03-2017 16-43-38.

Доказательство теоремы следует из того, что если 02-03-2017 16-40-32 находится в пересечении общих условий, налагаемых предложением для каждого подмножества 02-03-2017 16-43-46, то 02-03-2017 16-40-32 удовлетворяет заключению теоремы.

Определение 5: Набор векторов 02-03-2017 16-44-01 в  02-03-2017 16-44-08 назовем альтернативно полным, если для любого 02-03-2017 16-44-16, либо 02-03-2017 16-44-21, либо 02-03-2017 16-44-27 полно в 02-03-2017 16-44-33.

Теорема 2: Пусть 02-03-2017 16-44-39 - набор векторов  в 02-03-2017 16-44-46. Отображение 02-03-2017 16-44-54 определено равенствами: 02-03-2017 16-45-00. Тогда отображение 02-03-2017 16-45-09 инъективно тогда и только тогда, когда F- альтернативно полно.

Доказательство:

(⇒) Предположим, что - не альтернативно полно. Следовательно, найдется 02-03-2017 16-45-29 такое, что ни 02-03-2017 16-45-35, ни 02-03-2017 16-45-41не полно в 02-03-2017 16-45-46.

Выбираем ненулевые векторы 02-03-2017 16-45-52  так, что  02-03-2017 16-46-00для всех 02-03-2017 16-46-06 и 02-03-2017 16-46-12 для всех 02-03-2017 16-46-17. Для каждого 02-03-2017 16-46-22 имеем:

02-03-2017 16-46-29

Отсюда следует, что 02-03-2017 16-46-36 для каждого 02-03-2017 16-46-22, и 02-03-2017 16-46-44. Более того, так как 02-03-2017 16-46-58 и 02-03-2017 16-47-03 ненулевые, по предположению, то и 02-03-2017 16-47-09. Таким образом, инъективности отображения 02-03-2017 16-45-09 нет.

(⇐) Предположим, что 02-03-2017 16-45-09 не инъективно. Это означает, что существуют векторы  02-03-2017 16-47-25 такие, что 02-03-2017 16-47-30 и 02-03-2017 16-47-36. Обозначим 02-03-2017 16-47-43.

Имеем:02-03-2017 16-47-50  для каждого 02-03-2017 16-47-55. Иначе, если 02-03-2017 16-48-00 тогда 02-03-2017 16-48-06 и тогда 02-03-2017 16-48-13. По предположению, 02-03-2017 16-48-18, поэтому 02-03-2017 16-48-25 . Таким образом, и 02-03-2017 16-48-32не полны в 02-03-2017 16-48-38.

Определение 6: Множество 02-03-2017 16-48-46 называется набором с полным спарком, если каждое его подмножество из N векторов полно в 02-03-2017 16-49-33.

Теорема 3: В вещественном случае, если 02-03-2017 16-49-27 в 02-03-2017 16-49-33 и 02-03-2017 16-49-00, то отображение 02-03-2017 16-49-06  не является инъективным. Если 02-03-2017 16-49-13, то отображение 02-03-2017 16-45-09 инъективно тогда и только тогда, когда 02-03-2017 16-49-27 - полный спарк.

Следствие 1: Если F это М–элементный фрейм в 02-03-2017 16-49-33 с 02-03-2017 16-49-38 и у 02-03-2017 16-49-48 каждые N-элементов  фрейма линейно независимы, то оператор 02-03-2017 16-49-54 - инъективен.

Примером такого фрейма является фрейм Мерседес-Бенц в 02-03-2017 16-50-01, состоящий из 3-х векторов единичной длины, расположенных под углом 120º.

Теорема 4: (Комплексный случай) Если M≥4N-2, то для фрейма общего положения F, отображение 02-03-2017 16-45-09 инъективно.

Теорема 5 [3],[5, P.372]: Пусть H – фиксированное N-мерное векторное пространство (вещественное или комплексное), пусть 02-03-2017 16-50-13– ортонормированный базис для H.

(а) Если 02-03-2017 16-50-19, 02-03-2017 16-50-26 и 02-03-2017 16-50-34– фрейм общего положения, нелинейное отображение  P – инъективно. Тогда вектор 02-03-2017 16-51-10 может быть восстановлен (с точностью до знака) из множества 02-03-2017 16-51-18 модулей фреймовых коэффициентов за полиномиальное число шагов 02-03-2017 16-51-26.

(б) Если 02-03-2017 16-51-35– фрейм общего положения, нелинейное отображение  P – инъективно. Тогда вектор  02-03-2017 16-51-10 может быть восстановлен (с точностью умножения на корень из единицы) из множества 02-03-2017 16-51-18 модулей фреймовых коэффициентов за полиномиальное число шагов 02-03-2017 16-51-26.

Список литературы / References

  1. Новиков С.Я. Полные системы в задачах восстановления сигнала / Новиков С.Я., Федина М.Е. // Труды Международной научно-технической конференции, Том 1 «Перспективные информационные технологии» – 2015. – С. 280–283.
  2. Balan. Fast algorithems for signal reconstruction without phase / R. Balan , B. G. Bodmann, P. G. Casazza, D. Edidin // Proceedings of SPIE-Wavelets XII, San Diego 6701 (2007) 670111920-670111932
  3. Balan. Painless reconstruction from magnitudes of frame coefficients, preprint / R. Balan, B. G. Bodman, P. G. Casazza and D. Edidin.
  4. Balan. On signal reconstruction without phase / R. Balan, P. Casazza, D. Edidin // Appl.Comput.Harmon.Anal. 20 –2006 – P. 345–356.
  5. Kuleshova A. [Electronic resource] Generic frame in problems for signal reconstruction without phase // ITNT 2016 Information Technology and Nanotechnology – 2016.–  P. 364-372. – URL: http://ceur-ws.org/Vol-1638/

Список литературы на английском языке / References in English

  1. Novikov S.J. Polnye sistemy v zadachah vosstanovlenija signala [Complete systems in problems of signal reconstruction] / Novikov S.J., Fedina M.E. // Trudy Mezhdunarodnoj nauchno-tehnicheskoj konferencii, Tom 1 «Perspektivnye informacionnye tehnologii» [Proceedings of the International Scientific and Technical Conference, Volume 1 "Perspective Information Technologies"] – 2015. – P. 280–283. [in Russian]
  2. R. Balan. Fast algorithems for signal reconstruction without phase / R. Balan , B. G. Bodmann, P. G. Casazza, D. Edidin // Proceedings of SPIE-Wavelets XII, San Diego 6701 (2007) 670111920-670111932
  3. R. Balan. Painless reconstruction from magnitudes of frame coefficients, preprint / R. Balan, B. G. Bodman, P. G. Casazza and D. Edidin.
  4. R. Balan. On signal reconstruction without phase / R. Balan, P. Casazza, D. Edidin // Appl.Comput.Harmon.Anal. 20 – 2006 – P. 345–356.
  5. A. Kuleshova [Electronic resource] Generic frame in problems for signal reconstruction witho