• 163qb > wwwelseviercom/locate/acha
  • wwwelseviercom/locate/acha

    免费下载 下载该文档 文档格式:PDF   更新时间:2008-12-02   下载次数:0   点击次数:1
    文档基本属性
    文档语言:Traditional Chinese
    文档格式:pdf
    文档作者:MayMay
    关键词:
    主题:
    备注:
    点击这里显示更多文档属性
    Appl. Comput. Harmon. Anal. 25 (2008) 335–366 www.elsevier.com/locate/acha
    A fast randomized algorithm for the approximation of matrices
    Franco Woolfe, Edo Liberty, Vladimir Rokhlin, Mark Tygert
    Program in Applied Mathematics, Yale University, A.K. Watson Hall, 51 Prospect St., New Haven, CT 06511, USA Received 21 August 2007; accepted 6 December 2007 Available online 23 December 2007 Communicated by Naoki Saito
    Abstract We introduce a randomized procedure that, given an m × n matrix A and a positive integer k, approximates A with a matrix Z of rank k. The algorithm relies on applying a structured l × m random matrix R to each column of A, where l is an integer near to, but greater than, k. The structure of R allows us to apply it to an arbitrary m × 1 vector at a cost proportional to m log(l); the resulting procedure can construct a rank-k approximation Z from the entries of A at a cost proportional to mn log(k) + l 2 (m + n). We prove several bounds on the accuracy of the algorithm; one such bound guarantees that the spectral norm A Z of the discrepancy √ between A and Z is of the same order as max{m, n} times the (k + 1)st greatest singular value σk+1 of A, with small probability of large deviations. In contrast, the classical pivoted "QR" decomposition algorithms (such as Gram–Schmidt or Householder) require at least kmn oating-point operations in order to compute a similarly accurate rank-k approximation. In practice, the algorithm of this paper runs faster than the classical algorithms, even when k is quite small or large. Furthermore, the algorithm operates reliably independently of the structure of the matrix A, can access each column of A independently and at most twice, and parallelizes naturally. Thus, the algorithm provides an efcient, reliable means for computing several of the greatest singular values and corresponding singular vectors of A. The results are illustrated via several numerical examples. 2007 Elsevier Inc. All rights reserved.

    下一页

  • 下载地址 (推荐使用迅雷下载地址,速度快,支持断点续传)
  • 免费下载 PDF格式下载
  • 您可能感兴趣的
  • 163qb充值  cnc.163qb  if.163qb.com充值  cnc.163qb.com充值  httpcnc.163qb.cnm  搜索http;www.163qb  lf.163qb  if.163qb  cnc.163qb.cpm