Double descent in the condition number

TitleDouble descent in the condition number
Publication TypeCBMM Memos
Year of Publication2019
AuthorsPoggio, T, Kur, G, Banburski, A
Date Published12/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.

DSpace@MIT

https://hdl.handle.net/1721.1/123108

CBMM Memo No:  102

Associated Module: 

Research Area: 

CBMM Relationship: 

  • CBMM Funded