Метод наименьших квадратов с итеративным перевесом - Iteratively reweighted least squares

Методика методом наименьших квадратов с повторным взвешиванием (IRLS) используется для решения определенных задач оптимизации с целевые функции формы п-норма:

${displaystyle {underset {oldsymbol {eta }}{operatorname {arg,min} }}sum _{i=1}^{n}{ig |}y_{i}-f_{i}({oldsymbol {eta }}){ig |}^{p},}$

по итерационный метод в котором каждый шаг включает решение взвешенный метод наименьших квадратов проблема формы:^[1]

${displaystyle {oldsymbol {eta }}^{(t+1)}={underset {oldsymbol {eta }}{operatorname {arg,min} }}sum _{i=1}^{n}w_{i}({oldsymbol {eta }}^{(t)}){ig |}y_{i}-f_{i}({oldsymbol {eta }}){ig |}^{2}.}$

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

Одно из преимуществ IRLS перед линейное программирование и выпуклое программирование в том, что его можно использовать с Гаусс – Ньютон и Левенберг-Марквардт численные алгоритмы.

Примеры

L₁ минимизация для разреженного восстановления

IRLS можно использовать для ℓ₁ минимизация и сглаживание ℓ_п минимизация, п <1, в сжатое зондирование проблемы. Доказано, что алгоритм имеет линейную скорость сходимости при ℓ₁ норма и сверхлинейный для ℓ_т с т <1, под свойство ограниченной изометрии, что обычно является достаточным условием для разреженных решений.^[2][3] Однако в большинстве практических ситуаций свойство ограниченной изометрии не выполняется.^{[нужна цитата ]}

L^п нормальная линейная регрессия

Чтобы найти параметры β = (β₁, …,β_k)^Т которые минимизируют L^п норма для линейная регрессия проблема,

${displaystyle {underset {oldsymbol {eta }}{operatorname {arg,min} }}{ig |}mathbf {y} -X{oldsymbol {eta }}|_{p}={underset {oldsymbol {eta }}{operatorname {arg,min} }}sum _{i=1}^{n}left|y_{i}-X_{i}{oldsymbol {eta }}ight|^{p},}$

алгоритм IRLS на шаге т + 1 предполагает решение взвешенный линейный метод наименьших квадратов проблема:^[4]

${displaystyle {oldsymbol {eta }}^{(t+1)}={underset {oldsymbol {eta }}{operatorname {arg,min} }}sum _{i=1}^{n}w_{i}^{(t)}left|y_{i}-X_{i}{oldsymbol {eta }}ight|^{2}=(X^{m {T}}W^{(t)}X)^{-1}X^{m {T}}W^{(t)}mathbf {y} ,}$

куда W^(т) это диагональная матрица весов, обычно со всеми элементами, изначально установленными на:

${displaystyle w_{i}^{(0)}=1}$

и обновляется после каждой итерации до:

${displaystyle w_{i}^{(t)}={ig |}y_{i}-X_{i}{oldsymbol {eta }}^{(t)}{ig |}^{p-2}.}$

В случае п = 1, это соответствует наименьшее абсолютное отклонение регрессии (в этом случае к проблеме лучше подойти с помощью линейное программирование методы,^[5] так что результат будет точным) и формула:

${displaystyle w_{i}^{(t)}={frac {1}{{ig |}y_{i}-X_{i}{oldsymbol {eta }}^{(t)}{ig |}}}.}$

Чтобы избежать деления на ноль, регуляризация необходимо сделать, поэтому на практике формула выглядит так:

${displaystyle w_{i}^{(t)}={frac {1}{max left{delta ,left|y_{i}-X_{i}{oldsymbol {eta }}^{(t)}ight|ight}}}.}$

куда ${displaystyle delta }$ какое-то небольшое значение, например 0,0001.^[5] Обратите внимание на использование ${displaystyle delta }$ в весовой функции эквивалентно Потеря Хубера функция в робастной оценке. ^[6]

Смотрите также

• Возможные обобщенные методы наименьших квадратов
• Алгоритм Вайсфельда (для аппроксимации геометрическая медиана ), который можно рассматривать как частный случай IRLS

Примечания

1. К. Сидни Беррус, Итеративная переориентация наименьших квадратов
2. Chartrand, R .; Инь В. (31 марта - 4 апреля 2008 г.). «Алгоритмы с итеративным изменением веса для сжатия данных». Международная конференция IEEE по акустике, речи и обработке сигналов (ICASSP), 2008 г.. С. 3869–3872. Дои:10.1109 / ICASSP.2008.4518498.
3. Daubechies, I .; Devore, R .; Fornasier, M .; Гюнтюрк, К. С. Н. (2010). «Минимизация методом наименьших квадратов с повторным взвешиванием для разреженного восстановления». Сообщения по чистой и прикладной математике. 63: 1–38. arXiv:0807.0575. Дои:10.1002 / cpa.20303.
4. Нежный, Джеймс (2007). «6.8.1 Решения, минимизирующие другие нормы остатков». Матричная алгебра. Тексты Springer в статистике. Нью-Йорк: Спрингер. Дои:10.1007/978-0-387-70873-7. ISBN  978-0-387-70872-0.
5. Уильям А. Пфейл,Статистические учебные пособия, Диссертация бакалавра наук, Вустерский политехнический институт, 2006
6. Fox, J .; Вайсберг, С. (2013),Надежная регрессия, Курс, Миннесотский университет

Рекомендации

• Численные методы для задач наименьших квадратов, Оке Бьорк (Глава 4: Обобщенные задачи наименьших квадратов.)
• Практические методы наименьших квадратов для компьютерной графики. SIGGRAPH Курс 11

внешняя ссылка

• Итеративное решение недоопределенных линейных систем