Name
Abstract | ||
|---|---|---|
Osborneu0027s iteration is a method for balancing $ntimes n$ matrices which is widely used in linear algebra packages, as balancing preserves eigenvalues and stabilizes their numeral computation. The iteration can be implemented in any norm over $mathbb{R}^n$, but it is normally used in the $L_2$ norm. The choice of norm not only affects the desired balance condition, but also defines the iterated balancing step itself. In this paper we focus on Osborneu0027s iteration in any $L_p$ norm, where $p u003c infty$. We design a specific implementation of Osborneu0027s iteration in any $L_p$ norm that converges to a strictly $epsilon$-balanced matrix in $tilde{O}(epsilon^{-2}n^{9} K)$ iterations, where $K$ measures, roughly, the {em number of bits} required to represent the entries of the input matrix. is the first result that proves that Osborneu0027s iteration in the $L_2$ norm (or any $L_p$ norm, $p u003c infty$) strictly balances matrices in polynomial time. This is a substantial improvement over our recent result (in SODA 2017) that showed weak balancing in $L_p$ norms. Previously, Schulman and Sinclair (STOC 2015) showed strong balancing of Osborneu0027s iteration in the $L_infty$ norm. Their result does not imply any bounds on strict balancing in other norms. |
Year | Venue | DocType |
|---|---|---|
2018 | ICALP | Conference |
Volume | Citations | PageRank |
abs/1704.07406 | 0 | 0.34 |
References | Authors | |
3 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Rafail Ostrovsky | 1 | 8743 | 588.15 |
| Yuval Rabani | 2 | 2265 | 274.98 |
| Arman Yousefi | 3 | 1 | 1.71 |