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

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

Разве простой подход не сработает? ...

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

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

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

Answer 2

Если вы расширите термин (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.

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