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

[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]

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

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

[SSerge]

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

[getch]

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

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

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

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

С частными производными совсем запарно. Несколько листов A4 исписал.

Удалось значительно упростить систему линейных уравнений, когда мат. ожидания векторов на входе сделал нулевым. (Тогда МО сгенерированного вектора NewVector тоже стало нулевым)

[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]

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

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

[fontp]

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

На эту тему есть классная книга (на английском)
Regression and the Moore-Penrose Pseudoinverse

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

[Oldring]

На эту тему есть классная книга (на английском)
Regression and the Moore-Penrose Pseudoinverse

"И вышел опять на Дерибасовскую".
Дурацкое файлохранилище.

[fontp]

Дурацкое файлохранилище.

Что попалось, я нагуглил, а не выкладывал.
Это классическая книга 1972 года

И вообще это не Вам, а всем тем у кого уравнений слишком много или слишком мало

[Oldring]

И вообще это не Вам

Думаете, только я пользуюсь IE?

[getch]

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

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

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

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

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

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

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

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

[Oldring]

К сожалению, ваше решение, написанное в формате форума, крайне сложно уловить мне, как собирающемуся все же пройти курс линейной алгебры самостоятельно.

Так что там непонятно?
А - матрица размером Mx(N-1)
B - матрица размером MxN
y - вектор-столбец размером Mx1
x - вектор-столбец размером (N-1)x1
m - скаляр
I - вектор-столбец размером Mx1, заполненный единицами
z - вектор-столбец размером Nx1
Штрих обозначает транспонирование. Звездочка - матричное умножение. Линейное уравнение записано в стандартном матричном виде.

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

[fontp]

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

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

[Oldring]

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

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

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

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

[fontp]

Не соглашусь.

Понятное дело, Вы ж несогласный. Ни в чём не уступите Фишеру
"Книга призвана заполнить пробел, который существует между общим курсом линейной алгебры и приложениями этой дисциплины к научным и техническим задачам..."
http://www.polytech.poltava.ua/lib/resurs/...beklemishev.pdf

[Oldring]

Понятное дело, Вы ж несогласный. Ни в чём не уступите Фишеру

"Оффтопик временно закрыт по технически причинам"
Мне тоже есть что вам сказать. Подождем?

"Книга призвана заполнить пробел, который существует между общим курсом линейной алгебры и приложениями этой дисциплины к научным и техническим задачам..."
http://www.polytech.poltava.ua/lib/resurs/...beklemishev.pdf

Бек, конечно, молодец, что несмотря на общепринятые в России программы написал и книжку "для продвинутых", но всё же позвольте мне остаться при своём мнении, что курс MIT дает лучшее понимание основ?

[getch]

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

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

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

А за линейную алгебру взялся (без пафоса), потому что задачи впереди потребуют 100% ее применения.

[getch]

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

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

[alex_os]

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

Что-то не то.
Квадратичная форма F(x) = x.' * A *x (А- матрица n на n, x - вектора столбец, .' - транспонирование )
имеет один глобальный экстремум. Если F(x) нарисовать в n- мерном пространстве , то это будет параболоид.

[Sergey'F]

Мне в свое время больше всего понравился Г.Стренг, Линейная алгебра и ее применения. Djvu находится легко.

[getch]

Что-то не то.
Квадратичная форма F(x) = x.' * A *x (А- матрица n на n, x - вектора столбец, .' - транспонирование )
имеет один глобальный экстремум. Если F(x) нарисовать в n- мерном пространстве , то это будет параболоид.

Вроде, должен быть глобальный минимум. Пример решения задачи:


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

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

Нашел причину, обнулял МО столбцов у своей огромной матрицы, но не сохранял результат. Теперь все отлично, минимум находится.
Mathcad-файл, что выше, вычисляет верно любые варианты входных матриц! Похоже, что дисперсия решения (минимум) при любой входной матрице всегда равна нулю.

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

[Oldring]

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

Нет.

[getch]

Нет.

Точно, не всегда нулевая.

[Oldring]

Точно, не всегда нулевая.

Если совсем уж точно, то почти всегда ненулевая.

[getch]

Поскольку расширенная матрица "симметричная", то расчет ее ускоряется в два раза:

[Oldring]

Поскольку расширенная матрица "симметричная", то расчет ее ускоряется в два раза:

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

[getch]

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

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

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

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

[Oldring]

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

Дело не в скорости, а в вычислительной устойчивости. Холецкий очень устойчив, в отличие от Гаусса.

[getch]

Дело не в скорости, а в вычислительной устойчивости. Холецкий очень устойчив, в отличие от Гаусса.

Прошу, приведите пример. Не понял, что подразумевается под устойчивостью.

[Oldring]

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

Там N*(N+1)/2 скалярных произведений векторов. Скалярные произведения обычно считаются на современных процессорах эффективно, без излишних накладных расходов, с использованием MAC или вообще SIMD команд. Но может потребоваться кодирование этой операции на ассемблере.

Прошу, приведите пример. Не понял, что подразумевается под устойчивостью.

http://ru.wikipedia.org/wiki/%D0%92%D1%8B%...%81%D1%82%D1%8C

[getch]

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

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

Видится логичным такая ситуация:
Допустим, мы нашли искомый вектор (Vector), в котором дисперсия вектора (Matrix * Vector) минимальна.
Если мы меняем знак i-го столбца в Matrix, то новое решение было бы тем же вектором Vector, но только у которого i-й элемент тоже поменял знак.
Нормировка вектора единицей не дает такого свойства решению. Может, кто знает, как поставить условие задачи, чтобы его решение обладало свойством, как описал?

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

[Oldring]

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

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

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

[getch]

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

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

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

Есть такая наука - эконометрика. Стал с ней знакомиться и столкнулся с моей точки зрения с псевдо-научными рассуждениями и результатами (там не по делу (мое мнение) применяются довольно продвинутые результаты теорвера и матстатистики) эконометрики, за которые иногда авторы получали даже Нобелевские премии. Хочу разобраться просто, что откуда ведет. Благо огромное количество истории различных экономических показателей имеется. Разрабатываю инструментарий для исследования огромных баз экономических данных. Почему экономика, а не нечто другое? Причина только одна, нигде не накоплено такое большое количество информации. Ну нет измеренных данных изменения численности муравьев в муравейнике (и его роста) и подобных. В экономике есть.
Зачем мне это надо? Чтобы понимать или иметь хотя бы минимальное представление.

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

[Oldring]

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

Потому что минимум будет другим. Выделение первого вектора при этом нарушает симметрию между веаторами.

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

Про эконометрику не скажу ничего, какое там ограничение "естественно". Скорее всего, там много вымысла и приближенности. Сложно ожидать линейности от экономики.

[getch]

Потому что минимум будет другим. Выделение первого вектора при этом нарушает симметрию между веаторами.

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

Допустим, первый коэффициент равен Const1, и мы находим решение Vector1.
Если первый коэффициент равен Const2, находим решение Vector2.
При этом есть замечательное свойство: Vector2 = Vector1 * Const2 / Const1.

Поэтому решаю задачу так:
Первый коэффициент делаю единицей и нахожу решение Vector. Затем домножаю Vector на коэффициент, чтобы сумма квадратов его элементов была единица. Тем самым нахожу однозначное симметричное решение симметричной задачи.

Или я где-то что-то сильно упускаю?

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

[Oldring]

Или я где-то что-то сильно упускаю?

Да. Сделайте константой второй коэффициеинт. Получите в общем случае другой оптимальный вектор. Непропорциональный первому.

[getch]

Да. Сделайте константой второй коэффициеинт. Получите в общем случае другой оптимальный вектор. Непропорциональный первому.

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

Да. Сделайте константой второй коэффициеинт. Получите в общем случае другой оптимальный вектор. Непропорциональный первому.

И все же совершенно не понимаю природу этого.
Делаю так:
Определеляю первый коэффициент единицей, нахожу оптимальный вектор Vector1.
Заново решаю задачу, но уже определяю константой второй коэффициент, равным второму элементу из Vector1. Получаю оптимальный вектор Vector2.
Почему Vector1 не равен Vector2?!
Похоже, понял причину.

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

[getch]

Вроде, это задача квадратичного программирования. Пока смотрю материал на тему седловой точки функции Лагранжа. Загруз еще тот... Определиться бы с направлением.

Напоминаю формулировку задачи:
Найти такой вектор V, чтобы дисперсия вектора (Matrix*V) была минимальна.
При этом сумма КВАДРАТОВ элементов вектора V равна единице.
Мат. ожидание столбцов матрицы Matrix равно нулю.

[Oldring]

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

Нет, не подходит. С квадратичным ограничением задача сразу становится иная. Но также полностью обсосанная. Напишу еще раз, что решение есть собственный вектор, соответствующий минимальному собственному значению корреляционной матрицы. Собственные значения с собственными векторами - это также очень важные понятия из линейной алгебры, для их поиска разработаны свои эффективные и устойчивые алгоритмы, которые по своей природе итеративные, в отличие от решения системы линейных уравнений. В Матлабе их находит функция eig, для матрицы 10х10 она работает мгновенно. Но можете искать минимум квадратичной формы при квадратичном ограничении и явно. Или, например, вот таким способом, работающим для матриц с не слишком большыми числами обусловленностями:

1. Вычислить корреляционную матрицу сигналов: A=V'*V;
2. Найти обратную матрицу: B=inv(A);
3. Несколько раз возвести обратную матрицу в квадрат, не забывая её при этом перенормировать: B=B/max(max(abs(B )));B=B*B;
Скорее всего десятка итераций окажется достаточно, но лучше вычислять какую-либо норму разности между итерациями и итерировать, пока разность остается существенной.
4. Найти столбец x матрицы B с наибольшей суммой квадратов элементов. Перенормировать его на равенство суммы квадратов единице: x=x/sqrt(x'*x). Найденный x и есть искомый столбец коэффициентов, минимизирующий дисперсию.

[getch]

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

Корреляционная матрица составляется, как корреляция между соответствующими столбцами входной матрицы?

Но можете искать минимум квадратичной формы при квадратичном ограничении и явно.

Под явный поиск что имеете в виду?

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

1. Вычислить корреляционную матрицу сигналов: A=V'*V;
2. Найти обратную матрицу: B=inv(A);
3. Несколько раз возвести обратную матрицу в квадрат, не забывая её при этом перенормировать: B=B/max(max(abs(B )));B=B*B;
Скорее всего десятка итераций окажется достаточно, но лучше вычислять какую-либо норму разности между итерациями и итерировать, пока разность остается существенной.
4. Найти столбец x матрицы B с наибольшей суммой квадратов элементов. Перенормировать его на равенство суммы квадратов единице: x=x/sqrt(x'*x). Найденный x и есть искомый столбец коэффициентов, минимизирующий дисперсию.

Что здесь обозначает V и abs? Перенормировка B на каждой итерации?

[Oldring]

Корреляционная матрица составляется, как корреляция между соответствующими столбцами входной матрицы?

Да. Произведение V'*V

Что здесь обозначает V и abs? Перенормировка B на каждой итерации?

Да. abs - абсолютное значение элементов матрицы. Точный вид нормировки не важен.

[getch]

3. Несколько раз возвести обратную матрицу в квадрат, не забывая её при этом перенормировать: B=B/max(max(abs(B )));B=B*B;

Дважды max - это опечатка?

[Oldring]

Дважды max - это опечатка?

Это функции Матлаба.

[getch]

1. Вычислить корреляционную матрицу сигналов: A=V'*V;
2. Найти обратную матрицу: B=inv(A);
3. Несколько раз возвести обратную матрицу в квадрат, не забывая её при этом перенормировать: B=B/max(max(abs(B )));B=B*B;
Скорее всего десятка итераций окажется достаточно, но лучше вычислять какую-либо норму разности между итерациями и итерировать, пока разность остается существенной.
4. Найти столбец x матрицы B с наибольшей суммой квадратов элементов. Перенормировать его на равенство суммы квадратов единице: x=x/sqrt(x'*x). Найденный x и есть искомый столбец коэффициентов, минимизирующий дисперсию.

Воспроизвел, спасибо!. Ресурсоемкость минимальная при таком подходе.
Не знаю, правда, является ли найденный вектор оптимальным.
Если я правильно понял, то описанный вами метод - это общий численный метод нахождения собственного вектора, соответствующего минимальному собственному значению корреляционной матрицы.
Подскажите, где можно почитать на эту тему? Или это все тот же MIT-курс лекций освещает?

3. Несколько раз возвести обратную матрицу в квадрат, не забывая её при этом перенормировать: B=B/max(max(abs(B )));B=B*B;
Скорее всего десятка итераций окажется достаточно, но лучше вычислять какую-либо норму разности между итерациями и итерировать, пока разность остается существенной.

Мне хватает и 5-и итераций (корреляционная матрица 6x6). При такой быстрой сходимости норму разности между итерациями можно использовать простейшую: сумма квадратов элементов.

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

[Oldring]

Подскажите, где можно почитать на эту тему? Или это все тот же MIT-курс лекций освещает?

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

[getch]

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

Но где здесь упоминание итерационного подхода?
Еще не сообразил, почему берется именно корреляционная матрица.
И нужно ли приводить столбцы исходной матрицы к нулевому МО? Такое же преобразование на корреляционную матрицу не должно повлиять?

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

[Oldring]

Но где здесь упоминание итерационного подхода?

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

Еще не сообразил, почему берется именно корреляционная матрица.
И нужно ли приводить столбцы исходной матрицы к нулевому МО? Такое же преобразование на корреляционную матрицу не должно повлиять?

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

[getch]

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

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

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

[Oldring]

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

Нет, ни в коем случае. Именно ковариационная. Именно V'*V.

[getch]

Генерировал десятки тысяч случайных векторов, сумма квадратов которых равна единице. И сравнивал дисперсии с найденной по Вашей методике. Ваш вектор всегда оказывался оптимальным.

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

Честно признаюсь, просил помощи на нескольких форумах мат. направленности, но нигде мне ничего вразуметильного не ответили. Был приятно поражен отзывчивостью форумчан до селе неизвестного мне форума Electronix.
Всем ответившим огромное спасибо, и, конечно, еще раз отдельная благодарность Oldring!

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

[Oldring]

Похвала всегда приятна, спасибо.

[getch]

Для меня понятно одно свойство решения, но раньше мог и ошибаться, поэтому спрашиваю:
При добавлении любого нового столбца в исходную матрицу, дисперсия нового оптимального решения увеличиваться не будет?

[Oldring]

Для меня понятно одно свойство решения, но раньше мог и ошибаться, поэтому спрашиваю:
При добавлении любого нового столбца в исходную матрицу, дисперсия нового оптимального решения увеличиваться не будет?

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

[getch]

И нужно ли приводить столбцы исходной матрицы к нулевому МО? Такое же преобразование на корреляционную матрицу не должно повлиять?

Нужно приводить, иначе будет минимизироваться не дисперсия, а сумма квадратов результата. И матрица V'*V получится совсем не ковариационная.

На ковариационную матрицу МО столбцов никакого влияния не оказывает(т.к. cvar(V1, V2) == cvar(V1 + Scalar1, V2 + Scalar2)). Но решение будет верно с такой ковариационной матрицей только для столбцов с нулевым МО.

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

[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]

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

И при корреляции 1 такое возможно. Пример:
Исходный вектор1: (-1)^k - дисперсия 1, МО = 0.
Исходный вектор2: 2 * (-1)^k - дисперсия 2, МО = 0.
Корреляция 1.
Оптимальный вектор решения (1; 0).

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

[Oldring]

И при корреляции 1 такое возможно. Пример:
Исходный вектор1: (-1)^k - дисперсия 1, МО = 0.
Исходный вектор2: 2 * (-1)^k - дисперсия 2, МО = 0.
Корреляция 1.
Оптимальный вектор решения (1; 0).

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

[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 решений

Удачи!

[getch]

Удачи!

Подкололи!

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

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

[Oldring]

Не зря же дисперсия - это среднеквадратичная ошибка, а не среднеабсолютная ошибка.

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

[getch]

Независимых гауссово распределенных величин У вас, конечно, именно такой случай?

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

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

[Oldring]

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

Ещё и ещё раз. Дисперсия линейной комбинации зависит от нормировки вектора весов. Для одного и того же направления вектора весов дисперсия пропорциональна квадрату его длины. Поэтому говорить про минимизацию дисперсии без учета нормировки вектора весов бессмысленно.

[ivan219]

Извиняюсь за вмешательство.
Но хотелось бы немного для себя разъяснить. Вы тут пытаетесь сделать как можно узкий сигнал, т.е. суммарный размах амплитуды должен быть минимален у сигнала во времени с максимальным числом гармоник в нём???
А что тогда скажете про ЛЧМ???
А то вот при использовании ЛЧМ сигнала с 255 гармониках длинной в 512 семпла и амплитудой каждой гармоники 1 размах, получается, от -17 да 16.29, а если сделать число гармоник больше то и размах увеличивается. А я этот сигнал отправляю в АЦП, а он 16 бит, так что максимальное значение, которое он примет без искажения будет 32768 и не трудно посчитать максимальную амплитуду каждой гармоники. Т.е. при увеличении числа гармоник их амплитуда падает а, следовательно, сигнал / шум на выходе ЦАП уменьшается.

Сообщение отредактировал ivan219 - Oct 1 2010, 23:07

[getch]

Ещё и ещё раз. Дисперсия линейной комбинации зависит от нормировки вектора весов. Для одного и того же направления вектора весов дисперсия пропорциональна квадрату его длины. Поэтому говорить про минимизацию дисперсии без учета нормировки вектора весов бессмысленно.

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

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

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

Сообщение отредактировал getch - Oct 3 2010, 10:07

[Oldring]

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

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

[getch]

Объясните, пожалуйста, чем поставленная задача отличается от многомерной линейной регрессии.
Там задача решается по МНК через сингулярное разложение. Вы же нашли решение, вроде, той же задачи, гораздо более простое.
Что я не понимаю?

[Oldring]

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

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

[getch]

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

[Oldring]

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

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

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