检索结果-内蒙古大学图书馆

randomized LOW-RANK APPROXIMATION OF MONOTONE MATRIX FUNCTIONS

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS 2023年第2期44卷 894-918页

作者： Persson, David Kressner, Daniel EPF Lausanne Inst Math CH-1015 Lausanne Switzerland

This work is concerned with computing low-rank approximations of a matrix function f(A) for a large symmetric positive semidefinite matrix A, a task that arises in, e.g., statistical learning and inverse problems. The application of popular randomized methods, such as the randomized singular value decomposition or the Nystrom approximation, to f(A) requires multiplying f(A) with a few random vectors. A significant disadvantage of such an approach, matrix-vector products with f(A) are considerably more expensive than matrix-vector products with A, even when carried out only approximately via, e.g., the Lanczos method. In this work, we present and analyze funNystrom, a simple and inexpensive method that constructs a low-rank approximation of f(A) directly from a Nystrom approximation of A, completely bypassing the need for matrix-vector products with f(A). It is sensible to use funNystrom whenever f is monotone and satisfies f(0) = 0. Under the stronger assumption that f is operator monotone, which includes the matrix square root A(1/2) and the matrix logarithm log(I + A), we derive probabilistic bounds for the error in the Frobenius, nuclear, and operator norms. These bounds confirm the numerical observation that funNystrom tends to return an approximation that compares well with the best low-rank approximation of f(A). Furthermore, compared to existing methods, funNystrom requires significantly fewer matrix-vector products with A to obtain a low-rank approximation of f(A), without sacrificing accuracy or reliability. Our method is also of interest when estimating quantities associated with f(A), such as the trace or the diagonal entries of f(A). In particular, we propose and analyze funNystrom++, a combination of funNystrom with the recently developed Hutch++ method for trace estimation.

关键词： low-rank approximation randomized numerical linear algebra matrix functions

来源：评论

学校读者我要写书评

暂无评论

Simpler is better: a comparative study of randomized pivoting algorithms for CUR and interpolative decompositions

引用

ADVANCES IN COMPUTATIONAL MATHEMATICS 2023年第4期49卷 1-29页

作者： Dong, Yijun Martinsson, Per-Gunnar Univ Texas Austin Oden Inst Computat Engn & Sci 201 E 24th St Austin TX 78712 USA Univ Texas Austin Dept Math 2515 Speedway PMA 8-100 Austin TX 78712 USA

Matrix skeletonizations like the interpolative and CUR decompositions provide a framework for low-rank approximation in which subsets of a given matrix's columns and/or rows are selected to form approximate spanning sets for its column and/or row space. Such decompositions that rely on "natural" bases have several advantages over traditional low-rank decompositions with orthonormal bases, including preserving properties like sparsity or non-negativity, maintaining semantic information in data, and reducing storage requirements. Matrix skeletonizations can be computed using classical deterministic algorithms such as column-pivoted QR, which work well for small-scale problems in practice, but suffer from slow execution as the dimension increases and can be vulnerable to adversarial inputs. More recently, randomized pivoting schemes have attracted much attention, as they have proven capable of accelerating practical speed, scale well with dimensionality, and sometimes also lead to better theoretical guarantees. This manuscript provides a comparative study of various randomized pivoting-based matrix skeletonization algorithms that leverage classical pivoting schemes as building blocks. We propose a general framework that encapsulates the common structure of these randomized pivoting-based algorithms and provides an a-posteriori-estimable error bound for the framework. Additionally, we propose a novel concretization of the general framework and numerically demonstrate its superior empirical efficiency.

关键词： Low-rank approximation Interpolative decomposition CUR decomposition randomized numerical linear algebra Column pivoted QR factorization Rank revealing factorization

来源：评论

学校读者我要写书评

暂无评论

Bootstrapping the operator norm in high dimensions: Error estimation for covariance matrices and sketching

引用

BERNOULLI 2023年第1期29卷 428-450页

作者： Lopes, Miles E. Erichson, N. Benjamin Mahoney, Michael W. Univ Calif Davis Dept Stat Math Sci Bldg Davis CA 95616 USA Univ Calif Berkeley Dept Stat Evans Hall Berkeley CA 94720 USA Int Comp Sci Inst Berkeley CA 94704 USA

Although the operator (spectral) norm is one of the most widely used metrics for covariance estimation, compara-tively little is known about the fluctuations of error in this norm. To be specific, let (Sigma) over cap denote the sample covariance matrix of n i.i.d. observations in R-p that arise from a population matrix E, and let T-n = root n parallel to(Sigma) over cap - Sigma parallel to op. In the setting where the eigenvalues of Sigma have a decay profile of the form lambda(j)(Sigma) asymptotic to j(-2 beta), we analyze how well the bootstrap can approximate the distribution of T-n. Our main result shows that up to factors of log(n), the bootstrap can approxi-mate the distribution of T-n with respect to the Kolmogorov metric at the rate of n(-beta-1/2/6 beta+4), which does not depend on the ambient dimension p. In addition, we offer a supporting result of independent interest that establishes a high-probability upper bound for T-n based on flexible moment assumptions. More generally, we discuss the consequences of our work beyond covariance matrices, and show how the bootstrap can be used to estimate the errors of sketching algorithms in randomized numerical linear algebra (RandNLA). An illustration of these ideas is also provided with a climate data example.

关键词： Bootstrap error estimation high-dimensional statistics covariance estimation randomized numerical linear algebra sketching

来源：评论

学校读者我要写书评

暂无评论

PRACTICAL LEVERAGE-BASED SAMPLING FOR LOW-RANK TENSOR DECOMPOSITION

引用

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS 2022年第3期43卷 1488-1517页

作者： Larsen, Brett W. Kolda, Tamara G. Stanford Univ Stanford CA 94305 USA MathSci Ai Dublin CA 94568 USA

The low-rank canonical polyadic tensor decomposition is useful in data analysis and can be computed by solving a sequence of overdetermined least squares subproblems. Motivated by consideration of sparse tensors, we propose sketching each subproblem using leverage scores to select a subset of the rows, with probabilistic guarantees on the solution accuracy. We randomly sample rows proportional to leverage score upper bounds that can be efficiently computed using the special Khatri-Rao subproblem structure inherent in tensor decomposition. Crucially, for a (d + 1)-way tensor, the number of rows in the sketched system is O(r(d)/epsilon) for a decomposition of rank r and epsilon-accuracy in the least squares solve, independent of both the size and the number of nonzeros in the tensor. Along the way, we provide a practical solution to the generic matrix sketching problem of sampling overabundance for high-leverage-score rows, proposing to include such rows deterministically and combine repeated samples in the sketched system;we conjecture that this can lead to improved theoretical bounds. numerical results on real-world large-scale tensors show the method is significantly faster than deterministic methods at nearly the same level of accuracy.

关键词： tensor decomposition CANDECOMP/PARAFAC canonical polyadic CP matrix sketching leverage score sampling randomized numerical linear algebra RandNLA

来源：评论

学校读者我要写书评

暂无评论

Computationally Efficient Approximations for Matrix-Based Renyi's Entropy

引用

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2022年 70卷 6170-6184页

作者： Gong, Tieliang Dong, Yuxin Yu, Shujian Dong, Bo Jiaotong Univ Sch Comp Sci & Technol Xian 710049 Peoples R China Shaanxi Prov Key Lab Big Data Knowledge Engn Xian 710049 Peoples R China UiT Arctic Univ Norway Machine Learning Grp N-9019 Tromso Norway Vrije Univ Amsterdam Dept Comp Sci NL-1081 HV Amsterdam Netherlands

The recently developed matrix-based Renyi's alpha-order entropy enables measurement of information in data simply using the eigenspectrum of symmetric positive semi-definite (PSD) matrices in reproducing kernel Hilbert space, without estimation of the underlying data distribution. This intriguing property makes this new information measurement widely adopted in multiple statistical inference and learning tasks. However, the computation of such quantity involves the trace operator on a PSD matrix G to power alpha (i.e., tr(G(alpha))), with a normal complexity of nearly O (n(3)), which severely hampers its practical usage when the number of samples (i.e., n) is large. In this work, we present computationally efficient approximations to this new entropy functional that can reduce its complexity to even significantly less than O (n(2)). To this end, we leverage the recent progress on randomized numerical linear algebra, developing Taylor, Chebyshev and Lanczos approximations to tr(G(alpha) ) for arbitrary values of alpha by converting it into a matrix-vector multiplication problem. We also establish the connection between the matrix-based Renyi's entropy and PSD matrix approximation, which enables exploiting both clustering and block low-rank structure of G to further reduce the computational cost. We theoretically provide approximation accuracy guarantees and illustrate the properties for different approximations. Large-scale experimental evaluations on both synthetic and real-world data corroborate our theoretical findings, showing promising speedup with negligible loss in accuracy.

关键词： Entropy Kernel Estimation Symmetric matrices Signal processing algorithms Eigenvalues and eigenfunctions Approximation algorithms Matrix-based Renyi's entropy randomized numerical linear algebra trace estimation information bottleneck mutual information

来源：评论

学校读者我要写书评

暂无评论

Algorithmic Gaussianization through Sketching: Converting Data into Sub-gaussian Random Designs 36

Algorithmic Gaussianization through Sketching: Converting Da...

引用

36th Annual Conference on Learning Theory (COLT)

作者： Derezinski, Michal Univ Michigan Ann Arbor MI 48109 USA

Algorithmic Gaussianization is a phenomenon that can arise when using randomized sketching or sampling methods to produce smaller representations of large datasets: For certain tasks, these sketched representations have been observed to exhibit many robust performance characteristics that are known to occur when a data sample comes from a sub-gaussian random design, which is a powerful statistical model of data distributions. However, this phenomenon has only been studied for specific tasks and metrics, or by relying on computationally expensive methods. We address this by providing an algorithmic framework for gaussianizing data using sparse sketching operators, proving that it is possible to efficiently construct data sketches that are nearly indistinguishable (in terms of total variation distance) from sub-gaussian random designs. In particular, relying on a recently introduced sketching technique called Leverage Score Sparsified (LESS) embeddings, we show that one can construct an n x d sketch of an N x d matrix A, where n << N, that is nearly indistinguishable from a sub-gaussian design, in time O(nnz(A) log N + nd(2)), where nnz(A) is the number of non-zero entries in A. As a consequence, strong statistical guarantees and precise asymptotics available for the estimators produced from sub-gaussian designs (e.g., for least squares and Lasso regression, covariance estimation, low-rank approximation, etc.) can be straightforwardly adapted to our sketching framework. We illustrate this with a new approximation guarantee for sketched least squares, among other examples. The key technique that enables our analysis is a novel variant of the Hanson-Wright inequality on the concentration of random quadratic forms, which we establish for random vectors that arise from sparse sketches.

关键词： Sketching Least squares randomized numerical linear algebra Sub-gaussianity

来源：评论

学校读者我要写书评

暂无评论

Projection-Based QLP Algorithm for Efficiently Computing Low-Rank Approximation of Matrices

引用

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2021年 69卷 2218-2232页

作者： Kaloorazi, Maboud F. Chen, Jie Northwestern Polytech Univ Sch Marine Sci & Technol Xian Peoples R China Xian Shiyou Univ Sch Elect Engn Xian 710000 Peoples R China

Matrices with low numerical rank are omnipresent in many signal processing and data analysis applications. The pivoted QLP (p-QLP) algorithm constructs a highly accurate approximation to an input low-rank matrix. However, it is computationally prohibitive for large matrices. In this paper, we introduce a new algorithm termed Projection-based Partial QLP (PbP-QLP) that efficiently approximates the p-QLP with high accuracy. Fundamental in our work is the exploitation of randomization and in contrast to the p-QLP, PbP-QLP does not use the pivoting strategy. As such, PbP-QLP can harness modern computer architectures, even better than competing randomized algorithms. The efficiency and effectiveness of our proposed PbP-QLP algorithm are investigated through various classes of synthetic and real-world data matrices.

关键词： Matrix decomposition Approximation algorithms Signal processing algorithms Sparse matrices Singular value decomposition Signal processing Oceanography Low-rank approximation rank-revealing matrix factorization the pivoted QLP the singular value decomposition randomized numerical linear algebra

来源：评论

学校读者我要写书评

暂无评论

randomized QUASI-OPTIMAL LOCAL APPROXIMATION SPACES IN TIME

引用

SIAM JOURNAL ON SCIENTIFIC COMPUTING 2023年第3期45卷 A1066-A1096页

作者： Schleub, Julia Smetana, Kathrin Ter Maat, Lukas Univ Munster Fac Math & Comp Sci Einsteinstr 62 D-48149 Munster Germany Stevens Inst Technol Dept Math Sci Hoboken NJ 07030 USA Univ Twente NL-7522 NB Enschede Netherlands

We target time-dependent partial differential equations (PDEs) with heterogeneous coefficients in space and time. To tackle these problems, we construct reduced basis/multiscale ansatz functions defined in space that can be combined with time stepping schemes within model order reduction or multiscale methods. To that end, we propose to perform several simulations of the PDE for a few time steps in parallel starting at different, randomly drawn start points, prescribing random initial conditions;applying a singular value decomposition to a subset of the so obtained snapshots yields the reduced basis/multiscale ansatz functions. This facilitates constructing the reduced basis/multiscale ansatz functions in an embarrassingly parallel manner. In detail, we suggest using a data-dependent probability distribution based on the data functions of the PDE to select the start points. Each local in time simulation of the PDE with random initial conditions approximates a local approximation space in one time point that is optimal in the sense of Kolmogorov. The derivation of these optimal local approximation spaces which are spanned by the left singular vectors of a compact transfer operator that maps arbitrary initial conditions to the solution of the PDE in a later point of time is one other main contribution of this paper. By solving the PDE locally in time with random initial conditions, we construct local ansatz spaces in time that converge provably at a quasi-optimal rate and allow for local error control. numerical experiments demonstrate that the proposed method can outperform existing methods like the proper orthogonal decomposition even in a sequential setting and is well capable of approximating advection-dominated problems.

关键词： multiscale methods model order reduction randomized numerical linear algebra Kolmogorov n-width

来源：评论

学校读者我要写书评

暂无评论

PLSS: A PROJECTED linear SYSTEMS SOLVER

引用

SIAM JOURNAL ON SCIENTIFIC COMPUTING 2023年第2期45卷 A1012-A1037页

作者： Brust, Johannes J. Saunders, Michael A. Univ Calif San Diego Dept Math La Jolla CA 92093 USA Stanford Univ Dept Management Sci & Engn Stanford CA 94305 USA

We propose iterative projection methods for solving square or rectangular consistent linear systems Ax = b. Existing projection methods use sketching matrices (possibly randomized) to generate a sequence of small projected subproblems, but even the smaller systems can be costly. We develop a process that appends one column to the sketching matrix each iteration and converges in a finite number of iterations whether the sketch is random or deterministic. In general, our process generates orthogonal updates to the approximate solution x(k). By choosing the sketch to be the set of all previous residuals, we obtain a simple recursive update and convergence in at most rank(A) iterations (in exact arithmetic). By choosing a sequence of identity columns for the sketch, we develop a generalization of the Kaczmarz method. In experiments on large sparse systems, our method (PLSS) with residual sketches is competitive with LSQR and LSMR and with residual and identity sketches compares favorably with state-of-the-art randomized methods.

关键词： linear systems iterative solver randomized numerical linear algebra projection method LSQR Kaczmarz method LSMR Craig's method

来源：评论

学校读者我要写书评

暂无评论

Statistical properties of sketching algorithms

引用

BIOMETRIKA 2021年第2期108卷 283-297页

作者： Ahfock, D. C. Astle, W. J. Richardson, S. Univ Cambridge MRC Biostat Unit Robinson Way Cambridge CB2 0SR England

Sketching is a probabilistic data compression technique that has been largely developed by the computer science community. numerical operations on big datasets can be intolerably slow;sketching algorithms address this issue by generating a smaller surrogate dataset. Typically, inference proceeds on the compressed dataset. Sketching algorithms generally use random projections to compress the original dataset, and this stochastic generation process makes them amenable to statistical analysis. We argue that the sketched data can be modelled as a random sample, thus placing this family of data compression methods firmly within an inferential framework. In particular, we focus on the Gaussian, Hadamard and Clarkson-Woodruff sketches and their use in single-pass sketching algorithms for linear regression with huge samples. We explore the statistical properties of sketched regression algorithms and derive new distributional results for a large class of sketching estimators. A key result is a conditional central limit theorem for dataoblivious sketches. An important finding is that the best choice of sketching algorithm in terms of mean squared error is related to the signal-to-noise ratio in the source dataset. Finally, we demonstrate the theory and the limits of its applicability on two datasets.

关键词： Computational efficiency Random projection randomized numerical linear algebra Sketching

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：