Understand
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 \cite{Brgisser: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.
Built on
arXiv preprint arXiv:1903.08560
Hastie T, Montanari A, Rosset S, Tibshirani RJ (2019) Surprises in high-dimensional ridgeless least squares interpolation · 1903
Earlier work this paper cites.
Hastie T, Montanari A, Rosset S, Tibshirani RJ (2019) Surprises in High-Dimensional Ridgeless Least Squares Interpolation · 1903
Earlier work this paper cites.
Mei S, Montanari A (2019) The generalization error of random features regression: Precise asymptotics and double descent curve · 1908
Earlier work this paper cites.
Quarterly J. Mech. Appl. Math
Turing AM (1948) Rounding-off errors in matrix processes · 1948
Earlier work this paper cites.
Mat. Sb. (N.S.)
Marchenko VA, Pastur LA (1967) Distribution of eigenvalues for some sets of random matrices · 1967
Earlier work this paper cites.
Similar
Handbook of the geometry of Banach spaces
Davidson KR, Szarek SJ (2001) Local operator theory, random matrices and banach spaces · 2001
Cited alongside, same era.
SIAM J. Matrix Analysis Applications
Chen Z, Dongarra JJ (2005) Condition numbers of gaussian random matrices · 2005
Cited alongside, same era.
Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences
Rudelson M, Vershynin R (2009) Smallest singular value of a random rectangular matrix · 2009
Cited alongside, same era.
El Karoui N (2010) The spectrum of kernel random matrices · 2010
Cited alongside, same era.
(Springer Publishing Company, Incorporated)
Burgisser P, Cucker F (2013) Condition: The Geometry of Numerical Algorithms · 2013
Cited alongside, same era.
Then
Advani MS, Saxe AM (2017) High-dimensional dynamics of generalization error in neural networks · 2017
Later among the works it cites.
ArXiv e-prints
Belkin M, Ma S, Mandal S (2018) To understand deep learning we need to understand kernel learning · 2018
Later among the works it cites.
Rakhlin A, Zhai X (2018) Consistency of Interpolation with Laplace Kernels is a High-Dimensional Phenomenon · 2018
Later among the works it cites.
Liang T, Rakhlin A (2018) Just Interpolate: Kernel ”Ridgeless” Regression Can Generalize · 2018
Later among the works it cites.
Proceedings of the National Academy of Sciences
Belkin M, Hsu D, Ma S, Mandal S (2019) Reconciling modern machine-learning practice and the classical bias–variance trade-off · 2019
Closest in time.
Beyond the bibliography
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…