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

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

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

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

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

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

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

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

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

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

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

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

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



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

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

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

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

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



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

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


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

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

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

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

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


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


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

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






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



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

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



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


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

Там на самом деле была у меня ошибка. С минимизацией именно дисперсии результата при фиксированном среднем не всё так просто, приведенное решение не гарантирует равенство единице среднего от результата, а находит решение, минимизирующее сумму квадратов отклонений результата от единиц. Для нормировки среднего результата на единицу нужно сделать пару промежуточных шагов, но я лучше для примера покажу, как решать то, что вы ищете - как делать для выделенного первого вектора с коэффициентом 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 решений. Потом среди них найти то, где дисперсия в минимуме.
Так правильно?
И как сюда еще добавить условие нормализации, когда и так избыточность уравнений?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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



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

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

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




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

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

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

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

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

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

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

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


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


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

Нет.

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

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

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

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

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

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

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

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

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



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

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

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

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

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

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

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

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

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

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