инкрементные наименьшие квадраты, отличающиеся только одной строкой

Question

Я должен решить проблему с несколькими наименьшими квадратами последовательно - это один за другим. Каждая наименьшая квадратная проблема из предыдущего изменяется только на одну строку. Правая часть одинакова для всех. Например, задача 1: || Ax-b || и задача 2: || Cy-b || где C и A изменяется только на одну строку. То есть, это эквивалентно удалению строки из A и включение новой строки в A. При решении задачи 2 у меня также есть x. Существует ли быстрый способ решения у задачи 2?

Answer 1

К сожалению, ответ может быть НЕТ ...

Изменение одной строки матрицы приведет к совершенно другому спектру матрицы. Все собственные значения и собственные векторы изменяются как по величине, так и по ориентации. В результате градиент проблемы 1 не останется в задаче 2. Вы можете попытаться использовать свой x из проблемы 1 в качестве первоначального предположения для y в задаче 2, но это не гарантирует сокращения времени поиска в оптимизации.

Однако решение линейных матричных уравнений не так сложно с мощными пакетами. Вы можете использовать LU decomposition или QR decomposition для повышения эффективности вычислений.

Answer 2

Вы можете использовать формулу Sherman-Morrison.

Ключевой элемент решения линейной регрессии вычисляет инверсию A'A.

Если b старая строка из A и a является новая строка в C, то

C'C=A'A-bb'+aa'=A'A+(a-b)(a+b)'

Это выражение может быть вставлен в формулу Шерман-Morrison, чтобы вычислить (C'C)^{-1} задано (A'A)^{- 1}.