5 papers
Smoothed analysis of componentwise condition numbers for sparse matrices
Dennis Cheung, Felipe Cucker
We perform a smoothed analysis of the componentwise condition numbers for determinant computation, matrix inversion, and linear equations solving for sparse n times n matrices. The…
Solving Linear Problems with Finite Precision III: Sharp Expectation Bounds
Dennis Cheung, Felipe Cucker
We prove an O(log n) bound for the expectation of the logarithm of the condition number K for the computation of optimizers of linear programs.
Stochastic Vs Worst-case Condition Numbers
Dennis Cheung, Lisa H. Y. Zhou
We compare Stochastic and Worst-case condition numbers and loss of precision for general computational problems. We show an upper bound for the ratio of Worst-case condition number…
Componentwise condition numbers of random sparse matrices
Dennis Cheung, Felipe Cucker
We prove an O(log n) bound for the expected value of the logarithm of the componentwise (and, a fortiori, the mixed) condition number of a random sparse n x n matrix. As a conseque…
On Tail Decay and Moment Estimates of a Condition Number for Random Linear Conic Systems
Dennis Cheung, Felipe Cucker, Raphael Hauser
In this paper we study the distribution tails and the moments of a condition number which arises in the study of homogeneous systems of linear inequalities. We consider the case wh…