Минимизация суммы абсолютного отклонения ( расстояние

15

У меня есть набор данных и я хочу найти параметр m такой, чтобы он минимизировал сумму k i = 1 | м - х я | , то естьx1,x2,,xkm

i=1k|mxi|.

minmi=1k|mxi|.
mayenew
источник
2
Не могли бы вы уточнить немного?
Джефф Оксберри
В таком случае, не будет ли решение тогда серединой между максимальным и минимальным значениями?
Павел
@Paul медиана может минимизировать сумму, но хочет знать, как это можно сделать аналитически, в частности, l1-минимизация
май
@Kadu это верно, медиана является решением. Вычисление медианы аналитически тривиально; просто отсортируйте, а затем возьмите среднее значение.
Дэвид Кетчесон

Ответы:

22

Возможно, вы просите доказательства того, что медиана решает проблему? Ну, это можно сделать так:

Цель является кусочно-линейной и, следовательно, дифференцируемой, за исключением точек . Каким наклоном объектива является некоторая точка m x i ? Ну, наклон - это сумма наклонов отображений m | м - х J | и это либо + 1 (для m > x j ), либо - 1 (для m < x j ). Следовательно, наклон показывает, сколько x i меньше, чем mm=ximxim|mxj|+1m>xj1m<xjxim . Вы видите, что наклон равен нулю, если есть одинаково много меньше и больше, чем m (для и четного числаxim » s). Если есть нечетное число х я «Sто наклон - 1 слева от„middlest“один и + 1 право его, следовательно, middlest один является минимальным.xixi1+1

кортик
источник
16

Обобщение этой задачи на множественные измерения называется геометрической срединной задачей . Как указывает Дэвид, медиана является решением для одномерного случая; там вы могли бы использовать алгоритмы выбора медианного поиска , которые более эффективны, чем сортировка. Сорта а алгоритмы выбора O ( n ) ; сортировки более эффективны, только если необходимо несколько вариантов выбора, и в этом случае вы можете отсортировать (дорого) один раз, а затем повторно выбирать из отсортированного списка.O(nlogn)O(n)

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

Джефф Оксберри
источник
6

Явное решение с точки зрения медианы является правильным, но в ответ на комментарий Mayenew, вот еще один подход.

1

Следующая формулировка LP подойдет для данного упражнения с неизвестными zi,m

такое, что: z im - x i z i

minzi
zimxi
zixim

Ясно , что должна равняться | х я - мzi|xim|

hardmath
источник
2

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

|mxi|

m<xi

m=xi

m>xi

mx1,xk

cjordan1
источник
0

ArgминмΣязнак равно1N|м-Икся|

d|Икс|dИксзнак равноподписать(Икс)L1
Σязнак равно1Nподписать(м-Икся),
Это равно нулю только тогда, когда количество положительных элементов равно количеству отрицательных, что происходит, когдамзнак равномедиана{Икс1,Икс2,,ИксN},

Следует отметить, что medianдискретная группа не определяется однозначно.
Более того, это не обязательно предмет в группе.

Royi
источник