linear algebra in python

manpreet Best Answer 3 years ago

Giveref="https://forum.tuteehub.com/tag/n">n a tall ref="https://forum.tuteehub.com/tag/m">m×ref="https://forum.tuteehub.com/tag/n">n ref="https://forum.tuteehub.com/tag/m">matrix X, I ref="https://forum.tuteehub.com/tag/n">need to calculate s=1+x(XtX)−1xt. Here, x is a row ref="https://forum.tuteehub.com/tag/vector">vector. Is there aref="https://forum.tuteehub.com/tag/n">n efficieref="https://forum.tuteehub.com/tag/n">nt (or, recoref="https://forum.tuteehub.com/tag/m">mref="https://forum.tuteehub.com/tag/m">meref="https://forum.tuteehub.com/tag/n">nded) way to coref="https://forum.tuteehub.com/tag/m">mpute this iref="https://forum.tuteehub.com/tag/n">n pythoref="https://forum.tuteehub.com/tag/n">n?

Needless to say, XtX will be syref="https://forum.tuteehub.com/tag/m">mref="https://forum.tuteehub.com/tag/m">metric positive defiref="https://forum.tuteehub.com/tag/n">nite.

My atteref="https://forum.tuteehub.com/tag/m">mpt:

If we coref="https://forum.tuteehub.com/tag/n">nsider the QR decoref="https://forum.tuteehub.com/tag/m">mpositioref="https://forum.tuteehub.com/tag/n">n of X, i.e., X=QR, where Q is orthogoref="https://forum.tuteehub.com/tag/n">nal, R is upper triaref="https://forum.tuteehub.com/tag/n">ngular, theref="https://forum.tuteehub.com/tag/n">n XtX=RtR.

QR decoref="https://forum.tuteehub.com/tag/m">mpositioref="https://forum.tuteehub.com/tag/n">n caref="https://forum.tuteehub.com/tag/n">n be easily obtairef="https://forum.tuteehub.com/tag/n">ned usiref="https://forum.tuteehub.com/tag/n">ng

Q, R = ref="https://forum.tuteehub.com/tag/n">nuref="https://forum.tuteehub.com/tag/m">mpy.liref="https://forum.tuteehub.com/tag/n">nalg.qr(X)

But theref="https://forum.tuteehub.com/tag/n">n agairef="https://forum.tuteehub.com/tag/n">n, is there a particularly efficieref="https://forum.tuteehub.com/tag/n">nt way to calculate (RtR)−1?

manpreet 3 years ago

The way I see it, any preprocessing such as QR decomposition, will make the computation substantionally more time and memory expensive, espeially for large m. For sure, QR decomposition works as a normalization in matrix computations and you can avoid some numerical instability problems with it, but I don't think it is of much use in this situtation. Hence, I would probably perform the matrix-matrix product $X^TX

Regarding the inverse, if you do need the matrix itself for some reason, you can either solve n linear equations XTX=ei for i=1,…,n or you can use the SVD implemented in python for amtrix X. That is stable, but rather costly once again. However it provides complete knowledge of the operator XTX, since you obtain the spectral decomposition in this way and at the same time you also have a complete knowledge about X, which may come handy, depending on the algorithm.