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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.