PROBABILISTIC ERROR ANALYSIS FOR INNER PRODUCTS
- PMID: 34177105
- PMCID: PMC8225237
- DOI: 10.1137/19m1270434
PROBABILISTIC ERROR ANALYSIS FOR INNER PRODUCTS
Abstract
Probabilistic models are proposed for bounding the forward error in the numerically computed inner product (dot product, scalar product) between two real n-vectors. We derive probabilistic perturbation bounds as well as probabilistic roundoff error bounds for the sequential accumulation of the inner product. These bounds are nonasymptotic, explicit, with minimal assumptions, and with a clear relationship between failure probability and relative error. The roundoffs are represented as bounded, zero-mean random variables that are independent or have conditionally independent means. Our probabilistic bounds are based on Azuma's inequality and its associated martingale, which mirrors the sequential order of computations. The derivation of forward error bounds "from first principles" has the advantage of producing condition numbers that are customized for the probabilistic bounds. Numerical experiments confirm that our bounds are more informative, often by several orders of magnitude, than traditional deterministic bounds-even for small vector dimensions n and very stringent success probabilities. In particular the probabilistic roundoff error bounds are functions of rather than n, thus giving a quantitative confirmation of Wilkinson's intuition. The paper concludes with a critical assessment of the probabilistic approach.
Keywords: 60G42; 60G50; 65F30; 65G50; Azuma’s inequality; concentration bounds; martingale; random variables; roundoff errors.
Figures
Similar articles
-
Stochastic rounding: implementation, error analysis and applications.R Soc Open Sci. 2022 Mar 9;9(3):211631. doi: 10.1098/rsos.211631. eCollection 2022 Mar. R Soc Open Sci. 2022. PMID: 35291325 Free PMC article. Review.
-
A Survey on Scenario Theory, Complexity, and Compression-Based Learning and Generalization.IEEE Trans Neural Netw Learn Syst. 2023 Sep 13;PP. doi: 10.1109/TNNLS.2023.3308828. Online ahead of print. IEEE Trans Neural Netw Learn Syst. 2023. PMID: 37703153
-
A unified approach to universal prediction: generalized upper and lower bounds.IEEE Trans Neural Netw Learn Syst. 2015 Mar;26(3):646-51. doi: 10.1109/TNNLS.2014.2317552. IEEE Trans Neural Netw Learn Syst. 2015. PMID: 25720015
-
Bounding Quantum Contextuality with Lack of Third-Order Interference.Phys Rev Lett. 2015 Jun 5;114(22):220403. doi: 10.1103/PhysRevLett.114.220403. Epub 2015 Jun 4. Phys Rev Lett. 2015. PMID: 26196605
-
Income inequality, social cohesion, and class relations: a critique of Wilkinson's neo-Durkheimian research program.Int J Health Serv. 1999;29(1):59-81. doi: 10.2190/G8QW-TT09-67PL-QTNC. Int J Health Serv. 1999. PMID: 10079398 Review.
Cited by
-
Stochastic rounding: implementation, error analysis and applications.R Soc Open Sci. 2022 Mar 9;9(3):211631. doi: 10.1098/rsos.211631. eCollection 2022 Mar. R Soc Open Sci. 2022. PMID: 35291325 Free PMC article. Review.
References
-
- Babuška I and Söderlind G, On roundoff error growth in elliptic problems, ACM Trans. Math. Software, 44 (2018), 33.
-
- Bareiss EH and Barlow JL, Roundoff error distribution in fixed point multiplication, BIT, 20 (1980), pp. 247–250.
-
- Barlow JL and Bareiss EH, On roundoff error distributions in floating point and logarithmic arithmetic, Computing, 34 (1985), pp. 325–347.
-
- Barlow JL and Bareiss EH, Probabilistic error analysis of Gaussian elimination in floating point and logarithmic arithmetic, Computing, 34 (1985), pp. 349–364.
-
- Bennani M, Brunet M-C, and Chatelin F, De l’utilisation en calcul matriciel de modèles probabilistes pour la simulation des erreurs de calcul, C. R. Math. Acad. Sci. Paris, 307 (1988), pp. 847–850.
Grants and funding
LinkOut - more resources
Full Text Sources