Алгоритм вычисления расстояния суммы квадратов скользящего окна от заданной линейной функции

Question

Учитывая строковую функцию y = a*x + b (a а также b ранее известные константы), легко вычислить расстояние суммы квадратов между линией и окном выборок (1, Y1), (2, Y2), ..., (n, Yn) (где Y1 самый старый образец и Yn самый новый):

sum((Yx - (a*x + b))^2 for x in 1,...,n)

Мне нужен быстрый алгоритм для расчета этого значения для скользящего окна (длины n) - Я не могу повторно сканировать все образцы в окне каждый раз, когда приходит новый образец.
Очевидно, что некоторое состояние должно быть сохранено и обновлено для каждого нового образца, который входит в окно, и каждый старый образец выходит из окна.
Обратите внимание, что когда сэмпл покидает окно, значения остальных сэмплов также меняются - каждый Yx становится Y(x-1). Поэтому, когда образец покидает окно, каждый другой образец в окне вносит другое значение в новую сумму: (Yx - (a*(x-1) + b))^2 вместо (Yx - (a*x + b))^2,

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

Answer 1

Если вы расширите срок (Yx - (a*x + b))^2 условия разбиты на три части:

1. Условия только a,x а также b, Они дают некоторую постоянную при суммировании n и может быть проигнорировано.
2. Условия только Yx а также b, Они могут быть обработаны в стиле интегратора вагонов, как описано в @Xion.
3. Один срок -2*Yx*a*x, -2*a является константой, так что игнорируйте эту часть. Рассмотрим частичную сумму S = Y1*1 + Y2*2 + Y3*3 ... Yn*n, Дано Y1 и бегущая сумма R = Y1 + Y2 + ... + Yn ты можешь найти S - R который устраняет Y1*1 и сокращает все остальные условия, оставляя вас с Y2*1 + Y3*2 + ... + Yn*(n-1), Теперь обновите текущую сумму R что касается (2), вычитая из Y1 и добавление Y(n+1), Добавить новый Yn*n срок до S,

Теперь просто сложите все эти частичные термины.

Answer 2

Разве прямой подход не добьется цели?...

Под "простым" я подразумеваю поддержание очереди образцов. Как только появится новый образец, вы бы:

• вытолкнуть самый старый образец из очереди
• вычесть его расстояние от вашей суммы
• добавить новый образец в очередь
• рассчитать его расстояние и добавить его к вашей сумме

Что касается времени, то здесь все равно O(1), если очередь реализована в виде связанного списка или чего-то подобного, вы также хотите сохранить расстояние с вашими выборками в очереди, поэтому вы рассчитываете его только один раз. Таким образом, использование памяти составляет 3 числа с плавающей запятой на выборку - O(n).