遞歸矩陣

Question

快速交叉積我有一個矩陣A中的遞歸運算（這將是一個帽型矩陣），例如：

A(i) = A(i-1) + crossprod(B,A(i-1))

對於每個步驟i我需要的A(i)的跡線。有R中實現這個比下面的實現更快的方法：

# define random matrices 
set.seed(123) 
n <- 7^2*10^4 
steps <- 10 
A <- matrix(rnorm(n), ncol=sqrt(n)) 
B <- matrix(rnorm(n), ncol=sqrt(n)) 

# preallocation 
Amat <- traceA <- vector("list", steps) 
Amat[[1]] <- A 

# recursive computation for matrix A(i) 
ptm <- proc.time() 
for(i in 2:steps){ 
    Amat[[i]] <- Amat[[i-1]] + crossprod(B,Amat[[i-1]]) 
    traceA[[i]] <- sum(diag(Amat[[i]])) 
} 
proc.time() - ptm 

我想提一提的是，矩陣A（i）和矩陣B是對稱的和冪（因爲他們是一頂帽子矩陣線性模型）並且可能非常大。我猜這個並行計算會失敗，因爲for循環需要之前步驟的矩陣A（i-1）。

這背後的想法是一個基於似然的增強算法，其中我需要可以像上面提到的那樣計算的每個增強迭代的帽子矩陣的軌跡。

Answer 1

看起來你Amat_i的可寫爲Amat_i = (1+t(B))^(i-1) * A既然你提到B*B = B或t(B)*t(B) = t(B)，然後

(1+B)^n = 1 + choose(n,1)*B + choose(n,2)*B^2 + ... 
     = 1 + B * (choose(n,1) + choose(n,2) + ... + choose(n,n)) 
     = 1 + B * (2^n - 1) 

把它所有然後一起：

tr(Amat_i) = tr(A) + (2^(i-1) - 1) * tr(t(B)*A) 

所以才計算兩個跟蹤，然後你將不需要再進行矩陣乘法運算來得到所有的tr(Amat_i)。