Метод наименьших квадратов для аппроксимации эллипсом в геометрическом смысле., Ищутся сам алгоритм и его реализация. Опции

[Pechka]

Возникла необходимость аппроксимировать полученые данные эллипсом с минизацией квадратов геометрических (не алгебраических!) рсстояний от полученых точек до эллипса. Нашёл много быстрых реализаций для алгебраических расстояний, но нужно именно геометрические минимизировать (поскольку вектора X и Y имеют равную погрешность). В качестве затравки к алгоритму можно использовать результат минимизации алгебраических расстояний так что использование метода Ньютона-Гауса (или других, чувствительных к начальному приближению) вполне пригодно. Может кто-либо встречался с какой-нибудь статьёй на эту тему? или есть готовые библиотеки для таких манипуляций?

[Pechka]

Ах как интересно! А в каком направлении вы собираетесь мерить (минимизируемые) расстояния в этой задаче? Или спрошу об этом иначе - как вы узнаете точку эллипса, которая соответствует конкретной точке данных?

В класическом методе наименьших квадрартов, например, когда прямую линию по экспериментальным точкам проводят, то отклонения измеряют по вертикали (ординате). Их и минимизируют в смысле наименьших квадратов. А когда эллипс, то как? Можно, по-прежнему, по вертикали, то тогда на краях плохо будет. Можно измерять разницу в полярных координатах, по вектору из начала координат. Но где тут это начало? В точке пересечения осей эллипса или в одном из его фокусов? Сплошные непонятки... А может быть из точки надо опускать перпендикуляр на поверхность эллипса? Но тогда очень уж сложно получится.

Я имел ввиду геометрическое расстояние в терминах аналитической геометрии, где геометрическим расстоянием от точки до кривой есть длина перпендикуляра от точки до кривой. То, что задача получается не очень простая мне и так ясно, поэтому спрашиваю о готовом её решении, а не решаю сам.

Что такое геометрическое расстояние (ну и алгебраическое заодно)?
В МНК минимизируют функцию правдоподобия.
Обычно правдоподобие сводят к минимизации квадрата Евклидовой нормы.
Квадрат выбирают:
1. Сильно выпуклая функция
2. Можно дифференцировать

Евклидова (L2) - можно дифференцировать.
Кроме того обычно именно в L2 решение существует (например в l1, l2, C и пр. его может просто не существовать для этой же задачи).

Норма - это длина вектора.
Метрика (расстояние между двумя точками) определяют через норму.
Все это чистая геометрия.
Дискретное представление эллипса можно представить как N_мерный вектор.
Искомое решение на этой же сетке - это другой N-мерный вектор.
Вы (с помощью МНК) минимизируете квадрат расстояния ||Zo-Zp||^2.
Что вы имеете в виду под геометрическим и алгебраическим расстоянием?

Про эллипс подумалось:
Если вам надо [a,b,xo,yo], то это в рамках МНК тоже вектор (размерность 4).

Спасибо за введение в аналитическую геометрию, однако это не является вопросом темы. И если уж придираться - то в МНК минимизируют квадрат некой нормы, которая может являться оптимальной либо не оптимальной в зависимости от условий задачи и выбор которой во многом определяет эффективность метода.
Что касается геометрического расстояния и алгебраического - термины взяты из зарубежной литературы на эту тему, например:
http://www.ulb.ac.be/assoc/bms/Bulletin/sup962/gander.pdf

Если подробнее про расстояния, то алгебраическое это когда норма, которую следует минимизировать является функцией (F(xi)-yi)^2 т.е. предполагается, что по одной из осей погрешность отсчета много меньше чем по другой. Однако, это не всегда верно. и чтобы уравнять оси в "правах" необходимо использовать целевую функцию в смысле геометрического расстояния: (xi-x0)^2+(yi-y0)^2. Для нахождения x0,y0 можно построить нормаль к эллипсу через точку xi,yi и найти её точку пересечения с кривой. Для определённости: в моих рассуждениях использую прямоугольные декартовы координаты. При первых оценках метода у меня всё свелось к уравнению 4й степени, однако, возможно, эту проблему можно обойти. Поэтому я и интересуюсь, может кто-то уже нашёл метод решения в литературе.
Заранее спасибо!

[Xenia]

При первых оценках метода у меня всё свелось к уравнению 4й степени, однако, возможно, эту проблему можно обойти.

Если вам удалось свести данную задачу к уравнению 4-й степени, то вас уже можно поздравить с решением. В чем вы тут видите проблему? В наше время уравнения всех степеней разрешимы и проблемы не представляют.