Double descent in the condition number
Author(s)
Poggio, Tomaso; Kur, Gil; Banburski, Andrzej![Thumbnail](/bitstream/handle/1721.1/123108/CBMM-Memo-102.pdf.jpg?sequence=4&isAllowed=y)
DownloadCBMM-Memo-102.pdf (837.1Kb)
Metadata
Show full item recordAbstract
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.
Date issued
2019-12-04Publisher
Center for Brains, Minds and Machines (CBMM)
Series/Report no.
CBMM Memo;102