Como várias técnicas estatísticas (regressão, PCA, etc.) são escalonadas com o tamanho e a dimensão da amostra?

Existe uma tabela geral conhecida de técnicas estatísticas que explique como elas são dimensionadas com tamanho e dimensão da amostra? Por exemplo, um amigo meu me disse outro dia que o tempo de computação da simples classificação rápida de dados unidimensionais do tamanho n é n * log (n).

Então, por exemplo, se regredirmos y contra X, onde X é uma variável d-dimensional, ela será igual a O (n ^ 2 * d)? Como é a escala se eu quiser encontrar a solução através da solução exata de Gauss-Markov versus mínimos quadrados numéricos com o método Newton? Ou simplesmente obter a solução vs usar testes de significância?

Acho que quero mais uma boa fonte de respostas (como um artigo que resuma o dimensionamento de várias técnicas estatísticas) do que uma boa resposta aqui. Como, digamos, uma lista que inclui o dimensionamento de regressão múltipla, regressão logística, PCA, regressão proporcional ao risco cox, agrupamento K-significa, etc.

A maioria dos algoritmos estatísticos eficientes (e não triviais) é de natureza iterativa, de modo que a análise do pior caso O()é irrelevante, pois o pior caso é "falha na convergência".

No entanto, quando você tem muitos dados, mesmo os algoritmos lineares ( O(n)) podem ser lentos e você precisa se concentrar na constante 'oculta' por trás da notação. Por exemplo, o cálculo da variação de uma única variável é feito ingenuamente, varrendo os dados duas vezes (uma vez para calcular uma estimativa da média e depois uma vez para estimar a variação). Mas também pode ser feito de uma só vez .

Para algoritmos iterativos, o mais importante é a taxa de convergência e o número de parâmetros em função da dimensionalidade dos dados, um elemento que influencia bastante a convergência. Muitos modelos / algoritmos crescem vários parâmetros que são exponenciais com o número de variáveis ​​(por exemplo, splines), enquanto outros crescem linearmente (por exemplo, suportam máquinas de vetores, florestas aleatórias, ...)

Você mencionou regressão e PCA no título, e há uma resposta definitiva para cada uma delas.

A complexidade assintótica da regressão linear reduz-se a O (P ^ 2 * N) se N> P, onde P é o número de características e N é o número de observações. Mais detalhes em Complexidade computacional da operação de regressão pelo quadrado mínimo .

O PCA de baunilha é O (P ^ 2 * N + P ^ 3), como no algoritmo PCA mais rápido para dados de alta dimensão . No entanto, existem algoritmos rápidos para matrizes muito grandes, explicados nessa resposta e no melhor algoritmo PCA para um grande número de recursos? .

No entanto, acho que ninguém compilou uma única resenha, referência ou livro sobre o assunto. Pode não ser um projeto ruim para o meu tempo livre ...

Dei uma resposta parcial muito limitada ao pacote de análise fatorial confirmatória que desenvolvi para o Stata neste artigo do Stata Journal, com base no tempo das simulações reais. A análise fatorial confirmatória foi implementada como uma técnica de estimativa de máxima verossimilhança, e pude ver com muita facilidade como o tempo de computação cresceu com cada dimensão (tamanho da amostra n, número de variáveis p, número de fatores k). Como é fortemente dependente de como o Stata pensa sobre os dados (otimizado para calcular através de colunas / observações em vez de linhas), achei o desempenhoO(n^{0.68} (k+p)^{2.4})onde 2.4 é o mais rápido de inversão de matriz assintótica (e há muito disso na maximização iterativa da análise fatorial confirmatória). Não dei uma referência para o último, mas acho que peguei isso na Wikipedia .

X'X$10^8$