Max-Plus Algebraic Statistical Leverage Scores

DOI10.1137/16M1097596MaRDI QIDQ4598335zbMATH OpenFDO

Authors

Publication date 20 December 2017

Published in SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1609.09519

zbMATH Keywords

least squaresmax-plus algebraradial basis function networkrandom sampling algorithmrandomized numerical linear algebrastatistical leverage scores

Mathematics Subject Classification ID

Max-plus and related algebras (15A80) Numerical solutions to overdetermined systems, pseudoinverses (65F20)

Abstract: The statistical leverage scores of a complex matrix $Ainmathbb{C}^{nimesd}$ record the degree of alignment between col$(A)$ and the coordinate axes in $mathbb{C}^n$. These score are used in random sampling algorithms for solving certain numerical linear algebra problems. In this paper we present a max-plus algebraic analogue for statistical leverage scores. We show that max-plus statistical leverage scores can be used to calculate the exact asymptotic behavior of the conventional statistical leverage scores of a generic matrices of Puiseux series and also provide a novel way to approximate the conventional statistical leverage scores of a fixed or complex matrix. The advantage of approximating a complex matrices scores with max-plus scores is that the max-plus scores can be computed very quickly. This approximation is typically accurate to within an order or magnitude and should be useful in practical problems where the true scores are known to vary widely.

Recommendations

• Estimating Leverage Scores via Rank Revealing Methods and Randomization
• Exact computation of max weighted score estimators
• An augmented data scoring algorithm for maximum likelihood
• Maximum likelihood estimation for score-driven models
• Maximum scan score-type statistics
• A statistical perspective on algorithmic leveraging
• Conditioning of leverage scores and computation by QR decomposition
• Leverage in Least Squares Additive-Plus-Multiplicative Fits for Two-Way Tables

Cites work

• A statistical perspective on algorithmic leveraging
• Algorithms for the Assignment and Transportation Problems
• Fast approximation of matrix coherence and statistical leverage
• scientific article; zbMATH DE number 4074523 (Why is no real title available?)
• scientific article; zbMATH DE number 627763 (Why is no real title available?)
• scientific article; zbMATH DE number 5018129 (Why is no real title available?)
• Incomplete LU preconditioner based on max-plus approximation of LU factorization
• Max-linear systems. Theory and algorithms.
• Max-plus singular values
• Perturbation of eigenvalues of matrix pencils and the optimal assignment problem
• Revisiting the Nyström method for improved large-scale machine learning
• Sampling algorithms for l₂ regression and applications
• Sketching as a tool for numerical linear algebra
• The auction algorithm for the transportation problem
• Tropical scaling of polynomial matrices
• Uniform sampling for matrix approximation

Cited in

(3)

• Tropical Gaussians: a brief survey
• A Max-Plus Approach to Incomplete Cholesky Factorization Preconditioners
• Estimating Leverage Scores via Rank Revealing Methods and Randomization

Describes a project that uses

Uses Software

• Find
• QuickMatch

This page was built for publication: Max-Plus Algebraic Statistical Leverage Scores

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4598335)