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

randomized matrix approximation to enhance regularized projection schemes in inverse problems

INVERSE PROBLEMS 2020年第8期36卷

作者： Lu, Shuai Mathe, Peter Pereverzev, Sergei, V Fudan Univ Key Lab Math Nonlinear Sci Shanghai Key Lab Contemporary Appl Math Shanghai 200433 Peoples R China Fudan Univ Sch Math Sci Shanghai 200433 Peoples R China Weierstrass Inst Appl Anal & Stochast Mohrenstr 39 D-10117 Berlin Germany Johann Radon Inst Altenberger Str 69 A-4040 Linz Austria

The authors consider a randomized solution to ill-posed operator equations in Hilbert spaces. In contrast to statistical inverse problems, where randomness appears in the noise, here randomness arises in the low-rank matrix approximation of the forward operator, which results in using a Monte Carlo method to solve the inverse problems. In particular, this approach follows the paradigm of the study N. Halkoet al2011SIAM Rev.53217-288, and hence regularization is performed based on the low-rank matrix approximation. Error bounds for the mean error are obtained which take into account solution smoothness and the inherent noise level. Based on the structure of the error decomposition the authors propose a novel algorithm which guarantees (on the mean) a prescribed error tolerance. Numerical simulations confirm the theoretical findings.

关键词： randomized matrix approximation inverse problems general regularization schemes source conditions

来源：评论

学校读者我要写书评

暂无评论

Far-field compression for fast kernel summation methods in high dimensions

引用

APPLIED AND COMPUTATIONAL HARMONIC ANALYSIS 2017年第1期43卷 39-75页

作者： March, William B. Biros, George Univ Texas Austin Inst Computat Engn & Sci Austin TX 78712 USA

We consider fast kernel summations in high dimensions: given a large set of points in d dimensions (with d >> 3) and a pair-potential function (the kernel function), we compute a weighted sum of all pairwise kernel interactions for each point in the set. Direct summation is equivalent to a (dense) matrix vector multiplication and scales quadratically with the number of points. Fast kernel summation algorithms reduce this cost to log-linear or linear complexity. Treecodes and Fast Multipole Methods (FMMs) deliver tremendous speedups by constructing approximate representations of interactions of points that are far from each other. In algebraic terms, these representations correspond to low-rank approximations of blocks of the overall interaction matrix. Existing approaches require an excessive number of kernel evaluations with increasing d and number of points in the dataset. To address this issue, we use a randomized algebraic approach in which we first sample the rows of a block and then construct its approximate, low rank interpolative decomposition. We examine the feasibility of this approach theoretically and experimentally. We provide a new theoretical result showing a tighter bound on the reconstruction error from uniformly sampling rows than the existing state-of-the-art. We demonstrate that our sampling approach is competitive with existing (but prohibitively expensive) methods from the literature. We also construct kernel matrices for the Laplacian, Gaussian, and polynomial kernels all commonly used in physics and data analysis. We explore the numerical properties of blocks of these matrices, and show that they are amenable to our approach. Depending on the data set, our randomized algorithm can successfully compute low rank approximations in high dimensions. We report results for data sets with ambient dimensions from four to 1,000. (C) 2015 Elsevier Inc. All rights reserved.

关键词： Kernel independent fast multipole methods Fast summation randomized matrix approximation Interpolative decomposition matrix sampling

来源：评论

学校读者我要写书评

暂无评论

Joint Massive MIMO CSI Estimation and Feedback via randomized Low-Rank approximation

引用

IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY 2022年第7期71卷 7979-7984页

作者： Wei, Ziping Liu, Hongfu Li, Bin Zhao, Chenglin BUPT SICE Beijing 100876 Peoples R China

The acquisitionof channel state information at transmitter (CSIT) is crucial to attain the potential benefits of the frequency division duplexing (FDD) massive multiple-input multiple-output (MIMO) system. Traditionally, CSI estimation at receiver and feedback to transmitter are separately designed, failing to maximize the estimation accuracy while minimizing the complexity/overhead. In this work, we propose a novel computation and communication efficient CSIT acquisition scheme, by jointly designing downlink CSI estimation and uplink feedback, which is inspired by randomized matrix approximation techniques. In the process of CSI estimation, we represent a large channel matrix with three sub-matrices by exploiting its inherent low-rank characteristic, and then estimate these small matrices separately. Our new estimator significantly reduces the computation complexity in massive MIMO CSI acquisition, whilst attaining the high accuracy. The convergence as well as the error bound of our CSI estimator is derived theoretically. In the following CSI feedback process, only partial elements of sub-matrices are reported to transmitter without further compression, and finally the full CSI is recovered accurately. This novel CSI feedback scheme, relying on the estimated CSI with special structure, greatly reduces both the communication overhead. Numerical simulations are provided to valid our joint CSI estimation and feedback scheme, which would have great potential in massive MIMO communications.

关键词： Estimation Massive MIMO Channel estimation matrix decomposition Downlink Convergence Uplink CSIT acquisition FDD massive MIMO system randomized matrix approximation low-rank

来源：评论

学校读者我要写书评

暂无评论

randomized Approximate Channel Estimator in Massive-MIMO Communication

引用

IEEE COMMUNICATIONS LETTERS 2020年第10期24卷 2314-2318页

作者： Li, Bin Wang, Shuseng Zhang, Jun Cao, Xianbin Zhao, Chenglin Beijing Univ Posts & Telecommun Sch Informat & Commun Engn Beijing 100876 Peoples R China Beijing Inst Technol Sch Informat & Elect Beijing 100081 Peoples R China Stevens Inst Technol Dept Comp Sci Hoboken NJ 07030 USA Nanjing Univ Posts & Telecommun Jiangsu Key Lab Wireless Commun Nanjing 210003 Peoples R China Beihang Univ Sch Elect & Informat Engn Beijing 100191 Peoples R China

Massive MIMO is considered as one key enabling technology in 5G communications. Although the high-quality channel state information (CSI) estimation is essential to improve the energy/spectrum efficiency of massive MIMO systems, the optimal MMSE estimator unfortunately creates one major challenge, due to its formidable computation complexity. In this letter, we propose a rank-restrained low-complexity MMSE channel estimator for massive MIMO communications, leveraging a novel concept of randomized low-rank approximation. To accomplish this, we first design a two-stage pilot training scheme. Rather than directly estimating the large channel matrix as usual, we then acquire two low-dimensional subsets of it, which respectively gives the row and column sampling version of unknown channel matrix. Finally, we reconstruct the complete channel matrix via such two estimated low-dimensional sketches, by exploiting the low-rank structure of channel. As demonstrated, our scheme significantly reduces the time complexity as well as the energy consumption in CSI acquisition, which yet attains the near-optimal estimation accuracy. It thus provides great promises to the practical deployment of massive MIMO communications.

关键词： Channel estimation Massive MIMO Antennas Training Estimation matrix decomposition Time complexity Massive MIMO channel estimation low-rank randomized matrix approximation low complexity low power

来源：评论

学校读者我要写书评

暂无评论

randomized Low-Rank approximation Based Massive MIMO CSI Compression

引用

IEEE COMMUNICATIONS LETTERS 2021年第6期25卷 2004-2008页

作者： Wei, Ziping Li, Haozhan Liu, Hongfu Li, Bin Zhao, Chenglin Beijing Univ Posts & Telecommun BUPT Sch Informat & Commun Engn SICE Beijing 100876 Peoples R China

Massive multiple-input multiple-output (MIMO) is regarded as one enabling technique to improve channel capacity and energy/spectrum efficiency of 5G communications. To attain such potential benefits, accurate channel information is critical to the transmitter, which yet remains a challenging task for frequency division duplexing (FDD) systems, i.e., the channel state information (CSI) feedback tends to be resource-demanding especially for massive MIMO communications. In this work, we propose a novel CSI feedback method with low complexity and high precision, which is inspired by randomized matrix approximation. Our approach exploits the inherent low-rank characteristic of a large channel matrix, and approximates it by small sub-matrices which are then reported to transmitter to recover a CSI matrix. Theoretical bounds of the recovered CSI in both error-free and error cases are derived. Simulation results demonstrate our method could recover CSI accurately via an extremely low complexity and yet achieve a largely reduced compression ratio (or feedback overhead), compared to other schemes. It thus has the great potential in the emerging massive MIMO FDD communications.

关键词： Massive MIMO channel state information (CSI) feedback randomized matrix approximation low rank

来源：评论

学校读者我要写书评

暂无评论

Generalized matrix Local Low Rank Representation by Random Projection and Submatrix Propagation 23

Generalized Matrix Local Low Rank Representation by Random P...

引用

29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD)

作者： Dang, Pengtao Zhu, Haiqi Guo, Tingbo Wan, Changlin Zhao, Tong Salama, Paul Wang, Yijie Cao, Sha Zhang, Chi Purdue Univ Indianapolis IN 46202 USA Indiana Univ Bloomington IN USA Indiana Univ Sch Med Indianapolis IN 46202 USA Purdue Univ W Lafayette IN USA Uber Inc Seattle WA USA

ISBN: (纸本)9798400701030

matrix low rank approximation is an effective method to reduce or eliminate the statistical redundancy of its components. Compared with the traditional global low rank methods such as singular value decomposition (SVD), local low rank approximation methods are more advantageous to uncover interpretable data structures when clear duality exists between the rows and columns of the matrix. Local low rank approximation is equivalent to low rank submatrix detection. Unfortunately, existing local low rank approximation methods can detect only submatrices of specific mean structure, which may miss a substantial amount of true and interesting patterns. In this work, we develop a novel matrix computational framework called RPSP (Random Probing based submatrix Propagation)(1) that provides an effective solution for the general matrix local low rank representation problem. RPSP detects local low rank patterns that grow from small submatrices of low rank property, which are determined by a random projection approach. RPSP is supported by theories of random projection. Experiments on synthetic data demonstrate that RPSP outperforms all state-of-the-art methods, with the capacity to robustly and correctly identify the low rank matrices when the pattern has a similar mean as the background, background noise is heteroscedastic and multiple patterns present in the data. On real-world datasets, RPSP also demonstrates its effectiveness in identifying interpretable local low rank matrices.

关键词： Local low rank matrix Sub-matrix detection Representation learning randomized matrix approximation Random projection

来源：评论

学校读者我要写书评

暂无评论

Approximating Element-Wise Functions of matrix with Improved Streaming randomized SVD 34

Approximating Element-Wise Functions of Matrix with Improved...

引用

34th IEEE International Conference on Tools with Artificial Intelligence (ICTAI)

作者： Xie, Yuyang Feng, Xu Zhang, Xizhi Qiu, Jiezhong Yu, Wenjian Tsinghua Univ BNRist Dept Comp Sci & Tech Beijing Peoples R China

ISBN: (纸本)9798350397444

The element-wise functions of a matrix are widely used in machine learning. For the applications with large matrices, efficiently computing the matrix-vector multiplication of matrix element-wise function without explicitly constructed matrix is very desired. In this work, we aim to develop an efficient low-rank approximation of the element-wise function of matrix with the time/memory cost linear to the matrix dimension. We first propose a sparse-sign streaming randomized SVD (ssrSVD) algorithm based on a streaming singular value decomposition (SVD) algorithm and the sparse-sign random projection for the approximation of element-wise function of general asymmetric matrix. For symmetric positive semi-definite (SPSD) matrix, for which the existing Nystrom [1] and FastSPSD [2] method do not perform well if the matrix's singular value decays slowly, we propose a theoretically proved shift skill to improve the approximation accuracy. Combining with the ssrSVD, we obtain the sparse-sign streaming SPSD matrix approximation with shift (S3SPSD) algorithm. Experiments are carried out to evaluate the proposed algorithms' performance in approximating element-wise functions of matrix. With the color transfer task based on the Sinkhorn algorithm, the ssrSVD algorithm largely reduces the approximation error (up to 10(5)x) compared with the state-of-the-art baselines, and results in high-quality color transfer result. For the kernel matrix approximation, the proposed S3SPSD algorithm also consistently outperforms the state-of-the-art baselines. Experimental results finally validate the linear time complexity of the proposed algorithms.

关键词： element-wise function of matrix randomized matrix approximation sparse-sign random projection streaming algorithm shift skill

来源：评论

学校读者我要写书评

暂无评论

ASKIT: AN EFFICIENT, PARALLEL LIBRARY FOR HIGH-DIMENSIONAL KERNEL SUMMATIONS

引用

SIAM JOURNAL ON SCIENTIFIC COMPUTING 2016年第5期38卷 S720-S749页

作者： March, William B. Xiao, Bo Yu, Chenhan D. Biros, George Univ Texas Austin Inst Computat Engn & Sci Austin TX 78712 USA Univ Texas Austin Sch Comp Sci Austin TX 78712 USA

Kernel-based methods are a powerful tool in a variety of machine learning and computational statistics methods. A key bottleneck in these methods is computations involving the kernel matrix, which scales quadratically with the problem size. Previously, we introduced ASKIT (Approximate Skeletonization Kernel Independent Treecode), an efficient, scalable, kernel-independent method for approximately evaluating kernel matrix-vector products. ASKIT is based on a novel, randomized method for efficiently factoring off-diagonal blocks of the kernel matrix using approximate nearest neighbor information. In this context, ASKIT can be viewed as an algebraic fast multipole method for arbitrary dimensions. In this paper, we introduce our open-source implementation of ASKIT. Features of our ASKIT library include linear dependence on the input dimension of the data, the ability to approximate kernel functions with no prior information on the kernel, and scalability to tens of thousands of compute cores and data with billions of points or hundreds of dimensions. We also introduce some new extensions and improvements of ASKIT, included in our library. We introduce a new method for adaptively selecting approximation ranks and correctly partition the nearest neighbor information, both of which improve the performance of ASKIT over our previous implementation. We describe the ASKIT algorithm in detail, and collect and summarize our previous theoretical complexity and error bounds in one place. We present a brief selection of experimental results illustrating the accuracy and scalability of ASKIT. We then provide some details and guidance for users of ASKIT.

关键词： N-body methods treecodes machine learning kernel machines linear algebra randomized matrix approximation

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：