Suponha que eu possua uma matriz densa de m × n , com decomposição SVD A = U S V ⊤ . Em que posso calcular o SVD da seguinte forma: .
R
svd(A)
Se uma nova -ésima linha for adicionada a A , será possível calcular a nova decomposição do SVD com base na antiga (por exemplo, usando U , S e V ), sem recalcular o SVD do zero?
algorithms
svd
linear-algebra
matrix-decomposition
numerics
user1436187
fonte
fonte
rank 1 updates
. As rápidas revisões on-line de SVD para sistemas leves de recomendação da Brand são um primeiro documento acessível. Infelizmente, eu não vi algo para SVD já implementado em R. As atualizações do Cholesky existem (updown
deMatrix
) graças ao CHOLMOD. A esparsidade da sua matriz realmente fará uma diferença na sua solução final; você assume uma matriz densa ou esparsa?Respostas:
Sim, é possível atualizar uma decomposição SVD após adicionar uma nova linha à matriz existente.
Em geral, essa formulação de problema " adicione um a " é conhecida como atualizações de classificação um . O link MathOverflow fornecido pelo @amoeba em " atualizações eficientes de segundo grau de uma decomposição de autovalor " é um ótimo primeiro passo se você deseja começar a aprofundar o assunto; o primeiro artigo fornece uma solução explícita para sua pergunta específica. Apenas para esclarecer o que significam a classificação um e a classificação dois para que você não fique confuso, se o seu novo for tal que:UMA∗
a fórmula de Woodbury entra em jogo. Se você vir essas fórmulas, notará que há muitas inversas envolvidas. Você não os resolve diretamente. Como você já resolveu grande parte de seus subsistemas (por exemplo, você já tem alguma decomposição computada), você os utiliza para obter estimativas mais rápidas e / ou mais estáveis. (É por isso que as pessoas ainda pesquisam esse campo.) Eu usei o livro " Estatísticas Computacionais " de JE Gentle como referência; Eu acho que Chapt. 5 A Álgebra Linear Numérica o configurará corretamente. (O uber-clássico: " Álgebra matricial da perspectiva de um estatístico ", de Harville, infelizmente, não toca em atualizações de classificação.)
Olhando para o lado das estatísticas / aplicativos, as atualizações de classificação 1 são comuns nos sistemas de recomendação, pois é possível ter milhares de entradas de clientes e recalcular o SVD (ou qualquer decomposição fornecida), sempre que um novo usuário se registrar ou um novo produto. adicionado ou removido é um grande desperdício (se não for inatingível). Normalmente, as matrizes do sistema de recomendação são esparsas e isso torna os algoritmos ainda mais eficientes. Um primeiro artigo acessível é o manuscrito " Revisões on-line rápidas de SVD para sistemas de recomendação leve " de M. Brand. Indo para matrizes densas, acho que olhar para os papéis do reconhecimento de padrões e processamento de imagens pode levar você muito longe na obtenção de um algoritmo real para uso. Por exemplo, os papéis:
todos parecem estar enfrentando o mesmo problema em sua essência; novos recursos estão chegando e precisamos atualizar nossa representação rapidamente . Observe que essas matrizes não são simétricas nem quadradas. Outro trabalho de M. Brand também pode abordar esse problema (consulte o artigo " Modificações rápidas de baixa classificação da decomposição de valor singular fino (2006) " - isso também foi mencionado no link MO fornecido no início do post.) muitos trabalhos excelentes sobre o assunto, mas a maioria costuma ser bastante matemática (por exemplo, o artigo de Benaych-Georgesa e Nadakuditi sobre " Os valores e vetores singulares de perturbações de baixa ordem de grandes matrizes aleatórias retangulares (2012)") e não acho que eles ajudarão a obter uma solução em breve. Sugiro que você mantenha seu foco na literatura sobre processamento de imagens.
Infelizmente, não encontrei nenhuma implementação de R para rotinas de atualizações de nível um. A resposta sobre " Implementação de SVD atualizável em Python, C ou Fortran? " Do Computational Science SE fornece várias implementações de MATLAB e C ++ que você pode considerar. Geralmente, a implementação em R, Python etc. é envolvida em implementações em C, C ++ ou FORTRAN.
fonte