2
$\begingroup$

Let $A\mathbf{x}=\mathbf{b}$ be an overdetermined system, with $A$ being an $n \times m $ full-column rank rectangular matrix.

Are these minimization problems equivalent?
$$ 1) \;\underset{\mathbf{x}} {\mathop{\min }}\,{{\left\| A\mathbf{x}-\mathbf{b} \right\|}_{2}}$$ $$ 2)\; \underset{\mathbf{x}} {\mathop{\min }}\,({{\left\| A\mathbf{x}-\mathbf{b} \right\|}_{2}})^2 $$

I'm only familiar with the known OLS result which gives rise to the normal equation $\mathbf{x}_{ls}=(A^tA)^{-1}A^t\mathbf{b}$ obtained from $2)$ by expressing it as: $\; \underset{\mathbf{x}} {\mathop{\min }}\ (A\mathbf{x}-\mathbf{b})^t (A\mathbf{x}-\mathbf{b})$ and by imposing gradient to be zero.

I also think that both $1)$ and $2)$ share the convexity property because any "$p-norm$" is convex and a square of a convex non-negative function is still convex.

Improve this question
$\endgroup$
  • 2
    $\begingroup$ In what sense do you mean "equivalent"? Since squaring non-negative numbers is a one-to-one (and order preserving) operation, obviously the solutions are in one-to-one correspondence: it suffices to solve either problem if all you need is the solution. But that doesn't mean they can be solved in the same way or with equal efficiency. What, then, are you trying to ask? $\endgroup$ – whuber♦ Feb 12 '19 at 23:33
  • $\begingroup$ I was wondering how can I show with calculus that the solution for $1)$ is still $\mathbf{x}_{ls}=(A^t A)^{-1}A^t \mathbf{b} $. Is that sufficient to show $2)$ minimization and adding the "one-to-one" consideration you pointed out? $\endgroup$ – omega Feb 12 '19 at 23:41
  • 2
    $\begingroup$ You don't need Calculus, because the relationship between the two is immediate from the observation I made. Using Calculus would just obscure that basic fact. $\endgroup$ – whuber♦ Feb 12 '19 at 23:42
  • $\begingroup$ If you do not square the $2$-norm, the normal equations are given by $$\frac{1}{\| \rm A x - b \|_2} \rm A^\top (\rm A x - b) = 0_n$$ which is problematic if the linear system $\rm A x = b$ is feasible. However, if $\rm A x = b$ is feasible, why use least-squares? $\endgroup$ – Rodrigo de Azevedo Feb 13 '19 at 13:04
  • $\begingroup$ @Rodrigo Did you perhaps misread "overdetermined" as "underdetermined"? $\endgroup$ – whuber♦ Feb 13 '19 at 13:17

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.