Посмотрите на неё с большим разрешением в районе минимума.
Там, действительно, достаточно искать нуль производной, так как все модули выпуклы вверх. Точнее, вниз. Точнее, не принципиально, но в одну сторону.

Про производные не понял. Бывает и так:

Искать точку (не ясно как), где производная равна нулю. И эта точка будет искомой, если попадает в отрезок [-1; 1]. Если же точка < -1, то искомая = -1. Если > 1, то искомая = 1.

Как ищут минимум непрерывно дифференцируемой функции? У вас она кусочно непрерывно дефференцируемая.
Верхний график у вас вводит в заблеждуние. Наклон линий только возрастает. Увеличте ещё.

Про необходимость поиска нулевой производной написал выше. А вот как ее численно искать пока не знаю.


Вот так выглядит график и его производная в на всем отрезке [0; 1] и вблизи минимума:

А так меняется производная при уменьшении Delta:

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

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

Считать меньше. Дифференцировать целевую функцию, разумеется, нужно аналитически, а не численно. Это просто.

Конечно, производные N+2 линейных функций простые. Но как посчитать производную целевой функции?

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

Для интервала слева - до первого излома, производная будет Sum(a[i]-b[i])

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

Примем, что производная слева равна D[0].
тогда производная после 1-го излома (слагаемые отсортировали по возрастанию точек излома) будет D[1] = D[0] + 2 * (b[1] - a[1]).
Ну и вообще итерационная формула такая D[k] = D[k - 1] + 2 * (b[k] - a[k]).
В итоге получается, что надо сначала отсортировать слагаемые по возрастанию точек изломов, а потом итерационно дойти до производной, которая меняет знак. После чего взять точку, которая соответствуюет минимальному значению модуля двух соседних D.
P.S. Возрастание производной совсем неочевидно.

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




Нет!
Нужно юбрать излом, при переходе через который производная меняет знак.

Ошибки нет, если считать, что производная убывает.



Туплю - не понял.

Есть.



Сорри, читать "нужно брать".

Если у нас N отсортированных по возрастанию изломов слагаемых, то
D[0] = Sum(b[i] - a[i])
D[k] = D[k-1] + 2 * (a[k] - b[k]), k = 0..N
D[N+1] = Sum(a[i] - b[i])


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

Задумайтесь о смысле разности b[i] - a[i].



Думайте.

На всякий случай напишу целевую функцию: Sum(|a[i] * x + b[i] * (1 - x)|) = Sum((|(a[i] - b[i]) * x + b[i]|).
b[i] - a[i] - это изменение угла наклона.

Нулевой производной может и не существовать. Поэтому нам нужна производная, как можно ближе к нулю. Т.е. если D[M] * D[M + 1] < 0, то искомый излом будет соответствовать min(|D[M]|, |D[M + 1]|)

А теперь продифференцируйте модуль.



Но всегда существует излом, при переходе которой производная меняет знак. Он и есть минимум.

D(x) = b[i] - a[i], x < b[i] / (b[i] - a[i])
D(x) = Unknown, x = b[i] / (b[i] - a[i])
D(x) = a[i] - b[i], x > b[i] / (b[i] - a[i])

Так такой излом и слева и справа от нуля!

P.S. Unknown можно считать нулем.

А если a[i] < b[i]?




От какого ещё нуля?

D[0] = -Sum(|b[i] - a[i]|)
D[k] = D[k-1] + 2 * |a[k] - b[k]|, k = 0..N
D[N+1] = Sum(|b[i] - a[i]|)


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

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

Допустим, что мы пронумеровали изломы слева направо 1, 2, 3, ...., N
И для них получили такие значения производной:
D[100] = -1
D[101] = -0.25
D[102] = 0.5
D[103] = 1

Какой излом брать, 101 или 102?

Заметил у себя ошибку, проивзодных будет не N+2, а 2 * N + 2:
D[0] = -Sum(|b[i] - a[i]|)
D[k] = D[k-1] + |a[k/2] - b[k/2]|, k = 0..2 * N
D[2 * N+1] = Sum(|b[i] - a[i]|)

102




Мы уже добрались до полуцелых индексов массивов?

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

Спасибо огромное за разъяснения!

Наглею, но спрошу, может, сталкивались с такой задачей:

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

Да потому что у вас в массиве вершин к вершине приписана производная справа от неё

Написал нахождение минимума:



С какой это стати "бесконечно"? Они все пропорциональны друг другу. Если ковариационная матрица невырождена, то решение, написанное ранее, дает ровно один вектор.

Ну я и ступил... Точно!

Похоже, вы правы. Меня ввел в заблуждение такой результат (на знаки корреляции не обратил внимание):

P.S. Допустим мы имеем всего два вектора длинной единица в трехмерном пространстве. Тогда вектора, которые одинаково коррелированы с исходными двумя, разве не образуют окружность?

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

Я что-то запутался. Правильно ли я понимаю:
1. Количество непропорциональных векторов с одинаковой корреляцией к исходным бесконечно.
2. С одинаковой корреляцией и максимально-возможной - один.
3. К какому пункту относится вектор, находящийся, как обратная ковариационная матрица уноженная на единичную?

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

А непропорциональных векторов не бесконечно разве. Все та же окружность - это же непропорциональные вектора.


Т.е. вышеприведенное решение дает вектор с максимальной корреляцией к исходным?

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

Да, с равной максимальной, если такой существует.



Нет, это ковариация не изменяется, а в корреляции в знаменателе стоит длина вектора, и длина возрастает.
Максимальный вектор единственный с точностью до положительной константы.

Путаюсь. Если исходные вектора имеют единичную длину, то вектор с максимальной корреляцией к исходным и длиной единица единстенный?
Третий вектор на картине здесь - это тот самый единственный максимально-коррелированный вектор?
Вот так нахожу:

Не знаю, я его не вычислял.

Провел сравнение решений двух задач:

Знал, что различия будут, но что такие - не ожидал.
Складывая два сигнала в один с минимальной средне-КВАДРАТИЧНОЙ ошибкой (задача2) и минимальной средне-АБСОЛЮТНОЙ ошибкой (задача1), получил сигналы, которые вообще не похожи друг на друга.
Посмотрите весовые коэффициенты, они даже знаками различаются.
Также обратите внимание, что для получения сигнала с минимальной средне-КВАДРАТИЧНОЙ ошибкой мы всегда имеем равные абсолютные значения весовых коэффициентов (= 0.5).

Решил посмотреть, как выглядят коэффициенты для задач, где надо минимизировать средне-КУБИЧЕСКУЮ ошибку, средне-БИКВАДРАТНУЮ ошибку и т.д. Даже нецелые степени. Функции, которые решали задачи выше, работают мгновенно. Здесь же пришлось решать тупым перебором, но на качестве результата это не сказалось.

Так зависят весовые коэффициенты все на тех же исходных векторах, что выше приводились:

Интересная зависимость. Видно, что для степеней <= 1 изменение "нестандартное".

Теперь опустим условие, что СКО все тех же исходных векторов равно единице:

"Пересечение" весовых коэффициентов сдвинулось со степени 2 до ~18.

Я выбрал нечасто-попадающие исходные вектора. В 99% случаев картина такая:

Т.е. плавное изменение весовых коэффициентов при смене степени ошибки.

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


Я хотел сложить сигналы в самый "узкий". Узость определялась условием ошибки. Оказалось, что для ошибки со степенью <= 1 суммарный сигнал может сильно отличаться от тех, что со степенью ошибки > 1.

Возможно ли обобщить метод с дифференцированием, когда минимизировалось средне-АБСОЛЮТНОЕ отклонение, с двухмерного случая на многомерный?

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



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

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

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

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

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


Текущее решение имеет сложность 2^N: