Апроксимация сплайнами, оптимизация размещения контрольных точек Опции

[ataradov]

Эта тема является логическим продолжением вот этой, но может быть интересна и сама по себе, поэтому выношу в отдельный типик.

На картинках изображена характерная кривая (1 - общий план, 2 - приближенное начало), которую нужно представить сплайнами или любым другим способом, занчительно снижающим объем памяти, требуемый для ее хранения, но при этом допускающий сравнительно простое восстановление по точкам, не разжимя всей кривой сразу (то-есть запаковать ее ZIP-ом нельзя ).

Проблема в автоматическом определении положения контрольных точек. Очевидно, что равномерное расположение не выгодно, так как в начале есть сильные осциляции, а в конце график почти прямой.

В идеале нужен алгоритм, который позволит по заданному числу контрольных точек определть их положение так, чтобы СКО было минимальным. Или наоборот, по заданному СКО определить требуемое число точек и их положение.

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

Эскизы прикрепленных изображений

 

[igorchem]

В идеале нужен алгоритм, который позволит по заданному числу контрольных точек определть их положение так, чтобы СКО было минимальным. Или наоборот, по заданному СКО определить требуемое число точек и их положение.

Если Вам необходимо найти оптимальные распределения точек для сплайн аппроксимации k-ой степени в l2 норме, можно поступить так:
вначале аппроксимируете Вашу функцию сплайном k+2 степени s_{k+2}(x).
Далее ищите разбиение x_0 < ... < x_i < ... < x_n так, чтобы
\int_{x_i}^{x_{i+1}} \left(\frac{\delta^{k+1} s_{k+2}(x)}{\delta x^{k+1}}\right)^{\frac1{k+1}} dx было одинакого на всех отрезках. Если запутаетесь или не сможете сами, постораюсь формулы выложить, но, очень надеюсь, что сами справитесь.

От себя хочу по самой задаче добавить. Кажется, если я правильно понял, есть желание аппроксимировать несколько (около 100) функций, у которых есть схожие формы, то есть вначале много осцилляций, в конце - все гладко и есть желание чуток поиграться с шумом.

Моя идея - запишите эти функции (n штук) вначале на очень мелкой сетке с кусочно-постоянными или кусочно-линейными базисными функциями, чтобы шаг такой сетки был существенно меньше минимальной осцилляции. У Вас будет n векторов, образуйте из них матрицу. Сделайте этой матрице сингулярное разложение и выбросьте все сингулярные вектора, сингулярные значения которых будут меньше точности оцифровки вашого сигнала. Примените то, что я описал к оставшимся левым сингулярным векторам. Есть большая уверенность, что после всего этого Вы сильно сожмете эти данные, распаковка их будет съедать только несколько операций на точку, да и шум Вы тоже погасите.

Сообщение отредактировал igorchem - Mar 3 2011, 09:37

[Andrey_1]

Если Вам необходимо найти оптимальные распределения точек для сплайн аппроксимации k-ой степени в l2 норме, можно поступить так:
вначале аппроксимируете Вашу функцию сплайном k+2 степени s_{k+2}(x).
Далее ищите разбиение x_0 < ... < x_i < ... < x_n так, чтобы
\int_{x_i}^{x_{i+1}} \left(\frac{\delta^{k+1} s_{k+2}(x)}{\delta x^{k+1}}\right)^{\frac1{k+1}} dx было одинакого на всех отрезках. Если запутаетесь или не сможете сами, постораюсь формулы выложить, но, очень надеюсь, что сами справитесь.

От себя хочу по самой задаче добавить. Кажется, если я правильно понял, есть желание аппроксимировать несколько (около 100) функций, у которых есть схожие формы, то есть вначале много осцилляций, в конце - все гладко и есть желание чуток поиграться с шумом.

Моя идея - запишите эти функции (n штук) вначале на очень мелкой кусочно-постоянной или кусочно линейной сетке, чтобы шаг такой сетки был существенно меньше минимальной осцилляции. У Вас будет n векторов, образуйте из них матрицу. Сделайте этой матрице сингулярное разложение и выбросьте все сингулярные вектора, сингулярные значения которых будут меньше точности оцифровки вашого сигнала. Примените то, что я описал к оставшимся левым сингулярным векторам. Есть большая уверенность, что после всего этого Вы сильно сожмете эти данные, распаковка их будет съедать только несколько операций на точку, да и шум Вы тоже погасите.

help polyfit
POLYFIT Fit polynomial to data.
P = POLYFIT(X,Y,N) finds the coefficients of a polynomial P(X) of
degree N that fits the data Y best in a least-squares sense. P is a
row vector of length N+1 containing the polynomial coefficients in
descending powers, P(1)*X^N + P(2)*X^(N-1) +...+ P(N)*X + P(N+1).

[P,S] = POLYFIT(X,Y,N) returns the polynomial coefficients P and a
structure S for use with POLYVAL to obtain error estimates for
predictions. S contains fields for the triangular factor ® from a QR
decomposition of the Vandermonde matrix of X, the degrees of freedom
(df), and the norm of the residuals (normr). If the data Y are random,
an estimate of the covariance matrix of P is (Rinv*Rinv')*normr^2/df,
where Rinv is the inverse of R.

[P,S,MU] = POLYFIT(X,Y,N) finds the coefficients of a polynomial in
XHAT = (X-MU(1))/MU(2) where MU(1) = MEAN(X) and MU(2) = STD(X). This
centering and scaling transformation improves the numerical properties
of both the polynomial and the fitting algorithm.

Warning messages result if N is >= length(X), if X has repeated, or
nearly repeated, points, or if X might need centering and scaling.

Class support for inputs X,Y:
float: double, single

See also poly, polyval, roots, lscov.

[igorchem]

help polyfit
POLYFIT Fit polynomial to data.
...

Уважаемый Андрей,

очень хочу поинтересоваться смыслом Вашего ответа на мой топик, мне не понятно несколько моментов:

1. зачем копировать текст от матворкса без ссылки - Ваша копия получилась с не очень красивой визуализацией математических формул, поэтому, на мой вгляд, было бы правильннее дать ссылку на полифит, например так:
http://www.mathworks.com/help/techdoc/ref/polyfit.html

2. как полифит согласуется с вопросом топикстартера?

3. как полифит может быть ответом на мой текст об оптимальном разбиении сплайн-аппроксимации?

4. Вы хоть раз пробовали вписывать такие функции как у топикстартера в полиномы высоких степеней сами, и видели, какая ошибка хоть в l1, хоть в l2 или l_{\infty} получается не говоря об устойчивости такого вписывания? Если нет, то не советуйте то, что не знаете, а если да, очень рад буду от Вас увидеть такие результаты (мне даже достаточно ссылки на Вашу публикацию в нормальном цитируемом журнале), с радостью просвещусь Вашими знаниями!

С уважением

ИИ

[ataradov]

очень хочу поинтересоваться смыслом Вашего ответа на мой топик, мне не понятно несколько моментов:

Не обращайте внимания, человек то-ли самоутверждается, то-ли посты копит для становления своим.

По теме: в формуле с помощью \delta - это обычная производная так странно записана или это какая-то особая производная?

Выбор числа k: при степенях полинома больше 10 получается уже не очень хорошо, много осциляций.

Каков физический смысл подинтегрального выражения?

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