Оценка временного положения сигнала по сжатым данным на основе теории Compressive Sensing

Размещено на http: //www. allbest. ru/

Воронежский государственный университет (ВГУ), Воронеж, Россия

Оценка временного положения сигнала по сжатым данным на основе теории Compressive Sensing

В.И. Парфенов, Д.Ю. Голованов

Аннотация

сверхкороткий сигнал шум дискретный

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

Ключевые слова: Compressive Sensing; сверхкороткий сигнал; смещение оценки; рассеяние оценки; отношение сигнал/шум; степень сжатия.

Abstract

TIME DELAY ESTIMATION OF ULTRASHORT SIGNAL USING COMPRESSED DATA BASED ON THE THEORY OF COMPRESSIVE SENSING

V. I. Parfenov1, D. Y. Golovanov1

1Voronezh State University (VSU), Voronezh, Russia

In this paper, in order to reduce the number of operations performed in the estimator, an algorithm that allows one to estimate the time delay of the ultrashort signal observed against the additive white Gaussian noise during discrete processing was proposed. This algorithm is based on the methods of the Compressive Sensing theory. A statistical simulation of the proposed algorithm was performed and the dependences of the bias and dispersion of estimate on the signal to noise ratio and compression level were obtained. In order to determine the conditions of practical applicability, the paper compares the accuracy of the estimates for the proposed algorithm and the classical maximum likelihood algorithm.

Keywords: Compressive Sensing; ultrashort signal; bias of estimate; dispersion of estimate; signal to noise ratio; compression level.

Введение

Задача оценки параметров сигналов является классической задачей радиофизики, решению которой посвящено большое количество статей и монографий (см., например, [1-3] и др.). Часто ее решение основывается на поиске абсолютного максимума некоторой достаточной статистики , зависящей от оцениваемых параметров . При этом оценка

, , , ,

где - априорный интервал возможных значений параметра .

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

Число каналов измерителя может оказаться очень большим и практически нереализуемым даже в случае оценки только одного параметра, если велик априорный интервал его возможных значений по сравнению с шириной математического ожидания достаточной статистики (сигнальной функции [1,4]). Такая ситуация на практике встречается довольно часто, например, при оценке временного положения сверхкоротких сигналов [5,6]. Большое число каналов не только создает сложности при практической реализации измерительных устройств, но и существенно увеличивает время вынесения решения. Так что поиск способов решения этой проблемы в современных радиофизических системах является приоритетной задачей.

1. Основные принципы теории Compressive sensing

Активно развивающаяся в последние несколько лет новая область получения и обработки информации, получившая в англоязычной литературе название Compressive Sensing (CS), утверждает, что сигналы, имеющие разреженное или сжатое представление в некотором базисе, могут быть точно или приближенно восстановлены по своим линейным проекциям, причем число этих проекций может быть значительно меньше размерности исходного сигнала [7-11].

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

Однако на практике наиболее часто встречаются не разреженные, а сжимаемые сигналы. Сигнал называется сжимаемым, если у него лишь небольшое число компонент имеют достаточно большие по величине значения, а остальные относительно малы.

Если сам вектор не удовлетворяет одному из этих условий, то почти всегда можно найти его представление в каком-либо базисе, т.е. представить его в виде , где - вектор-столбец коэффициентов в выбранном базисе (Фурье, вейвлет и пр.), - базисная матрица размера , причем поведение коэффициентов во многих случаях будет удовлетворять либо перечисленным выше условиям разреженности либо сжимаемости.

Введем в рассмотрение вектор размера , а также матрицу , удовлетворяющую определенным условиям, таким образом, что

. (1)

Задача, формулируемая в рамках теории CS, состоит в том, чтобы восстановить вектор по совокупности его линейных измерений, то есть по вектору , причем практический интерес в рамках этой теории представляет случай . Так как , получившаяся система уравнений является недоопределенной, а, следовательно, имеет бесконечное множество решений. То есть однозначно восстановить вектор без дополнительной информации невозможно. Однако, если учесть, что восстанавливаемый сигнал является разреженным или сжимаемым, то при определенных условиях это становится возможным.

Матрица не может быть произвольной, она должна удовлетворять определенным условиям [7-11], которые часто формулируются в виде свойства ограниченной изометрии (Restricted Isometry Property или RIP) [10,11].

С большой вероятностью свойство RIP может быть достигнуто за счет выбора случайной матрицы в качестве , то есть за счет рандомизации процесса измерения. При этом вектор результатов измерений представляет собой набор различных линейных комбинаций компонент вектора со случайно выбранными весами [10,11].

Было показано, что в качестве матрицы целесообразно выбирать матрицу со случайными элементами, распределенными, например, по нормальному закону, закону Бернулли и другим законам распределения.

Алгоритм восстановления сигнала должен на основании вектора измерений , матрицы размера (или, в случае случайного характера ее формирования, на основании закона, в соответствии с которым она была сгенерирована), восстановить сигнал длины или разреженный вектор коэффициентов при условии, что .

Наиболее эффективно задачу CS можно решить посредством минимизации нормы [7-11]:

,

при условии, что

.

Это задача выпуклой оптимизации, поскольку норма является выпуклой функцией, которая может быть сведена к задаче линейного программирования, известной как выбор базиса (basis pursuit).

На практике чаще встречается ситуация, описываемая не моделью (1), а моделью вида:

, (2)

в которой вектор размера является шумовой составляющей.

Следует отметить, что существуют различные методы решения задач типа (1) и (2). Наряду с методами линейного программирования [10,11] могут применяться и так называемые «грубые» алгоритмы (greedy algorithms). К ним относятся, например, Orthogonal Matching Pursuit (OMP) [12,13], Regularized Orthogonal Matching Pursuit (ROMP) [14], Compressive Sampling Matching Pursuit (CoSaMP) [15] и другие.

2. Алгоритм оценки временного положения сверхкороткого сигнала на основе теории Compressive Sensing

Пусть сверхкороткий сигнал наблюдается на фоне белого гауссовского шума с односторонней спектральной плотностью мощности , так что входное колебание имеет вид:

, , (3)

где - время наблюдения реализации. Рассмотрим задачу оценки временного положения такого сигнала. Как известно, оценка максимального правдоподобия неизвестного параметра сигнала находится как положение абсолютного максимума логарифма функционала отношения правдоподобия, который для данной задачи может быть представлен в виде [1]

Параметр является неэнергетическим, поэтому достаточная статистика равна

(4)

При дискретной обработке вместо непрерывной реализации (3) будем иметь ее отсчеты, взятые с шагом :

, ,

где - отсчеты полезного сигнала при , - отсчеты белого гауссовского шума, - их количество. Тогда (4) с точностью до постоянного множителя можно записать в виде

, (5)

где .

Разобьем далее априорный интервал неизвестного параметра на подынтервалы с шагом и получим количество отсчетов . Тогда выражение (5) в матричном виде запишется следующим образом:

(6)

где - вектор отчетов достаточной статистики, - вектор отсчетов реализации, - матрица размера , элементы которой

(, ).

Чтобы найти оценку , для каждого из значений () из априорного интервала необходимо сформировать статистику (6). Количество отсчетов и может быть достаточно большим, при этом количество операций умножения для формирования всех отсчетов вектора равно , что также очень велико.

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

1) Пропустить реализацию через пороговое устройство с некоторым порогом с целью ее прореживания, так что

, .

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

2) В приемном устройстве сформировать матрицу , элементами которой будут независимые и одинаково распределенные случайные величины. Например, могут быть выбраны гауссовские случайные величины с нулевыми математическими ожиданиями и единичными дисперсиями. Величина выбирается из условия . Далее эта матрица умножается на матрицу из (9), в результате чего получаем матрицу

размера . Следует отметить, что эти операции могут быть выполнены до начала обработки входного колебания в приемном устройстве.

3) Получить вектор линейных измерений

размера ,

где - вектор отсчетов прореженной реализации. При этом для получения вектора требуется всего операций умножения, что существенно меньше, чем при формировании классической статистики (6).

4) Зная матрицу и вектор , используя теорию CS, восстановить вектор

,

то есть найти его оценку , решив выпуклую оптимизационную задачу вида:

, при условии, что ,

которая, как отмечалось выше, может быть сведена к задаче линейного программирования.

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

 .

Отнормируем интервал наблюдения реализации к единице, т.е. ; установим априорный интервал неизвестного параметра , где -длительность сигнальной функции. Установим для определенности значение ; в соответствие с теоремой Котельникова выберем шаг дискретизации сигнала и положим его равным ; установим, также в соответствие с теоремой Котельникова, шаг дискретизации по параметру равным (количество получаемых отсчетов ). Сформируем матрицу размера так, чтобы каждый ее элемент представлял собой случайную величину, распределенную по нормальному закону с нулевым математическим ожиданием и единичной дисперсией. Более того, подвергнем эту матрицу стандартной процедуре ортонормализации [16]. Далее, после проведения компьютерного моделирования предложенного алгоритма, при котором количество испытаний для каждого набора параметров составляло не менее 30000, получим ряд зависимостей смещения и рассеяния оценки от различных параметров для описанного выше алгоритма.

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

На рисунке 1 изображена зависимость смещения оценки для алгоритма CS от степени сжатия при различных значениях отношения сигнал/шум

,

где - энергия сигнала (кривые 1 и 2 построены при и 6 соответственно).

Рис. 1 Зависимость смещения оценки от отношения для алгоритма CS при различных значениях отношения сигнал/шум

Аналогично на рисунке 2 изображена зависимость смещения оценки для алгоритма CS от отношения сигнал/шум z при разных значениях степени сжатия (кривые 1 и 2 построены при =15/354 и 30/354 соответственно)

Рис. 2 Зависимость смещения оценки от отношения сигнал/шум z для алгоритма CS при различных значениях

Из анализа приведенных зависимостей следует, что смещение оценки уменьшается по абсолютной величине с ростом отношения сигнал/шум z и степени сжатия . Кроме того, смещение оценки стремится к 0 при , т.е. оценка является асимптотически несмещенной даже при .

Далее приведем аналогичные зависимости для рассеяния оценки. Так, на рисунке 3 представлена зависимость рассеяния оценки для алгоритма CS от отношения для ряда значений z (кривые 1 и 2 построены при и 6 соответственно).

Рис. 3 Зависимость рассеяния оценки от отношения для алгоритма CS при различных значениях отношения сигнал/шум z

Далее на рисунке 4 изображена зависимость рассеяния оценки для алгоритма CS от отношения сигнал/шум для ряда значений (кривые 1 и 2 построены при соответственно =15/354 и 30/354). Кроме того на этом рисунке изображена зависимость рассеяния оценки для классического алгоритма от (кривая 3).

Рис. 4 Зависимость рассеяния оценки от отношения сигнал/шум z для алгоритма CS при различных значениях и классического алгоритма оценки

Как следует из анализа представленных рисунков, рассеяние оценки убывает с увеличением отношения сигнал/шум z и степени сжатия .

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

Заключение

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

Литература

1. Куликов Е.И., Трифонов А.П. Оценка параметров сигналов на фоне помех. М.: Советское радио, 1978. - 296 с.

2. Шинаков Ю.С., Трифонов А.П. Совместное различение сигналов и оценка их параметров на фоне помех. М.: Радио и связь, 1986. - 264 с.

3. Парфенов В.И. Прием радиосигналов в каналах с замираниями типа Накагами // Известия вузов. Радиоэлектроника, 2005, Т.48, №10. - С. 73 - 80.

4. Трифонов А.П., Нечаев Е.П., Парфенов В.И. Обнаружение стохастических сигналов с неизвестными параметрами. Воронеж: Воронежский государственный университет, 1991. - 246 с.

5. Радзиевский В.Г., Трифонов П.А. Обработка сверхширокополосных сигналов и помех. М.: Радиотехника, 2009. - 290 с.

6. Астанин Л.Ю., Костылев А.А. Основы сверхширокополосных радиолокационных измерений. М.: Радио и связь, 1989. - 190 с.

7. Baraniuk R. Compressive sensing // IEEE Signal Processing Magazine, 2007, Vol. 24, №4. - P. 118 - 121.

8. Hayashi K. A User's guide to compressed sensing for communications systems / Hayashi K., Nagahara M., Tanaka T. // IEICE Transaction on communications, 2013, Vol. E96-B, №3 - P. 685 - 712.

9. Candes E. An introduction to compressive sampling / Candes E., Wakin M. // IEEE Signal Processing Magazine, 2008, Vol. 25, №2. - P. 21 - 30.

10. Foucart S., Rauhut H. A mathematical introduction to compressive sensing. Springer, 2013. - 625 p.

11. Eldar C., Kutyniok G. Compressed sensing: theory and applications. Cambridge University Press, 2012. - 555 p.

12. Tropp J. Signal recovery from random measurements via orthogonal matching pursuit / Tropp J., Gilbert A. // IEEE Transaction on Information Theory, 2007, Vol. 53, №12. - P. 4655 - 4666.

13. Cai T. Orthogonal matching pursuit for sparse signal recovery with noise / Cai T., Wang L. // IEEE Transaction on Information Theory, 2011, Vol. 57, №7. - P. 4680 - 4688.

14. Needell D. Signal recovery from incomplete and inaccurate measurements via regularized orthogonal matching pursuit / Needell D., Vershynin R. // IEEE Journal of Selected Topics in Signal Processing, 2010, Vol. 4, №2. - P. 310 - 316.

15. Needell D. CoSaMP: Iterative signal recovery from incomplete and inaccurate samples / Needel D., Tropp J. // Applied and Computational Harmonic Analysis, 2009, Vol. 26, №3. - P. 301 - 321.

16. Стренг Г. Линейная алгебра и ее применения. Пер. с англ. Ю.А. Кузнецова и Д.М. Фаге, под ред. Г.И. Марчука. М.: Мир, 1980. - 456 с.

References

1. Kulikov, E.I., Trifonov, A.P. Estimation of parameters of signals on a noise background. M.: Soviet radio, 1978. - 296 p.

2. Shinakov, Y.S., Trifonov, A.P. The discrimination of signals combined with the estimation of their parameters on a noise background. М.: Radio and communication, 1986. - 264 с.

3. Parfenov, V.I. Reception of radiosignals in the channel with fadings of Nakagami type. // Radioelectronics and Communications Systems, 2005, Vol. 48, No. 10. - pp. 73 - 80.

4. Trifonov, A.P., Nechaev, E.P., Parfenov, V.I. Detection of the stochastic signals with the unknown parameters. Voronezh: Voronezh State University, 1991. - 246 p.

5. Radzievsky, V.G., Trifonov, P.A. Processing of ultrawideband signals and hindrances. M.: Radio engineering, 2009. - 290 p.

6. Astanin, L.Y., Kostylev, A.A. Fundamentals of ultrawideband radiolocation measurements. M.: Radio and communication, 1989. - 190 p.

7. Baraniuk, R. Compressive sensing // IEEE Signal Processing Magazine, 2007, Vol. 24, No. 4. - pp. 118 - 121.

8. Hayashi, K., Nagahara, M., Tanaka, T. A User's guide to compressed sensing for communications systems // IEICE Transaction on communications, 2013, Vol. E96-B, No. 3 - pp. 685 - 712.

9. Candes, E., Wakin, M. An introduction to compressive sampling // IEEE Signal Processing Magazine, 2008, Vol. 25, No. 2. - pp. 21 - 30.

10. Foucart, S., Rauhut, H. A mathematical introduction to compressive sensing. Springer, 2013. - 625 p.

11. Eldar, C., Kutyniok, G. Compressed sensing: theory and applications. Cambridge University Press, 2012. - 555 p.

12. Tropp, J., Gilbert, A. Signal recovery from random measurements via orthogonal matching pursuit // IEEE Transaction on Information Theory, 2007, Vol. 53, No. 12. - pp. 4655 - 4666.

13. Cai, T., Wang, L. Orthogonal matching pursuit for sparse signal recovery with noise // IEEE Transaction on Information Theory, 2011, Vol. 57, No. 7. - pp. 4680 - 4688.

14. Needell, D., Vershynin, R. Signal recovery from incomplete and inaccurate measurements via regularized orthogonal matching pursuit // IEEE Journal of Selected Topics in Signal Processing, 2010, Vol. 4, No. 2. - pp. 310 - 316.

15. Needell, D., Tropp, J. CoSaMP: Iterative signal recovery from incomplete and inaccurate samples // Applied and Computational Harmonic Analysis, 2009, Vol. 26, No. 3. - pp. 301 - 321.

16. Strang, G. Linear algebra and its application. New York: Academic Press, 1976 - 374 p.

Размещено на Allbest.ru