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

[getch]

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

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

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

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

[Oldring]

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

Про метод наименьших квадратов что-нибудь слышали? Так тут почти что он.
Всё решается исключительно методами линейной алгебры.

[getch]

Про метод наименьших квадратов что-нибудь слышали? Так тут почти что он.
Всё решается исключительно методами линейной алгебры.

Прочел в википедии про метод. Не пойму, как он может помочь? Ведь нам неизвестно минимальное значение дисперсии.

[Oldring]

Прочел в википедии про метод. Не пойму, как он может помочь? Ведь нам неизвестно минимальное значение дисперсии.

Так прочтите еще раз. Можно не только в Википедии. Разберитесь с его выводом.

[getch]

Так прочтите еще раз. Можно не только в Википедии. Разберитесь с его выводом.

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

[Oldring]

На всякий случай, чтобы не было недопониманий, прилагаю более математическое описание задачи:

Что-ж, учиться студентам никогда не поздно.
Рекомендую: http://ocw.mit.edu/courses/mathematics/18-...video-lectures/

[getch]

Что-ж, учиться студентам никогда не поздно.
Рекомендую: http://ocw.mit.edu/courses/mathematics/18-...video-lectures/

Давно уже не студент... Решаю задачу для своих нужд.
Очень доступно о методе написано здесь: http://multitest.semico.ru/mnk.htm
Попробую обобщить на функцию многих переменных.

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

[Oldring]

Очень доступно о методе написано здесь: http://multitest.semico.ru/mnk.htm
Попробую обобщить на функцию многих переменных.

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

[getch]

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

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

[Oldring]

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

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

Про алгебраическую запись не понял.

В матричном виде. В случае N векторов проще решать задачу сразу в матричном виде.

[getch]

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

Пока этого не чувствую. Посмотрю по-ходу.

В матричном виде. В случае N векторов проще решать задачу сразу в матричном виде.

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

P.S. Одно дело, когда изучаешь и не знаешь, для чего. И совсем другое, когда знаешь.

[Oldring]

Пока этого не чувствую. Посмотрю по-ходу.

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

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

Ну какую-нибудь "линейную алгебру для чайников".
Шучу.
Видеокурс MIT по линейной алгебре очень не плох.
Лекция №16 так прямо посвящена решению задачи наименьших квадратов.

[getch]

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

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

Ну какую-нибудь "линейную алгебру для чайников".
Шучу.
Видеокурс MIT по линейной алгебре очень не плох.
Лекция №16 так прямо посвящена решению задачи наименьших квадратов.

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

[Oldring]

Если не первый будет выделен, а второй или третий, то соотношения между коэффициентами в решениях не поменяются. Так что все в порядке.

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

[getch]

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

Все вектора на входе не нулевые. Все же речь идет о снятых показаниях сигналов. Не совсем уж теоретическое применение.

[Oldring]

Все вектора на входе не нулевые. Все же речь идет о снятых показаниях сигналов. Не совсем уж теоретическое применение.

Ну какой упертый
Ну хорошо, вот вам парочка ненулевых векторов, для "прочувствования" минимизации при разных ограничениях.
<1,0,0> и <0,1,0>. Система получается невырожденная.
И только не говорите мне теперь, что хоть вектора коэффициентов и не пропорциональны, но минимум получается одинаковый. Если так думаете - умножьте в условии второй вектор на 2.

Для такой задачи естественно нормировать вектор коэффициентов так, чтобы Σx_i=1

Мне кажется, скорее всего, там совершенно естественно нормировать среднее значение результата на 1.

С частными производными совсем запарно. Несколько листов A4 исписал. За всем не уследить. Наверное, аналитическое решение в данном случае не оправдано из-за своей огромной ресурсоемкости. Хотя, возможно там можно все упростить... Но может численные методы будут попроще. У меня не получается применить МНК. Метод слабо понял. Прошу, подскажите, как действовать? В математике сам далеко не "айс".

Вы просто не умеете их готовить

[getch]

Ну какой упертый
Ну хорошо, вот вам парочка ненулевых векторов, для "прочувствования" минимизации при разных ограничениях.
<1,0,0> и <0,1,0>. Система получается невырожденная.
И только не говорите мне теперь, что хоть вектора коэффициентов и не пропорциональны, но минимум получается одинаковый. Если так думаете - умножьте в условии второй вектор на 2.

Действительно, упертый!

Мне кажется, скорее всего, там совершенно естественно нормировать среднее значение результата на 1.

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

Пусть А - это матрица, состоящая из столбцов - исходных векторов, а x - вектор неизвестных коэффициентов.
Нужно минимизировать квадратичную норму вектора I-A*x, где I - это вектор-столбец, состоящий из единиц. Решение этой задачи хорошо известно, выводить здесь не буду, хоть оно тривиально выводится аналитически дифференцированием дисперсии по x: x=inv(A'*A)*A'*I, что эквивалентно решению системы линейных уравнений (A'*A)*x=A'*I. Единственная тонкость - если матрица A'*A вырождена. Например, в исходных данных два одинаковых столбца. В этом случае линейная система оказывается недоопределенной, имеет бесконечное количество решений, и можно взять любое решение - все решения дают одинаковую дисперсию.

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

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

При нулевом МО входных векторов после дифференцирования получилась удобносчитаемая матрица линейных уравнений.

Получилась матрица из N уравнений, а неизвестных (N - 1). Это нормально?

[Oldring]

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

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

Пусть А - это матрица, состоящая из столбцов - исходных векторов, начиная со второго, y - первый исходный вектор (выделенный), I - вектор-столбец, состоящий из единиц, а x - вектор-столбец неизвестных коэффициентов, начиная со второго коэффициента (первый известен). Задача - минимизировать квадратичную норму вектора y+A*x-m*I, где m - также неизвестное среднее значение результата, которое, как известно, само минимизирует дисперсию результата при остальных фиксированных членах выражения. Пусть B=[I -A], а z=[m; x], тут мы добавляем к -A спереди единичный столбец и добавляем к столбцу неизвестных коэффициентов еще один неизвестный коэффициент - среднее значение результата. Тогда задача сводится к нахождению наилучшего решения переопределенной системы B*z=y, из линейной алгебры хорошо известно, что точное решение в большинстве случаев не существует, а минимизирующее квадратичную норму ошибки решение есть z=pinv(B )*y, то есть z - есть решение возможно недоопределенной системы N линейных уравнений (B'*B )*z=B'*y. Найдя z мы явно получаем x и m как его компоненты.

[getch]

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

Пусть А - это матрица, состоящая из столбцов - исходных векторов, начиная со второго, y - первый исходный вектор (выделенный), I - вектор-столбец, состоящий из единиц, а x - вектор-столбец неизвестных коэффициентов, начиная со второго коэффициента (первый известен). Задача - минимизировать квадратичную норму вектора y+A*x-m*I, где m - также неизвестное среднее значение результата, которое, как известно, само минимизирует дисперсию результата при остальных фиксированных членах выражения. Пусть B=[I -A], а z=[m; x], тут мы добавляем к -A спереди единичный столбец и добавляем к столбцу неизвестных коэффициентов еще один неизвестный коэффициент - среднее значение результата. Тогда задача сводится к нахождению наилучшего решения переопределенной системы B*z=y, из линейной алгебры хорошо известно, что точное решение в большинстве случаев не существует, а минимизирующее квадратичную норму ошибки решение есть z=pinv(B )*y, то есть z - есть решение возможно недоопределенной системы N линейных уравнений (B'*B )*z=B'*y. Найдя z мы явно получаем x и m как его компоненты.

Все, наверное, замечательно. Только я не понимаю.
Поскольку МО входных векторов обнулил, то вот так строю матрицу линейных уравнений:

Здесь Matrix - матрица, где каждый столбец - вектор (размерность M) на входе
LinMatrix - матрица линейных уравнений NxN (искомый вектор тоже размерности N). Вектор для линейной матрицы нулевой (частные производные в нуле). Матрица уравнений получилась такая, что элементы симметрично повторяются относительно диагонали (из левого-верхнего в правый-нижний угол).
В итоге у меня получается N уравнений и N неизвестных. Когда первый коэффициент задаю единицей, то уравнений остается N, а неизвестных уже (N - 1). Решать однозначно такую систему не получается.
Как тут можно действовать? Подумал так:
выкидывать по одному уравнению и решать систему. Итого будет N решений. Потом среди них найти то, где дисперсия в минимуме.
Так правильно?
И как сюда еще добавить условие нормализации, когда и так избыточность уравнений?

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

[Oldring]

Как тут можно действовать?

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

[getch]

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

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

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

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

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

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

P.S. Никак не думал, что решение задачи с такой простой формулировкой (конечно, не гипотеза Ферма), потребует столького.

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

[Oldring]

P.S. Никак не думал, что решение задачи с такой простой формулировкой (конечно, не гипотеза Ферма), потребует столького.

Так и решение задачи на самом деле очень простое.

Это как бы не сама линейная алгебра, а её вычислительные аспекты

Не соглашусь. Псевдоинверсии непосредственно связаны со структурой небиективных линейных отображений. Без понимания их структуры полноценного понимания линейной алгебры быть не может.