# Backward stable algorithm to get orthogonal projection onto the column space of a matrix

I have to find the orthogonal projection of a vector $b$ onto the matrix $A$ of size $m \times n$.

In my application, I don't have the luxury of calculating the QR factorization. All I have are routines that give me the least squares solutions with minimum norm, i.e., ${A^\dagger b}$. I can, of course, use matrix multiplication. There are two ways to get $\mbox{proj}_{A}(b)$, $A (A^{\dagger}b)$ or $(A^T)^{\dagger}(A^Tb)$.

What would be the better strategy for following cases in terms of backward stability?

1. $m>n$ and A is full rank.
2. $m>n$ and A is not full rank.
3. $n>m$ and A is not full rank.
4. $n=1$.

For the last part, this suggests that there is no backward stable algorithm on the account of the solution having an outer product. I am not convinced, though, because we never explicitly calculate the outer product.

• Pleas define "least squares solutions with minimum norm". – Rodrigo de Azevedo Feb 3 '18 at 6:17
• I also think that that part of the answer you quote is not correct. – Federico Poloni Feb 3 '18 at 11:45
• What do you mean by "all I have are routines that give me [...] $A^\dagger b$"? There are many ways to compute this solution, with different stability properties: QR, normal equations, SVD, gradient descent... – Federico Poloni Feb 3 '18 at 11:46
• @FedericoPoloni You are right. Edited. – Abhay Gupta Feb 3 '18 at 18:43
• My point is that for rank-deficient matrices, we will get multiple solutions for least squares problem. $A^{\dagger}$ gives the least squares solution which will have the minimum norm. I don't think gradient descent will give me this solution. – Abhay Gupta Feb 5 '18 at 13:03