The statistical leverage scores of a matrix A is an element of R-n (x) (d) record the degree of alignment between col(A) and the coordinate axes in R-n. These scores are used in random sampling algorithms for solving ...
详细信息
The statistical leverage scores of a matrix A is an element of R-n (x) (d) record the degree of alignment between col(A) and the coordinate axes in R-n. These scores are used in random sampling algorithms for solving certain numericallinearalgebra problems. In this paper we present a max-plus algebraic analogue of 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 radial basis function network (RBFN) matrix. We also show how max-plus statistical leverage scores can provide a novel way to approximate the conventional statistical leverage scores of a fixed, nonparametrized matrix.
We show how to perform sparse approximate Gaussian elimination for Laplacian matrices. We present a simple, nearly linear time algorithm that approximates a Laplacian by the product of a sparse lower triangular matrix...
详细信息
ISBN:
(纸本)9781509039333
We show how to perform sparse approximate Gaussian elimination for Laplacian matrices. We present a simple, nearly linear time algorithm that approximates a Laplacian by the product of a sparse lower triangular matrix with its transpose. This gives the first nearly linear time solver for Laplacian systems that is based purely on random sampling, and does not use any graph theoretic constructions such as low-stretch trees, sparsifiers, or expanders. Our algorithm performs a subsampled Cholesky factorization, which we analyze using matrix martingales. As part of the analysis, we give a proof of a concentration inequality for matrix martingales where the differences are sums of conditionally independent variables.
Random sampling has become a critical tool in solving massive matrix problems. For linear regression, a small, manageable set of data rows can be randomly selected to approximate a tall, skinny data matrix, improving ...
详细信息
ISBN:
(纸本)9781450333337
Random sampling has become a critical tool in solving massive matrix problems. For linear regression, a small, manageable set of data rows can be randomly selected to approximate a tall, skinny data matrix, improving processing time significantly. For theoretical performance guarantees, each row must be sampled with probability proportional to its statistical leverage score. Unfortunately, leverage scores are difficult to compute. A simple alternative is to sample rows uniformly at random. While this often works, uniform sampling will eliminate critical row information for many natural instances. We take a fresh look at uniform sampling by examining what information it does preserve. Specifically, we show that uniform sampling yields a matrix that, in some sense, well approximates a large fraction of the original. While this weak form of approximation is not enough for solving linear regression directly, it is enough to compute a better approximation. This observation leads to simple iterative row sampling algorithms for matrix approximation that run in input-sparsity time and preserve row structure and sparsity at all intermediate steps. In addition to an improved understanding of uniform sampling, our main proof introduces a structural result of independent interest: we show that every matrix can be made to have low coherence by reweighting a small subset of its rows.
Several innovative random-sampling and random-mixing techniques for solving problems in linearalgebra have been proposed in the last decade, but they have not yet made a significant impact on numericallinearalgebra...
详细信息
Several innovative random-sampling and random-mixing techniques for solving problems in linearalgebra have been proposed in the last decade, but they have not yet made a significant impact on numericallinearalgebra. We show that by using a high-quality implementation of one of these techniques, we obtain a solver that performs extremely well in the traditional yardsticks of numericallinearalgebra: it is significantly faster than high-performance implementations of existing state-of-the-art algorithms, and it is numerically backward stable. More specifically, we describe a least-squares solver for dense highly overdetermined systems that achieves residuals similar to those of direct QR factorization-based solvers (lapack), outperforms lapack by large factors, and scales significantly better than any QR-based solver.
暂无评论