# How to establish that an iterative method can be applied to large matrices whose size may reach 10^3?

I have an iterative method for computing the Moore-Penrose generalized inverse of matrices, that is

$$X_{k+1} = ((I-\beta X_{k}A)^t) + X_{k}$$

with initial approximation: $$X_{0} = \beta AA^t$$

where:

• $A$ is a given $m \times n$ matrix
• $\beta \in [0,1]$
• $X_{k}$ is the $k$th iterate generated by the algorithm, approximating the Moore-Penrose generalized inverse of matrix $A$.

1. Can this method be applied for higher-order matrices?
2. What is the advantage of this method over other algorithms like singular value decomposition and QR factorization?
3. How would I determine if the iterative algorithm runs faster than the other methods mentioned above?
• @Nunoxic: Looks like we simultaneously edited, feel free to go back and fix anything I missed (I had to stomp over your changes) – Aron Ahmadia Apr 21 '12 at 6:44
• What do you mean by "higher-order matrices"? Like higher-order tensors? – Geoff Oxberry Apr 21 '12 at 7:29
• that mean matrices of order say 1000*1000 – shwetabh Apr 21 '12 at 11:57

2 and 3) These are related questions. Your best bet would be to start with an order of magnitude analysis for each of your algorithms. Basically, using this kind of analysis you can roughly figure out how many computational steps are required for each algorithm as a function of the size of matrix $A$. You can probably assume that if an algorithm takes fewer steps to produce an answer then it will run faster (although in reality this depends on the computational cost of each step. Cost is very implementation dependent, however, so you may not want to get into it). Other possible advantages one algorithm can have over another include requiring less memory or being easier to parallelize.
Program it in Matlab, say, and test it against SVD for increrasing dimensions and matrices generated by $A=BDC$ with random square B and nonrandom diagonal $D>0$ with increasing ratio of $\max_i D_{ii}/\min_i D_{ii}$ Most likely, your method is much slower for the same accuracy.