2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Аппроксимация с нормой L1
Сообщение11.02.2015, 13:11 
Требуется аппроксимировать набор точек нелинейной функцией $y(t) = A+B\cdot\sin^2(t)$ используя норму L1. С нормой L2 все понятно - получается метод наименьших квадратов:
$F = \sum (y_i - A-B\cdot\sin^2(t_i))^2\rightarrow \min$
В случае L1 в производной по коэффициентам получается необходимость учитывать знак и я что-то не соображу, как решать эту систему
$F = \sum |y_i - A-B\cdot\sin^2(t_i)|\rightarrow \min$

Прошу направить, потому что давно не математик

 
 
 
 Re: Аппроксимация с нормой L1
Сообщение11.02.2015, 13:33 
Аватара пользователя
Начнём с мелочи: ничего нелинейного по существу здесь нет. От коэффициентов зависимость линейная, а значит, это то же самое, что приближать прямой $Ax+B$.
Далее, насчёт как решать, если минимизируем разность модулей. Решается эта штука плохо и неоднозначно.

 
 
 
 Re: Аппроксимация с нормой L1
Сообщение11.02.2015, 20:23 
В принципе задача сводится к линейному программированию: каждый модуль в критерии это пара дополнительных переменных
http://lpsolve.sourceforge.net/5.1/absolute.htm

Тогда задачу можно решить с использованием готовых пакетов (линейное программирование есть даже в Excel). Если количество данных - сотни тысяч или даже миллионы, то метод внутренней точки.

 
 
 
 Re: Аппроксимация с нормой L1
Сообщение12.02.2015, 11:42 
Если делать "руками", то я бы не так решал. Фиксируем $B$ и полагаем $x_i = y_i - B \sin^2 t_i$.
Функционал
$G = \sum |x_i - A|\rightarrow \min$
легко минимизируется по $A$. Для этого надо просто найти медиану в множестве $\{x_i\}, i = \overline {0,N}$.
Ну а дальше, что-нибудь типа делением пополам для оптимизации по $B$.
Сложность получится типа
$O(N \ln N |\ln \varepsilon |)$,
где $ \varepsilon$ - допустимая погрешность. Ну а если чуть постараться, то и от $\ln N$ можно избавиться.
По-моему дешево и сердито.

 
 
 
 Re: Аппроксимация с нормой L1
Сообщение12.02.2015, 12:15 
Оказалось, что велосипед носит имя метода наименьших модулей. В англоязычных источниках Least Absolute Deviations. Методы решения базируются в том числе на симплекс-методе и МНК

 
 
 
 Re: Аппроксимация с нормой L1
Сообщение12.02.2015, 12:34 
Аватара пользователя
МНК служит для того, чтобы посмотреть, как надо, а потом сделать примерно так же?

 
 
 
 Re: Аппроксимация с нормой L1
Сообщение12.02.2015, 13:02 
Не совсем. Это итеративный процесс. Отсылаю к древней книжке Мудров В.И. Кушко. В.Л. Метод наименьших модулей.

 
 
 
 Re: Аппроксимация с нормой L1
Сообщение12.02.2015, 14:14 
Аватара пользователя
Там взвешенный МНК используется. Веса подбираются так, чтобы результат минимизации взвешенных квадратов был бы эквивалентен минимизации по модулям.

 
 
 [ Сообщений: 8 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group