Фурье от данных с небольшим потерянным блоком

[ilghiz]

Добрый день,

имеется дискретный сигнал (скажем 512 точек), у него где-то с 20-50 точек, идущих друг за другом, которые потеряны. Исходный сигнал обычно имеет одну или несколько несущих и сколько-то белого шума.

Если потерянные данные забить нулями и сделать Фурье, то уровень шума подрастет.

Если начало-конец потерянных данных саппроксимировать линейно, то будет чуть лучше.

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

Скажите, пожалуйста, а есть ли какой-то "доказанно оптимальный" метод?

Спасибо!

[Pphantom]

ilghiz в сообщении #1549933 писал(а):

Если начало-конец потерянных данных саппроксимировать линейно, то будет чуть лучше.

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

Вопрос в том, что такое "лучше". Формально шум уменьшится, фактически же есть все шансы (особенно во втором случае) "улучшить" сигнал, внеся в него то, чего в нем не было.

ilghiz в сообщении #1549933 писал(а):

Скажите, пожалуйста, а есть ли какой-то "доказанно оптимальный" метод?

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

[ilghiz]

Спасибо большое, Pphantom, за ответ!

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

Pphantom в сообщении #1549934 писал(а):

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

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

Спасибо!

[Евгений Машеров]

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

[Евгений Машеров]

С другой стороны, можно попробовать перейти к параметрическому оцениванию. Если известно, что в спектре сигнала не более k пиков, то можно подогнать авторегрессионную модель порядка $2k$. А уж по ней оценивать спектр. Для оценки параметров модели использовать данные по тем отрезкам, по которым они есть, отсутствующие игнорируя. Скажем, посчитать автоковариацию по каждому отрезку и просуммировав.

[ilghiz]

Спасибо большое, Евгений Машеров,

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

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

Еще пробовал адаптивную кросс-аппроксимацию - то есть я взял по несколько соседних регионов той же длины, что и неизвестный, построил матрицу, и по ней кросс-аппроксимацию сделал, но работает довольно непредсказуемо, если ранг этой кросс-аппроксимации меньше $2k$, и, в общем-то это и очевидно.

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

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

[Евгений Машеров]

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

[novichok2018]

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

[ilghiz]

Спасибо большое, Евгений Машеров и novichok2018 за советы!

Евгений Машеров в сообщении #1549961 писал(а):

Ну вот я за зануление. Только как-то побороться со скачками на границе выпавших данных.

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

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

2 novichok2018 Как я понял, Вы имели ввиду Микеладзе, Шалва Ефимович, но его книга вышла даже до Кули-Тьюки алгоритма... Маловероятно, что там будет что-то, что могло бы помочь, да и достать ее как-то не просто, в Ленинку или БЕН теперь от меня прямые самолеты, к сожалению, не летают. Спасибо Вам на добром слове!

[novichok2018]

Уточню, что хотел сказать. Метод Микеладзе - это решение ДУ, когда нет данных, скажем, на всей границе области. Или интеграл, когда нет функции на части отрезка интегрирования, по каким формулам в некотором смысле оптимальным образом дополнить, хотя понятно, что задача некорректная. Фурье - это тоже интеграл, пусть нет значений на части прямой. Дискретный случай - связан с непрерывным. Кули и Тьюки здесь не нужны, БПФ, по крайней мере сразу.
Кажется, копия про эту задачу Микеладзе у меня есть, если сочтёте нужным, поищу.

[Pphantom]

Прозевал сообщение...

ilghiz в сообщении #1549935 писал(а):

Скажите, пожалуйста, что может дать центровка данных, если мы исходный вектор до Фурье сдвинем

Математически - действительно ничего, но численные ошибки будут при прочих равных немного меньше.

[ilghiz]

Спасибо большое, Pphantom за ответ!

Да, численно конечно это может что-то улучшить, но у меня двойная точность и Фурье от 512 точек, то есть тут ну максимум два последних бита в мантиссе.

2 novichok2018. Спасибо большое за заботу! Теоретически мне это очень интересно. Правда в практику - не сильно верю. То есть если Вам вдруг это совсем-совсем не внапряг, пришлите, пожалуйста, обещаю почитать, но есть большие сомнения, что мне это поможет.

[novichok2018]

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

[Евгений Машеров]

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

[ilghiz]

Спасибо большое, Евгений Машеров, что советуете!

Евгений Машеров в сообщении #1549990 писал(а):

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

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

Пусть у нас имеется вектор $a \in {\call C}^N$, к которому мы применяем Фурье преобразование, а именно $F a$, где $F = \{f_{jk}\} \in {\call C}^{N \times N}, ~ f_{jk}=\exp (i 2 \pi j k / N)$.

Центрирование на $l$ позиций - это умножение на матрицу перестановок $P_l \in {\call C}^{N \times N}$, в виде циркулянта, у которого только одна $l$-тая диагональ содержит единицы и все остальное равно нулю. Тогда

$$F P_l a = F F^* {\rm diag}(F e_l) F a = {\rm diag}(f_l) Fa,$$

фактически переставляя (центрируя) исходный вектор мы только домножаем результат $Fa$ на диагональную матрицу ${\rm diag}(f_l)$, причем каждый диагональный элемент этой матрицы по норме равен единице. То есть кроме призрачной надежды увеличить численную устойчивость ФФТ (которое и так очень стабильно!!!) я не вижу, и, предполагаю, что Вы под центрированием, что-то другое имели ввиду.

Скажите, пожалуйста, а что Вы имели ввиду под центрированием?

Спасибо!