O artigo da Wikipedia sobre análise de componentes principais afirma que
Existem algoritmos eficientes para calcular o SVD de sem precisar formar a matriz , portanto, calcular o SVD agora é a maneira padrão de calcular uma análise de componentes principais a partir de uma matriz de dados, a menos que apenas alguns componentes sejam necessários.
Alguém poderia me dizer quais são os algoritmos eficientes sobre os quais o artigo está falando? Não há nenhuma referência fornecida (URL ou citação de um artigo que proponha esse método de cálculo seria bom).
pca
algorithms
svd
numerics
svd
fonte
fonte
Respostas:
O principal trabalho por trás do cálculo do SVD é o algoritmo QR . Dito isto, existem muitos algoritmos diferentes para calcular a decomposição do valor singular de um genérico -by- matriz . Um ótimo esquema sobre o problema disponível aqui (na documentação do MKL da Intel ) é o seguinte:M N UMA
Como você vê, dependendo do seu caso de uso, existem abordagens diferentes (as convenções de nomenclatura de rotina podem ser encontradas aqui ). Isso ocorre porque, por exemplo, existem formulários matriciais em que uma redução de agregado familiar pode ser mais cara que uma rotação de Givens (para citar duas maneiras "óbvias" de obter QR). Uma referência padrão sobre o assunto é a Matrix Computations de Golub e Van Loan (eu sugeriria usar pelo menos a 3ª edição). Eu também encontrei Å. Métodos numéricos de Björck para problemas de mínimos quadrados recurso muito bom sobre esse assunto; enquanto SVD não é o foco principal do livro, ajuda a contextualizar o uso.
Se eu tiver que lhe dar um conselho geral sobre o assunto , não tente escrever seus próprios algoritmos SVD, a menos que você tenha realizado com êxito algumas aulas de Álgebra Linear Numérica e saiba o que está fazendo. Eu sei que isso soa contra-intuitivo, mas realmente existe uma tonelada de coisas que podem dar errado e você acaba com (na melhor das hipóteses) implementações sub-ótimas (se não estiver errado). Existem algumas suítes gratuitas muito boas sobre o assunto (por exemplo , Eigen , Tatu e Trilinos, para citar alguns.)
fonte
svds
) chegam ao ponto de simplesmente usar sua função SVD truncada como invólucro para suaseigs
rotinas eigendecomposition ( ) truncadas .