@article {4375, title = {Double descent in the condition number}, year = {2019}, month = {12/2019}, abstract = {

In solving a system of n linear equations in d variables\ \  Ax=b, the condition number of the (n,d) matrix A measures how\ \  much errors in the data b affect the solution x. Bounds of\ \  this type are important in many inverse problems. An example is\ \  machine learning where the key task is to estimate an underlying\ \  function from a set of measurements at random points in a high\ \  dimensional space and where low sensitivity to error in the data is\ \  a requirement for good predictive performance. Here we report the\ \  simple observation that when the columns of A are random vectors,\ \  the condition number of A is highest, that is worse, when d=n,\ \  that is when the inverse of A exists. An overdetermined system\ \  (n\>d) and especially an underdetermined system (n\<d), for which\ \  the pseudoinverse must be used instead of the inverse, typically\ \  have significantly better, that is lower, condition numbers. Thus\ \  the condition number of A plotted as function of d shows a\ \  double descent behavior with a peak at d=n.

}, author = {Tomaso Poggio and Gil Kur and Andrzej Banburski} }