Timeline for Approximate the square root of (1-X) efficiently through (nested) products
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 6, 2014 at 7:34 | vote | accept | cdh | ||
| Apr 6, 2014 at 7:34 | comment | added | cdh | Yes, you are right. In that inverse case, by applying sparsifier on $X^2,X^4,\dots,X^{2^d}$, we can actually afford these multiplications, so it takes $d$ multiplications to get $X^2,X^4,\dots,X^{2^d}$. In the inverse square root case, I am now trying to do the similar thing by sparsifying $S_n$ (assuming the update rule is $y_{n+1} = y_n S_n$). There are still difficulties, but it looks promising. | |
| Apr 5, 2014 at 6:57 | comment | added | Federico Poloni | @DehuaCheng I see. Don't you have the same problem in your example with $(I-X)^{-1}$, then? If you expand out all the products, it becomes $2^d$ operations again. | |
| Apr 4, 2014 at 19:58 | comment | added | cdh | Thank you very much for your answer. It partially solved my problem. Although the quadratic convergence of Newton's method is exactly what I am looking for, but expanding the Newton's update ($d$ steps,e.g., from $y_0=I$ to $y_1$ to $y_d$ ) will result in $2^d$ times matrix operations. The reason I don't want to store $y_1$ to $y_d$ is that the matrix multiplication is usually as expensive as calculating its SVD and sorry for not making this clear in the question. Your answer definitely gives me something to work on. | |
| Apr 4, 2014 at 6:17 | history | answered | Federico Poloni | CC BY-SA 3.0 |