7

Thanks for reading my thread.

I am thinking, many of us know that Moore–Penrose pseudoinverse can solve for overdetermined system $Ax=b$, where $x=(A^TA)^{-1}A^Tb$; for exmplae the linear regression application , or curve fitting applications.

However, I am wondering for underdetermined system, can we use Moore–Penrose pseudoinverse solver? If yes, why we need many iterative reconstruction algorithm? Since we can know the derivative of the objective anyway, then why don't we just set the derivative to 0, then solve it using some skills like Moore–Penrose pseudoinverse?

Some explanation in theory is highly appreciated. Does not have to be rigorous prove, but something that makes sense. Thanks a lot!

Michael Hardy
  • 1
Ono
  • 429
  • I suspect the "curve-fitting applications" you have in mind are themselves instances of linear regression, so you wouldn't need to mention those separately. – Michael Hardy Apr 21 '14 at 20:32
  • @MichaelHardy For example, fitting $y = a \sqrt{x} + b$ to data using least squares is a curve fitting problem (and can be solved with pseudoinverse), but it is not linear regression. – user127096 Apr 21 '14 at 23:00
  • Pseudoinverse indeed solves underdetermined linear system, picking the solution of smallest $\ell_2$ norm. Two questions to consider: (a) do we want the solution of smallest $\ell_2$ norm? (b) is it computationally feasible to find the pseudoinverse of the relevant matrix? (What size of matrix are we talking about?) If the answer to either one is no, one has to think of other ways... – user127096 Apr 21 '14 at 23:04
  • @user127096 : If you observe $(x_i,y_i)$ for $i=1,\ldots,n$ and find the values $\hat a$ and $\hat b$ that minimize the sum of the squares of the residuals $y_i-(\hat a\sqrt{x} +\hat b)$ then that is an instance of linear regression. On the other hand, if you fit $y=\dfrac{ax}{b+x}$, you're doing nonlinear regession. – Michael Hardy Apr 22 '14 at 01:29
  • @user127096 Suppose you want to fit $y = a + bu +cv$ when you've observed $(u_i,v_i,y_i)$ for $i=1,2$. I.e. only two data points. What would you mean by picking the solution with the smallest $\ell_2$ norm? – Michael Hardy Apr 22 '14 at 01:31
  • @user127096 : Pardon me, but your mistaken comment above causes me to wonder if you have fallen into the commonplace mistake of thinking that the word "linear" in "linear regression" is there because one is fitting a line rather than some other curve. For a bit more on that see this question: http://math.stackexchange.com/questions/75959/why-is-polynomial-regression-considered-a-kind-of-linear-regression – Michael Hardy Apr 22 '14 at 01:39

1 Answers1

5

If $A^TA$ is not positive definite (or it's not invertible, or equivalently some of its eigen values are zero), then we can either use the Moore–Penrose inverse, or we can use Tikhonov regularization.

Tikhonov regularization calculates the regular inverse of $(A^TA+\epsilon I)$ for some small $\epsilon$, and uses this inverse instead.

Moore–Penrose inverse is basically based on the SVD decomposition of $A^TA$ say $V\Lambda V^T$, where $V$ is a unitary matrix and $\Lambda$ is a diagonal matrix. Then $(A^TA)^{-1}=V\Lambda^{-1} V^T$, if an element $\lambda_i$ (a singular value) on the diagonal of $\Lambda$ is not zero then we replace it with $1/\lambda_i$ in $\Lambda^{-1}$, but if it's zero, we set the corresponding element to zero in $\Lambda^{-1}$.

Now we can answer your question, about why people use iterative solutions. There can be several reasons, one is when you have other constraints on the variable $x$, then $(A^TA)^{-1}A^Tb$ is not the solution. But the main reason is that for large scale $A$, calculating the SVD decomposition for example can be expensive, and at the same time it maybe not memory efficient. Some times you don't have access to full $A$, and can only observe a sparse representation of it, and so on.

Alt
  • 2,592