As in case of linear overdetermined system of equations, we can prove that the cost function i.e. the least square function is convex. But in linear underdetermined system, we know that there exist infinite number of solutions, it means the cost function should be non-convex. How can we prove the least square function to be non-convex?

Can anyone provide some suggestions regarding this.

edit:: I was confused if the least square cost function for linear system of equations is always convex or does it depends upon the kind of problem, undetermined or overdetermined?

  • $\begingroup$ Your premise simply isn't true. It's easy to find examples of linear least squares problems with more equations than unknowns where there are infinitely many least squares solutions. Furthermore, the underdetermined linear least squares problem is still a convex optimization problem. Thus there is no answer to your question. $\endgroup$ – Brian Borchers Aug 19 '18 at 19:48
  • $\begingroup$ @BrianBorchers Sir, as there exist infinitely many solutions for underdetermined system, it means the gradient must be zero at more than one point. How is this possible for a convex function? $\endgroup$ – nooob Aug 19 '18 at 19:58
  • 2
    $\begingroup$ $$f (x_1, x_2) := x_1^2$$ has infinitely many minima and is convex. There is a difference between a bowl and an aqueduct. $\endgroup$ – Rodrigo de Azevedo Aug 19 '18 at 20:08
  • $\begingroup$ @BrianBorchers Sorry I was a bit confused, a convex function can have infinite number of points where gradient vanishes. But in case of underdetermined problems, can we say that the function cannot be strictly convex? Also, if we use least square which solution we prefer from those infinite solutions? $\endgroup$ – nooob Aug 19 '18 at 20:10
  • $\begingroup$ You choose the solution with the least Euclidean norm, for instance. Google "least norm solution". $\endgroup$ – Rodrigo de Azevedo Aug 19 '18 at 20:13

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.