Сложение сигналов в самый "узкий", Как найти весовые коэффициенты для сложения? Опции

[getch]

Приветствую всех!

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

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

Ребята, если кто сталкивался с подобным или знает, где копать-читать, подскажите!

[getch]

Столкнулся с необъяснимой ситуацией. Исходных векторов всего два (длина 288). Вот так они выглядят и решение задачи:

Посмотрите, какое решение получилось. Вектор (0; 1)! Разве может такое быть?! Ведь теоретически такое возможно, только когда дисперсия одного из исходных векторов равна нулю.
Брал сотни тысяч случайных альтернативных векторов. Все они показывали NewVector с более высокой дисперсией.
Но все же не объяснить, как такое возможно?!
На всякий случай прилагаю файл с исходными векторами: Analyse.rar

Сообщение отредактировал getch - Sep 30 2010, 08:08

[Oldring]

Посмотрите, какое решение получилось. Вектор (0; 1)! Разве может такое быть?! Ведь теоретически такое возможно, только когда дисперсия одного из исходных векторов равна нулю.

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

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

[getch]

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

Посмотрел корреляцию этих исходных векторов. Действительно, почти нулевая.
Похоже, я не понимаю особенность условия суммы квадратов членов вектора-решения равная единице.
А если бы было условие, сумма абсолютных значений членов вектора-решения равна единице, то сам метод нахождения такого решения был бы совсем непростым? Такая задача не "обсосана"?
В таком случае для векторов выше было бы решение (0.16; 0.84).
Про корреляция что-то не понимаю. Определение ее знаю. Но ее часто используют для определения взаимосвязей. Нулевая корреляция - отсутствие взаимосвязи. Но как же так, если есть (0.16; 0.84)? Значит взаимосвязь имеется и нехилая - дисперсия NewVector значительно меньше дисперсий исходных векторов.

Сообщение отредактировал getch - Sep 30 2010, 08:26

[Oldring]

А если бы было условие, сумма абсолютных значений членов вектора-решения равна единице, то сам метод нахождения такого решения был бы совсем непростым? Такая задача не "обсосана"?

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

Про корреляция что-то не понимаю. Определение ее знаю. Но ее часто используют для определения взаимосвязей. Нулевая корреляция - отсутствие взаимосвязи. Но как же так, если есть (0.16; 0.84)? Значит взаимосвязь имеется и нехилая - дисперсия NewVector значительно меньше дисперсий исходных векторов.

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

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

[getch]

Тогда случай сложнее. Мы приходим почти что к общей задаче квадратичного программирования с линейными ограничениями. Так как ограничение оказывается лишь кусочно-дифференцируемой замкнутой гиперповерхностью размерности n-1, минимум может оказаться на особенности ограничения меньшей размерности, и поэтому, чтобы его найти, нужно перебирать вершины, ребра разной размерности и грани. Задача гораздо более трудоёмкая.

Симплекс-метод сюда подойдет?

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

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

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

Под взаимосвязью имел в виду линейную взаимосвязь. Посмотрел книги по мат. статистике. Там утверждается, что при нулевой корреляции линейная взаимосвязь отсутствует. Но на приведенных графиках она явно есть. Да и вектор (0.16; 0.84) тому подтверждение. Вообще, на конечной выборке любых случайных величин линейная взаимосвязь всегда есть.

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

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

Тут еще встает вопрос об эффективной оценке метода. Минимальная дисперсия - это метод МНК. И он дает отвратительные показания, если в исходных векторах имеются редкие, но большие выбросы.
Немного посмотрел в сторону квантильного метода (квантильная регрессия)

Нет, оптимальное решение пропорционально вектору <2, -1> и даёт нулевую дисперсию.
Тот упрощенный алгоритм не работает в случае выраждения корреляционной матрицы. У вас не должна обратиться корреляционная матрица прежде всего.

Да, вы правы: пропорционально <2, -1>.

Сообщение отредактировал getch - Sep 30 2010, 09:58

[Oldring]

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

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

Под взаимосвязью имел в виду линейную взаимосвязь. Посмотрел книги по мат. статистике. Там утверждается, что при нулевой корреляции линейная взаимосвязь отсутствует. Но на приведенных графиках она явно есть. Да и вектор (0.16; 0.84) тому подтверждение. Вообще, на конечной выборке любых случайных величин линейная взаимосвязь всегда есть.

Она кажущаяся. Ещё раз: добро пожаловать в реальный мир.

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

Под граблями я имел в виду зависимость результата от ограничения.
Вы, видимо, не понимаете. Поверхности равного значения положительно определенной квадратичной формы есть гиперэллипсоиды. Вложенные друг в друга для различных значений квадратичной формы. Такая вот многослойная "конкреция". Без ограничений на аргумент минимум строго в нуле. Единственное непрерывное ограничение есть гиперповерхность размерности n-1, на которой рассматривается значение этой квадратичной формы. Разные ограничения дают разные гиперповерхности и, соответственно, различные минимумы, как по величине квадратичной формы, так и по аргументу. Соответственно, различная сложность их нахождения, более того, в общем случае даже не гарантируется единственность локального минимума и простота получаемого минимизируемого функционала, если переходить к локальным координатам на этой гиперповерхности. Какой нужен вам - решать вам и только вам.

[getch]

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

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

Она кажущаяся. Ещё раз: добро пожаловать в реальный мир.

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

Под граблями я имел в виду зависимость результата от ограничения.
Вы, видимо, не понимаете. Поверхности равного значения положительно определенной квадратичной формы есть гиперэллипсоиды. Вложенные друг в друга для различных значений квадратичной формы. Такая вот многослойная "конкреция". Без ограничений на аргумент минимум строго в нуле. Единственное непрерывное ограничение есть гиперповерхность размерности n-1, на которой рассматривается значение этой квадратичной формы. Разные ограничения дают разные гиперповерхности и, соответственно, различные минимумы, как по величине квадратичной формы, так и по аргументу. Соответственно, различная сложность их нахождения, более того, в общем случае даже не гарантируется единственность локального минимума и простота получаемого минимизируемого функционала, если переходить к локальным координатам на этой гиперповерхности.

Просто расстоптали... понял 0.001%.

Какой нужен вам - решать вам и только вам.

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

Сообщение отредактировал getch - Sep 30 2010, 10:49

[Oldring]

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

Открою вам страшный секрет. Если последовательности ортогональны, то никакой "линейной взаимосвязи" у них нет по определению.
Например: <1, -1, 1, -1> и <1, 1, -1, -1>

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

[getch]

Открою вам страшный секрет. Если последовательности ортогональны, то никакой "линейной взаимосвязи" у них нет по определению.
Например: <1, -1, 1, -1> и <1, 1, -1, -1>

Ух, я упрямый:
МО = 0, дисперсия = 1 у вышеприведенных векторов.
Для условия суммы абсолютных значений членов оптимального вектора будет: <0.5, 0.5> - дисперсия NewVector = 0.5
Для условия суммы квадратов значений членов оптимального вектора решение будет: <-0.667, 0.745> - дисперсия NewVector = 1.

Первое решение с дисперсией 0.5 показывает нам, что линейная взаимосвязь исходных векторов имеется. Т.к. дисперсия NewVector меньше дисперсий исходных векторов.
А вот второе решение - это как раз ущербная интерпретация нелувой корреляции (у этих векторов): отсутствие линейной взаимосвязи. Поэтому дисперсия NewVector равна минимальной дисперсии исходных векторов.

Сообщение отредактировал getch - Sep 30 2010, 11:15

[Oldring]

Ух, я упрямый:
...
Первое решение с дисперсией 0.5 показывает нам, что линейная взаимосвязь исходных векторов имеется. Т.к. дисперсия NewVector меньше дисперсий исходных векторов.

Чересчур.

А теперь посмотрите на исходные последовательности внимательно. Они симметричны. Если есть "линейная связь", она не может не зависеть от знаков последовательностей, при изменении знака одной последовательностью она должна изменяться на противоположную. А у вас на самом деле дисперсию 0.5 дают любые вектора весов с коэффициентами +-0.5, и минимум тут связан исключительно со свойствами вашего ограничения - так как в таких точках минимизируется квадратичная норма самого весового вектора.

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

[getch]

А теперь посмотрите на исходные последовательности внимательно. Они симметричны. Если есть "линейная связь", она не может не зависеть от знаков последовательностей, при изменении знака одной последовательностью она должна изменяться на противоположную. А у вас на самом деле дисперсию 0.5 дают любые вектора весов с коэффициентами +-0.5, и минимум тут связан исключительно со свойствами вашего ограничения - так как в таких точках минимизируется квадратичная норма самого весового вектора.

У приведенных вами двух векторов 2^2 = 4 решения с одинаковым исходом (дисперсия 0.5).
Если мы у одного исходного вектора поменяем знак, то будет тоже таких 4 решения.
Только не надо здесь видеть противоречий с условием независимости линейной связи от знаков последовательностей. И вот почему:
В первом случае (знаки не меняли) мы берем одно решение из 4-х. И от него уже пляшем.
Для второго условия мы возьмем тоже решение, что и у второго.
О присутствии линейной связи нам говорит диперсия (0.5), меньшая дисперсий исходных векторов.

[Oldring]

Только не надо здесь видеть противоречий с условием независимости линейной связи от знаков последовательностей.

Позвольте всё же мне остаться при своём мнении, что неформализованное вами понятие "линейная связь" тем не менее не может быть нечуствительной к знакам аргументов. Если она, конечно, "линейная". Из этого следует, что обнаруженная вами "связь" есть что угодно, кроме "линейной связи".

[getch]

Позвольте всё же мне остаться при своём мнении, что неформализованное вами понятие "линейная связь" тем не менее не может быть нечуствительной к знакам аргументов. Если она, конечно, "линейная". Из этого следует, что обнаруженная вами "связь" есть что угодно, кроме "линейной связи".

Я беру и в том и в другом случае одно решение <0.5, 0.5>. И это и есть упомянутая вами независимость.
Спорить, конечно же, не будем. Да и ни к чему это. Благодарен вам, за подробные разъяснения и подсказки.
Буду решать задачу квадратичного программирования численным методом. Жаль, что нет столь же быстрого аналитического решения, как был предложен вами для случая суммы квадратов.

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

[Oldring]

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

Я даже не могу представить, как это эффективно решать, тем более, в многомерном случае.

[Oldring]

Впрочем, как искать эффективно то, что вы хотите, в случае двух последовательностей, понятно.

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

Во-вторых, рассмотрим отрезок x+y=1. Отсюда y=1-x, при этом x изменяется от 0 до 1.
Вклад каждого отсчета последовательностей для x, изменяющегося от 0 до 1, есть кусочно-линейная функция с максимум одним изломом в середине. Проходим по всем отсчетам и вычисляем параметры суммарной линейной функции при x=0 и, возможно, положение излома и скачок параметров линейной функции в этой точке излома.

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

Всё. Пройдя по 4-м отрезкам ограничения вычисляем положение глобального минимума.

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

[getch]

Впрочем, как искать эффективно то, что вы хотите, в случае двух последовательностей, понятно.

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

Для вектора длины N понадобится найти 2^N решений задач c простым условием нормировки: сумма членов равна единице. Потом выбрать наименьший. Конечно, 2^N это очень ресурсоемко, но это полностью аналитическое решение.

[Oldring]

Для вектора длины N понадобится найти 2^N решений

Удачи!