3
$\begingroup$

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?
$\endgroup$
  • $\begingroup$ @Nunoxic: Looks like we simultaneously edited, feel free to go back and fix anything I missed (I had to stomp over your changes) $\endgroup$ – Aron Ahmadia Apr 21 '12 at 6:44
  • $\begingroup$ What do you mean by "higher-order matrices"? Like higher-order tensors? $\endgroup$ – Geoff Oxberry Apr 21 '12 at 7:29
  • $\begingroup$ that mean matrices of order say 1000*1000 $\endgroup$ – shwetabh Apr 21 '12 at 11:57
2
$\begingroup$

From the phrasing of question 2, I'm assuming that this is a homework question, so I'm going to give vague answers and not feel too bad about it:

1) A 1000 X 1000 matrix isn't that big, so as long as your computer has enough memory (and any computer made in the last ten years probably would), yes you can run this algorithm on such matrices.

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.

Also, in terms of running speed alone, you can make a set of test cases and then time how long it takes for each algorithm to finish the set.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.