Order of complexity Newton Method (Mock exam 2014), question on Poisson regression
Hello, I am struggling to understand the order of complexity that is given in the answers here.
The Hessian H is the result of a (DxN) x (NxN) x (NxD) matrix multiplication, which if I am not mistaken should be \( O(N^{2}D + ND^{2} \). Could somebody explain to me why this is not included in the final complexity and break down how they reach this final result? Thanks in advance.
According to me you are doing some mistakes, just small one as our NN matrix is diagonal. Multipying it whith a ND matrix, it has a complexity of ND. Indeed you juste have to multiply each element of row i by the element Diag_{ii}, no sums needed. Then you obtain a matrix of size ND and the multiplication of a matrix of size DN and a matrix of size N D is indeed N^2D. As soon as ND is smaller than N^2D we do not care of the first operation in the time complexity. Then after that you have to inverse a matrix of size DD which has a complexity of O(D^{2.7..}) in best case but we will assume O(D^3). After you must compute the gradient which has complexity of O(ND) (small compare to to O(N^2D). Finally, make a matrix vector multiplication between a DD matrix and D1 vector => D^2 complexity small compare to D^3. The finally complexity is O(N^2D + D^3).
I am sorry I did not use beautiful formulas but I hope you understand it.
Order of complexity Newton Method (Mock exam 2014), question on Poisson regression
Hello, I am struggling to understand the order of complexity that is given in the answers here.
The Hessian H is the result of a (DxN) x (NxN) x (NxD) matrix multiplication, which if I am not mistaken should be \( O(N^{2}D + ND^{2} \). Could somebody explain to me why this is not included in the final complexity and break down how they reach this final result? Thanks in advance.
2
According to me you are doing some mistakes, just small one as our NN matrix is diagonal. Multipying it whith a ND matrix, it has a complexity of ND. Indeed you juste have to multiply each element of row i by the element Diag_{ii}, no sums needed. Then you obtain a matrix of size ND and the multiplication of a matrix of size DN and a matrix of size N D is indeed N^2D. As soon as ND is smaller than N^2D we do not care of the first operation in the time complexity. Then after that you have to inverse a matrix of size DD which has a complexity of O(D^{2.7..}) in best case but we will assume O(D^3). After you must compute the gradient which has complexity of O(ND) (small compare to to O(N^2D). Finally, make a matrix vector multiplication between a DD matrix and D1 vector => D^2 complexity small compare to D^3. The finally complexity is O(N^2D + D^3).
I am sorry I did not use beautiful formulas but I hope you understand it.
2
Thank you for clarifying!
Add comment