# Obtaining column vectors of pseudo-inverse of a matrix

I need to compute the pseudo-inverse of a very large rectangular dense matrix without any special structure or properties. I run out of memory/computing power and have no access to a large parallel computing resource.

However, the good news is that I need only one column of the result at a time (for the subsequent calculations).

Is there any iterative algorithm that can compute the 'kth' column (or at-least progressively build up the first 'k' columns of the pseudo-inverse ?). I'd appreciate any inputs/thoughts on this.

PS: I am using MATLAB for now, but the programming environment does not really matter.

• Is the matrix short and fat or is it tall and thin (that is, does it have many more columns than rows or vice versa)? Is it of full rank in the smaller dimension? – Brian Borchers Oct 14 '15 at 12:16
• You haven't explained why you want columns of the pseudoinverse as opposed to just solving the inverse problem for some collection of right hand sides. – Brian Borchers Oct 15 '15 at 15:55

The pseudo inverse $A^+$ fulfills: $A^+b$ is the minimimum norm solution of the least squares problem $\min_x \|Ax-b\|_2^2$. Hence, to calculate $A^+e_k$ by solving the respective optimization problem (which has a different structure, depending on the format of $A$, as Brian Borchers commented.
You could also use an iterative method to solve $A^TA x = A^Te_k$ in the overdetermined case or solve $AA^Ty = e_k$ and $x = A^T y$ in the underdetermined case, respectively. The method of choice depends on further properties of the matrix…
• If $A$ isn't of full row rank and also not of full column rank, then the normal equations will be singular- you would need to regularize the problem to get a minimum norm least squares solution. – Brian Borchers Oct 14 '15 at 14:46
• @BrianBorchers Good point! But wouldn't CG, initialized with zero, also converge to the right solution of the normal equations $A^TA x = A^T e_k$? (A solution exists, even if $A^TA$ is not of full rank, since $A^Te_k$ is in the range of $A^TA$.) – Dirk Oct 15 '15 at 7:35