3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Pleas define "least squares solutions with minimum norm". $\endgroup$ – Rodrigo de Azevedo Feb 3 '18 at 6:17
  • $\begingroup$ I also think that that part of the answer you quote is not correct. $\endgroup$ – Federico Poloni Feb 3 '18 at 11:45
  • $\begingroup$ 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... $\endgroup$ – Federico Poloni Feb 3 '18 at 11:46
  • $\begingroup$ @FedericoPoloni You are right. Edited. $\endgroup$ – Abhay Gupta Feb 3 '18 at 18:43
  • 1
    $\begingroup$ 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. $\endgroup$ – Abhay Gupta Feb 5 '18 at 13:03

Your Answer

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

Browse other questions tagged or ask your own question.