Моя задача с нормировкой легко сводится к задаче с выделенным одним коэффициентом в качестве единицы.
А решение моей задачи через SVD видится гораздо более ресурсоемким.

Нет. Опять те же грабли.

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

Почему-то понять не могу:
моя задача имеет решение V1 * X1[i] + V2 * X2[i] + ... + Vn * Xn[i] = D[i] - мин. дисперсия.
Значит это решение регрессии: X1[i] = D[i] / V1 - X2[i] * V2 / V1 - ... - Xn[i] * Vn / V1.

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

Это не регрессия.
Вы опять путаете различные условные минимумы.

Но как же так, ведь регрессия формулируется так:
X1[i] = V2 * X2[i] + ... + Vn * Xn[i] + E[i], где E[i] имеет мин. дисперсию. Здесь E[i] = D[i] / V1


Приведите, пожалуйста, простой невырожденный контрпример.

Вы не знаете D[i].
Контрпример вы уже сами когда-то приводили. Пока не начнете видеть решение своей задачи - всё равно бестолку. Думайте.

Спасибо, задачу решил. Решение оказалось значительно проще:

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

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

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

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

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

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

Ссылка на этот пост. Выдержка из него:

И не забудьте заглянуть на два поста выше.

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

Не знаю, подумаю потом.

Поторопился, решение неправильное.

Пока решение такое (правильное, но медленное):
1. Сначала решается задача для условия, что сумма коэффициентов (не их модулей) равна единице.
1.1 Составляется ковариационная матрица из столбцов исходной.
1.2. Берется обратная.
1.3. i-й искомый весовой коэффициент равен сумме элементов i-го столбца обратной матрицы, деленной на сумму всех элементов обратной матрицы.
1.4. Дисперсия, которую мы минимизировали, равна единице, деленной на сумму всех элементов обратной матрицы.

2. Используем решение выше для решения задачи, где сумма МОДУЛЕЙ коэффициентов равна единице.
2.1 "Перебираем" (есть свои оптимизации, но все равно не особо быстро) все варианты. Если коэффициентов N, то количество вариантов 2^N. Таким образом находим решение. Для N = 10 - работает быстро. А вот для больших N - плохо.

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

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

Вы, видимо, ветку не читали.
1. Уважаемый Oldring, привел очень быстрое и простое решение для случая, когда сумма КВАДРАТОВ весовых коэффициентов равна единице.
2. Постом выше написано, как решается задача, когда сумма коэффициентов равна единице.
3. И там же, как можно решить задачу (медленно, но работает), когда сумма МОДУЛЕЙ весовых коэффициентов равна единице.
4. Также в ходе обсуждения ставилась задача уменьшения не средне-квадратичной ошибки (дисперсии), а средне-абсолютной ошибки. Видение решения такой задачи уважаемый Oldring привел для двухмерного случая.

Очень интересное свойство у решения, точнее у получившегося сложенного сигнала (NewVector):
1. ковариации NewVector c любым исходным сигналом равны. При этом обязательность условия "АБСОЛЮТНЫХ" не нужна.
2. Если дисперсии исходных сигналов равны, то из п.1 следует, что коэффициент корреляции NewVector c любым исходным сигналом совпадает.
P.S. Интересно, как сложить сигналы, чтобы получившийся сигнал имел одинаковый коэффициент корреляции с исходными, даже если дисперссии исходных сигналов неравны...

Ну например так.

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

Уравнение: A*v=I, где I - единичный вектор-столбец высотой, равной числу векторов. Тогда v=inv(A)*I - сумма столбцов обратной от ковариационной матрицы отнормированных векторов.

Так это решение я написал выше. И оно делает одинаковые ковариации, но не корреляции на случай несовпадающих исходных дисперсий.
P.S. Не пойму, почему при минимизации дисперсии суммы двух векторов с одинаковой дисперсией весовые коэффициенты всегда равны?
P.P.S. Интересное наблюдение, для двух сигналов с КК = 0 существует сигнал, который имеет одинаковый КК к исходным, и КК далеко не нулевой (у себя на примере получил > 0.7)

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



Потому что cos(90/2)=0.707...

Под вечер, наверное, туплю. Как учесть нормировку в векторе полученных коэффициентов?


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

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

Ага, спасибо! Я точно ступил.

Не всегда, но возможно вам подскажет, что у симметричной матрицы 2х2 с одинаковыми элементами на главной диагонали собственные вектора всегда [1, 1] и [1, -1]. Когда их два.

Спрошу еще, мне непонятен сей момент:

Как такое может быть в данном случае, чтобы средне-квадратичная ошибка была меньше у NewV1 (в сравнении с NewV2), а средне-абсолютная - больше?
Ведь по графикам видно, что и NewV1 и NewV2 находятся в диапозоне (-1; 1).

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

Элементы векторов NewV1 и NewV2 находятся в диапазоне (-1;1).
Раз сумма квадратов элементов NewV1 < суммы квадратов элементов NewV2, то отсюда же должно следовать, что и сумма модулей элементов NewV1 < суммы модулей элементов NewV2. А на картинке это не так.
Я бы понял, если бы элементы NewV1 и NewV2 вылезали за диапазон [-1;1], но они все внутри.
P.S. Представьте, что я ничего не говорил про V1 и V2. А сразу показал NewV1 и NewV2.

Не должно. Рассмотрите, ну, например... Бином Ньютона.

Прошу, поясните свое решение для минимизации средне-абсолютной ошибки:

Даже для двухмерного случая не понял (выделил).

Вспомните как выглядит график функции модуля.

Про то, что это "галочка"с минимумом в нуле - ясно. Я, видимо, какую-то очевидность в ваших рассуждениях не могу уловить.

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

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

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

Для двухмерного случая надо минимизировать: Sum(|x * a[i] + y * b[i]|).
Рассматриваем только один из четырех случаев: x + y = 1.
Для каждого члена суммы излом будет только в одной точке: x = b[i] / (b[i] - a[i]).
Про вычитание/сложение половинок слева/справа от излома не понял.
P.S. Если минимум находится в одном из изломов, то достаточно же пробежаться по всем изломам и найти минимум: посчитать сумму для каждой точки излома и выбрать минимальную.

Слева от вершины вклад от некоторого модуля в сумму будет, например, , а справа -

Ух, так и не понял про половинки. Зачем они? И почему некорректно пробежаться по точками излома и точкам слева-справа?

Можно и в лоб. Но на длинах в несколько десятков тысяч точек будет уже долго.

Извините, я не понял Ваш вариант решения. Он разве не в лоб?
Я не дошел до понимания вашего решения.

Он NlogN, а в лоб - это квадрат. Вы как собираетесь находить величину функции в каждом изломе?

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

Пошагово - сортируете, потом выкидываете все точки вне отрезка [0,1], сворачивая их вклад в суммы линейных функций, потом оставшиеся точки сортируете по координате вершины, потом проходите слева направо по всем точкам плюс края отрезка, сравниваете их высоту, но только высоту считаете не суммируя по всему массиву вклад всех точек для данной координаты, а переходя от предыдущей точки к следующей, изменяя вклад перескакиваемой точки и обновляя вклад всех остальных скопом.

Для векторов {a1, a2, a2} и {b1, b2, b3} можете показать? Возможно, у меня незнание терминологии. Потому как "сворачивать" - не понимаю. Изменять вклад перескакиваемой точки - это как?

Мне вам код написать? С сортировкой?
Представьте что вы оказались слева от двух вершин модулей. Как выглядит график суммы модулей в вашей окрестности? Это линейная функция, иначе говоря, прямая. Как можно описать эту прямую? Уравнением y=a*x+b, причем, параметры a и b равны суммам параметров от слагаемых модулей в окрестности рассматриваемой точки.
Пусть вы прибавили график ещё одного модуля, но вы всё ещё слева от всех их изломов. Что изменится? Уравнение останется то же, но к её значению в нуле и наклону прибавятся значение в нуле и наклон от третьего слагаемого. И так далее.
Теперь предположим, что вы по этой прямой, двигаясь вправо, дошли до самой левой вершины и хотите её обойти. Что будет в промежутке между первой и второй вершиной? Тоже прямая. Какие будут её параметры? Её параметры будут почти такие же, как и слева от рассматриваемой вершины, изменится в сумме только вклад от модуля, которому принадлежит эта вершина. Это изменение можно учесть и идти дальше.

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

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

В итоге, если слагаемых N, то имеем N+2 линейные функции. Что нам это дает?

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



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

Да, это понял, так получим N+2 линейные функции.

Прошу, поясните эту цитату.
Вот так выглядит функция, минимум которой ищется: