.png){kind=icon}
返回
SUBSPACE ITERATION RANDOMIZATION AND SINGULAR VALUE PROBLEMS
.png){kind=icon}
OA
AI
DOI：10.1137/130938700.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
A classical problem in matrix computations is the efficient and reliable approximation of a given matrix by a matrix of lower rank. The truncated singular value decomposition (SVD) is known to provide the best such approximation for any given fixed rank. However, the SVD is also known to be very costly to compute. Among the different approaches in the literature for computing low-rank approximations, randomized algorithms have attracted researchers' attention recently due to their surprising reliability and computational efficiency in different application areas. Typically, such algorithms are shown to compute with very high probability low-rank approximations that are within a constant factor from optimal, and are known to perform even better in many practical situations. In this paper, we present a novel error analysis that considers randomized algorithms within the subspace iteration framework and show with very high probability that highly accurate low-rank approximations as well as singular values can indeed be computed quickly for matrices with rapidly decaying singular values. Such matrices appear frequently in diverse application areas such as data analysis, fast structured matrix computations, and fast direct methods for large sparse linear systems of equations and are the driving motivation for randomized methods. Furthermore, we show that the low-rank approximations computed by these randomized algorithms are actually rank-revealing approximations, and the special case of a rank-1 approximation can also be used to correctly estimate matrix 2-norms with very high probability. Our numerical experiments are in full support of our conclusions.
Keyword:
low-rank approximation
randomized algorithms
singular values
standard Gaussian matrix
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
2.6
论文数:
5.1K
被引数:
1.8W
机构
暂无机构信息
引用论文
An auto-calibration method for spatially and temporally correlated noncircular sources in unknown noise fields适用于时空相关非圆信号源在未知噪声场中的自动校准方法
PREAI
分享收藏Face recognition by humans: Nineteen results all computer vision researchers should know about.png)
PROCEEDINGS OF THE IEEE
PROCEEDINGS OF THE IEEEIF25.9
PREAI
分享收藏
分享收藏
查看更多内容