2019/12/12 by Tomaso Poggio, Gil Kur, Poggio, Tomaso +3 · 2 citations
Mathematics · #Advanced Combinatorial Mathematics #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Random Matrices and Applications #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.1912.06190
openalex publication_date 2019/12/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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. Estimates 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 discuss the simple observation, which is known but surprisingly little quoted (see Theorem 4.2 in \citeBrgisser:2013:CGN:2526261): when the columns of A are random vectors, the condition number of A is highest if d=n, that is when the inverse of A exists. An overdetermined system (n>d) as well as an underdetermined system (n