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

Computing rank-revealing factorizations of matrices stored out-of-core

CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE 2023年第22期35卷

作者： Heavner, N. Martinsson, P. G. Quintana-Orti, G. Univ Colorado Boulder Dept Appl Math Boulder CO USA Univ Texas Austin Dept Math Austin TX USA Univ Jaume 1 Dept Ingn & Ciencia Comp Castellon de La Plana Spain

This paper describes efficient algorithms for computing rank-revealing factorizations of matrices that are too large to fit in main memory (RAM), and must instead be stored on slow external memory devices such as disks (out-of-core or out-of-memory). Traditional algorithms for computing rank-revealing factorizations (such as the column pivoted QR factorization and the singular value decomposition) are very communication intensive as they require many vector-vector and matrix-vector operations, which become prohibitively expensive when data is not in RAM. Randomization allows to reformulate new methods so that large contiguous blocks of the matrix are processed in bulk. The paper describes two distinct methods. The first is a blocked version of column pivoted Householder QR, organized as a "left-looking" method to minimize the number of the expensive write operations. The second method results employs a UTV factorization. It is organized as an algorithm-by-blocks to overlap computations and I/O operations. As it incorporates power iterations, it is much better at revealing the numerical rank. numerical experiments on several computers demonstrate that the new algorithms are almost as fast when processing data stored on slow memory devices as traditional algorithms are for data stored in RAM.

关键词： blocked matrix computations householder QR factorization HQRRP factorization out-of-core computation partial rank-revealing factorization randomized numerical linear algebra randUTV factorization rank-revealing factorization shared-memory multicore processors shared-memory multiprocessors

来源：评论

学校读者我要写书评

暂无评论

Efficient algorithms for computing rank-revealing factorizations on a GPU

引用

numerical linear algebra WITH APPLICATIONS 2023年第6期30卷

作者： Heavner, Nathan Chen, Chao Gopal, Abinand Martinsson, Per-Gunnar Univ Colorado Boulder Dept Appl Math Boulder CO USA Univ Texas Austin Oden Inst Austin TX 78712 USA Yale Univ Dept Math New Haven CT USA Univ Texas Austin Dept Math Austin TX USA

Standard rank-revealing factorizations such as the singular value decomposition (SVD) and column pivoted QR factorization are challenging to implement efficiently on a GPU. A major difficulty in this regard is the inability of standard algorithms to cast most operations in terms of the Level-3 BLAS. This article presents two alternative algorithms for computing a rank-revealing factorization of the form A = UTV*, where U and V are orthogonal and T is trapezoidal (or triangular if A is square). Both algorithms use randomized projection techniques to cast most of the flops in terms of matrix-matrix multiplication, which is exceptionally efficient on the GPU. numerical experiments illustrate that these algorithms achieve significant acceleration over finely tuned GPU implementations of the SVD while providing low rank approximation errors close to that of the SVD.

关键词： parallel algorithm for GPU randomized numerical linear algebra rank-revealing matrix factorization

来源：评论

学校读者我要写书评

暂无评论

APPROXIMATE WEIGHTED CR CODED MATRIX MULTIPLICATION

APPROXIMATE WEIGHTED <i>CR</i> CODED MATRIX MULTIPLICATION

引用

IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)

作者： Charalambides, Neophytos Pilanci, Mert Hero, Alfred O., III Univ Michigan EECS Dept Ann Arbor MI 48109 USA Stanford Univ EE Dept Stanford CA 94305 USA

ISBN: (纸本)9781728176055

One of the most common operations in signal processing is matrix multiplication. However, it presents a major computational bottleneck when the matrix dimension is high, as can occur for large data size or feature dimension. Two different approaches to overcoming this bottleneck are: 1) low rank approximation of the matrix product;and 2) distributed computation. We propose a scheme that combines these two approaches. To enable distributed low rank approximation, we generalize the approximate matrix CR-multiplication to accommodate weighted block sampling, and we introduce a weighted coded matrix multiplication method. This results in novel approximate weighted CR coded matrix multiplication schemes, which achieve improved performance for distributed matrix multiplication and are robust to stragglers.

关键词： randomized numerical linear algebra approximation algorithms coded computing coding theory

来源：评论

学校读者我要写书评

暂无评论

LSAR: efficient leverage score sampling algorithm for the analysis of big time series data

The Journal of Machine Learning Research

引用

The Journal of Machine Learning Research 2022年第1期23卷 986-1021页

作者： Ali Eshragh Fred Roosta Asef Nazari Michael W. Mahoney School of Information and Physical Sciences University of Newcastle Australia and International Computer Science Institute Berkeley CA School of Mathematics and Physics University of Queensland Australia and International Computer Science Institute Berkeley CA School of Information Technology Deakin University Australia Department of Statistics University of California at Berkeley and International Computer Science Institute Berkeley CA

We apply methods from randomized numerical linear algebra (RandNLA) to develop improved algorithms for the analysis of large-scale time series data. We first develop a new fast algorithm to estimate the leverage scores of an autoregressive (AR) model in big data regimes. We show that the accuracy of approximations lies within (1 + O(ε)) of the true leverage scores with high probability. These theoretical results are subsequently exploited to develop an efficient algorithm, called LSAR, for fitting an appropriate AR model to big time series data. Our proposed algorithm is guaranteed, with high probability, to find the maximum likelihood estimates of the parameters of the underlying true AR model and has a worst case running time that significantly improves those of the state-of-the-art alternatives in big data regimes. Empirical results on large-scale synthetic as well as real data highly support the theoretical results and reveal the efficacy of this new approach.

关键词： autoregressive model maximum likelihood estimation big data regime randomized numerical linear algebra sampling

来源：评论

学校读者我要写书评

暂无评论

Newton-type methods for non-convex optimization under inexact Hessian information

引用

MATHEMATICAL PROGRAMMING 2020年第1-2期184卷 35-70页

作者： Xu, Peng Roosta, Fred Mahoney, Michael W. Stanford Univ Inst Computat & Math Engn Stanford CA 94305 USA Univ Queensland Sch Math & Phys Brisbane Qld Australia Int Comp Sci Inst Berkeley CA 94704 USA Univ Calif Berkeley Dept Stat Berkeley CA 94720 USA

We consider variants of trust-region and adaptive cubic regularization methods for non-convex optimization, in which the Hessian matrix is approximated. Under certain condition on the inexact Hessian, and using approximate solution of the corresponding sub-problems, we provide iteration complexity to achieve epsilon-approximate second-order optimality which have been shown to be tight. Our Hessian approximation condition offers a range of advantages as compared with the prior works and allows for direct construction of the approximate Hessian with a priori guarantees through various techniques, including randomized sampling methods. In this light, we consider the canonical problem of finite-sum minimization, provide appropriate uniform and non-uniform sub-sampling strategies to construct such Hessian approximations, and obtain optimal iteration complexity for the corresponding sub-sampled trust-region and adaptive cubic regularization methods.

关键词： Non-convex optimization Inexact Hessian Trust region Cubic regularization randomized numerical linear algebra

来源：评论

学校读者我要写书评

暂无评论

Efficient Low-Rank Approximation of Matrices Based on randomized Pivoted Decomposition

引用

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2020年 68卷 3575-3589页

作者： Kaloorazi, Maboud F. Chen, Jie Northwestern Polytech Univ Ctr Intelligent Acoust & Immers Commun Sch Marine Sci & Technol Xian 710072 Peoples R China Minist Ind & Informat Technol Key Lab Ocean Acoust & Sensing Xian 710072 Peoples R China

Given a matrix A with numerical rank k, the twosided orthogonal decomposition (TSOD) computes a factorization A = UDVT, where U and V are orthogonal, and D is (upper/lower) triangular. TSOD is rank-revealing as the middle factor D reveals the rank of A. The computation of TSOD, however, is demanding. In this paper, we present an algorithm called randomized pivoted TSOD (RP-TSOD), where the middle factor is lower triangular. Key in our work is the exploitation of randomization, and RP-TSOD is primarily devised to efficiently construct an approximation to a low-rank matrix. We provide three different types of bounds for RP-TSOD: (i) we furnish upper bounds on the error of the low-rank approximation, (ii) we bound the k approximate principal singular values, and (iii) we derive bounds for the canonical angles between the approximate and the exact singular subspaces. Our bounds describe the characteristics and behavior of our proposed algorithm. Through numerical tests, we showthe effectiveness of the devised bounds as well as our proposed algorithm.

关键词： Matrix decomposition low-rank approximation rank-revealing factorization dimension reduction randomized numerical linear algebra image recovery

来源：评论

学校读者我要写书评

暂无评论

RCHOL: randomized CHOLESKY FACTORIZATION FOR SOLVING SDD linear SYSTEMS

引用

SIAM JOURNAL ON SCIENTIFIC COMPUTING 2021年第6期43卷 C411-C438页

作者： Chen, Chao Liang, Tianyu Biros, George Univ Texas Austin Austin TX 78705 USA

We introduce a randomized algorithm, namely, rchol, to construct an approximate Cholesky factorization for a given Laplacian matrix (a.k.a., graph Laplacian). From a graph perspective, the exact Cholesky factorization introduces a clique in the underlying graph after eliminating a row/column. By randomization, rchol only retains a sparse subset of the edges in the clique using a random sampling developed by Spielman and Kyng [private communication, 2020]. We prove rchol is breakdown free and apply it to solving large sparse linear systems with symmetric diagonally dominant matrices. In addition, we parallelize rchol based on the nested-dissection ordering for shared-memory machines. We report numerical experiments that demonstrate the robustness and the scalability of rchol. For example, our parallel code scaled up to 64 threads on a single node for solving the three-dimensional Poisson equation, discretized with the 7-point stencil on a 1024 x 1024 x 1024 grid, a problem that has one billion unknowns.

关键词： randomized numerical linear algebra incomplete Cholesky factorization sparse matrix symmetric diagonally dominant matrix graph Laplacian random sampling

来源：评论

学校读者我要写书评

暂无评论

Robust and Sample Optimal Algorithms for PSD Low Rank Approximation 61

Robust and Sample Optimal Algorithms for PSD Low Rank Approx...

引用

61st IEEE Annual Symposium on Foundations of Computer Science (FOCS)

作者： Bakshi, Ainesh Chepurko, Nadiia Woodruff, David P. CMU Pittsburgh PA 15213 USA MIT 77 Massachusetts Ave Cambridge MA 02139 USA

ISBN: (纸本)9781728196213

Recently, Musco and Woodruff (FOCS, 2017) showed that given an nxn positive semidefinite (PSD) matrix A, it is possible to compute a (1 + epsilon)-approximate relative-error low-rank approximation to A by querying (O) over tilde (nk/epsilon(2.5)) entries of A in time (O) over tilde (nk/epsilon(2.5) + nk(omega-1)/epsilon(2(omega-1))). They also showed that any relative-error low-rank approximation algorithm must query Omega(nk/epsilon) entries of A, this gap has since remained open. Our main result is to resolve this question by obtaining an optimal algorithm that queries (O) over tilde (nk/epsilon) entries of A and outputs a relative-error low-rank approximation in (O) over tilde (n . (k/epsilon)(omega- 1)) time. Note, our running time improves that of Musco and Woodruff, and matches the information-theoretic lower bound if the matrix-multiplication exponent omega is 2. We then extend our techniques to negative-type distance matrices. Here, our input is a pair-wise distance matrix A corresponding to a point set P = {x(1), x(2), ..., x(n)} such that A(i, j) = parallel to x(i) - x(j)parallel to(2)(2). Bakshi and Woodruff (NeurIPS, 2018) showed a bi-criteria, relative-error low-rank approximation for negative-type metrics. Their algorithm queries (O) over tilde (nk/epsilon(2.5)) entries and outputs a rank-(k + 4) matrix. We show that the bi-criteria guarantee is not necessary and obtain an (O) over tilde (nk/epsilon) query algorithm, which is optimal. Our algorithm applies to all distance matrices that arise from metrics satisfying negative-type inequalities, including l(1), l(2), spherical metrics, hypermetrics and effective resistances on a graph. We also obtain faster algorithms for ridge regression. Next, we introduce a new robust low-rank approximation model which captures PSD matrices that have been corrupted with noise. We assume that the Frobenius norm of the corruption is bounded. Here, we relax the notion of approximation to additive-error, since it is inform

关键词： low rank approximation psd matrices regression sublinear algorithms randomized numerical linear algebra

来源：评论

学校读者我要写书评

暂无评论

LOW-RANK APPROXIMATION OF MATRICES VIA A RANK-REVEALING FACTORIZATION WITH RANDOMIZATION

LOW-RANK APPROXIMATION OF MATRICES VIA A RANK-REVEALING FACT...

引用

IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP)

作者： Kaloorazi, Maboud Farzaneh Chen, Jie Northwestern Polytech Univ Sch Marine Sci & Technol Ctr Intelligent Acoust & Immers Commun CIAIC Xian Shaanxi Peoples R China

ISBN: (纸本)9781509066315

Given a matrix A with numerical rank k, the two-sided orthogonal decomposition (TSOD) computes a factorization A = UDVT, where U and V are unitary, and D is (upper/lower) triangular. TSOD is rank-revealing as the middle factor D reveals the rank of A. The computation of TSOD, however, is demanding, especially when a low-rank representation of the input matrix is desired. To treat such a case efficiently, in this paper we present an algorithm called randomized pivoted TSOD (RP-TSOD) that constructs a highly accurate approximation to the TSOD decomposition. Key in our work is the exploitation of randomization, and we furnish (i) upper bounds on the error of the low-rank approximation, and (ii) bounds for the canonical angles between the approximate and the exact singular subspaces, which take into account the randomness. Our bounds describe the characteristics and behavior of our proposed algorithm. We validate the effectiveness of our proposed algorithm and devised bounds with synthetic data as well as real data of image reconstruction problem.

关键词： low-rank approximation randomized numerical linear algebra rank-revealing factorization image recovery

来源：评论

学校读者我要写书评

暂无评论

Subspace learning by randomized sketching

Subspace learning by randomized sketching

引用

作者： Rakshith Sharma Srinivasa Georgia Institute of Technology

学位级别：博士

High dimensional data is often accompanied by inherent low dimensionality that can be leveraged to design scalable machine learning and signal processing algorithms. Developing efficient computational frameworks that take advantage of the underlying structure in the data is crucial. In this thesis, we consider a particular form of inherent low dimensionality in data: subspace models. In many applications, data is known to lie close to a low dimensional subspace. The underlying subspace itself may or may not be known a priori. Incorporating this structure into data acquisition systems and algorithms can aid in scalability. We first consider two specific applications in the field of array signal processing where subspace priors on the data are commonly used. For both these applications, we develop algorithms that require a number of measurements that scale with only the dimension of the underlying subspace. In doing so, we show that arrays demand dimensionality reduction maps that can operate on individual subsets or blocks of data at a time, without having access to other blocks. Inspired by such block constraints, we consider more general problems in numerical linear algebra where data has a natural partition into blocks. This is common in applications with distributed or decentralized data. We study the problems of sketched ridge regression and sketched matrix multiplication under this constraint and give sample optimal theoretical guarantees on block diagonal sketching matrices. Extending the block model to low-rank matrix sensing, we then study the problem of recovering a low-rank matrix from compressed observations of each column. While each column itself is compressed to a point that is beyond recovery, we leverage their joint structure to recover the matrix as a whole. To do so, we establish a new framework to design estimators of low-rank matrices that obey the constraints imposed by different observation models. Finally, we extend our framework of designing

关键词： Subspace learning randomized numerical linear algebra array processing sketching

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：