Каков BigO линейной регрессии?
Насколько большой система - это разумный, чтобы попытаться сделать линейную регрессию на?
Конкретно: у Меня есть система с ~300K точками выборки и ~1200 линейными членами. Это в вычислительном отношении выполнимо?
1 ответ
Можно выразить это как матричное уравнение:
, где матрица 
- 300К строк и 1200 столбцов, вектор коэффициента 
- 1200х1, а вектор RHS 
- 1200х1.
Если умножить обе стороны на транспонирование матрицы 
, то получится система уравнений для неизвестных - 1200х1200. Для коэффициентов можно использовать LU-разложение или любой другой алгоритм, который Вы хотите решить. (Это то, что делают наименьшие квадраты.)
Так что поведение Big-O - это что-то вроде O(mmn), где m = 300K и n = 1200. Чтобы получить коэффициенты, нужно учитывать транспозирование, умножение матриц, разложение LU и подстановку вперед-назад.
.