Condition number | EPFL Graph Search

In numerical analysis, the condition number of a function measures how much the output value of the function can change for a small change in the input argument. This is used to measure how sensitive a function is to changes or errors in the input, and how much error in the output results from an error in the input. Very frequently, one is solving the inverse problem: given f(x) = y, one is solving for x, and thus the condition number of the (local) inverse must be used. In linear regression the condition number of the moment matrix can be used as a diagnostic for multicollinearity. The condition number is an application of the derivative, and is formally defined as the value of the asymptotic worst-case relative change in output for a relative change in input. The "function" is the solution of a problem and the "arguments" are the data in the problem. The condition number is frequently applied to questions in linear algebra, in which case the derivative is straightforwa

Blowing in the Wind

Marta Martinez-Camara

Every day tons of pollutants are emitted into the atmosphere all around the world. These pollutants are altering the equilibrium of our planet, causing profound changes in its climate, increasing global temperatures, and raising the sea level. The need to curb these emissions is clear and urgent. To do so, it is first necessary to estimate the quantity of pollutants that is being emitted. Hence, the central challenge of this thesis: how can we estimate the spatio-temporal emissions of a pollutant from many later observations of the concentration of that pollutant at different times and locations? Mathematically speaking, given such observations and an atmospheric dispersion model, this is a linear inverse problem. Using real datasets, we show that the main difficulties in solving this problem are ill-conditioning and outliers. Ill-conditioning amplifies the effect of additive noise, and each outlier strongly deflects our estimate from the ground truth. We proceed in two different ways to design new estimation methods that can handle these challenges. In the first approach, we enhance traditional estimators, which are already equipped to deal with ill-conditioning, with a preprocessing step to make them robust against outliers. This preprocessing step blindly localizes outliers in the dataset to remove them completely or to downgrade their influence. We propose two ways of localizing outliers: the first one uses several transport models, while the second one uses random sampling techniques. We show that our preprocessing step significantly improves the performance of traditional estimators, both in synthetic datasets as well as in real-world measurements. The second approach is based on enhancing existing robust estimators, which are already equipped to deal with outliers, with suitable regularizations, so that they are stable when the problem is ill-conditioned. We analyze the properties of our new estimators and compare them with the properties of existing estimators, showing the advantages of introducing the regularization. Our new estimators perform well both in the presence and in the absence of outliers, making them generally applicable. They have good performance with up to 50 % of outliers in the dataset. They are also stable when the problem is ill-conditioned. We demonstrate their performance using real-world measurements. Two different algorithms to compute the new estimators are given: one is based on an iterative re-weighted least squares algorithm and the other on a proximal gradient algorithm. Software implementations of all our proposed estimators, along with sample datasets, are provided as part of our commitment to reproducible results. In addition, we provide LinvPy, an open-source python package that contains tested, documented, and user-friendly implementations of our regularized robust algorithms.

EPFL2017

Stochastic distributed learning with gradient quantization and double-variance reduction

Konstantin Mishchenko, Sebastian Urban Stich

We consider distributed optimization over several devices, each sending incremental model updates to a central server. This setting is considered, for instance, in federated learning. Various schemes have been designed to compress the model updates in order to reduce the overall communication cost. However, existing methods suffer from a significant slowdown due to additional variance omega > 0 coming from the compression operator and as a result, only converge sublinearly. What is needed is a variance reduction technique for taming the variance introduced by compression. We propose the first methods that achieve linear convergence for arbitrary compression operators. For strongly convex functions with condition number kappa, distributed among n machines with a finite-sum structure, each worker having less than in components, we also (i) give analysis for the weakly convex and the non-convex cases and (ii) verify in experiments that our novel variance reduced schemes are more efficient than the baselines. Moreover, we show theoretically that as the number of devices increases, higher compression levels are possible without this affecting the overall number of communications in comparison with methods that do not perform any compression. This leads to a significant reduction in communication cost. Our general analysis allows to pick the most suitable compression for each problem, finding the rig ht balance between additional variance and communication savings. Finally, we also (iii) give analysis for arbitrary quantized updates.

TAYLOR & FRANCIS LTD2022

Randomized Extended Kaczmarz For Solving Least Squares

Nikolaos Freris

We present a randomized iterative algorithm that exponentially converges in the mean square to the minimum l(2)-norm least squares solution of a given linear system of equations. The expected number of arithmetic operations required to obtain an estimate of given accuracy is proportional to the squared condition number of the system multiplied by the number of nonzero entries of the input matrix. The proposed algorithm is an extension of the randomized Kaczmarz method that was analyzed by Strohmer and Vershynin.

Society for Industrial and Applied Mathematics2013

Blowing in the Wind

Marta Martinez-Camara

EPFL2017