期刊
PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA
卷 105, 期 36, 页码 13212-13217出版社
NATL ACAD SCIENCES
DOI: 10.1073/pnas.0804869105
关键词
-
资金
- Office of Naval Research [N00014-07-1-0711]
- Defense Advanced Research Projects Agency [FA9550-07-1-0541]
- National Geospatial Intelligence Agency [HM1582-06-1-2039]
We introduce a randomized algorithm for overdetermined linear least-squares regression. Given an arbitrary full-rank m x n matrix A with m >= n, any m x 1 vector b, and any positive real number 6, the procedure computes an n x 1 vector x such that x minimizes the Euclidean norm parallel to Ax - b parallel to to relative precision epsilon. The algorithm typically requires O((log(n) + log(1/epsilon))mn + n(3)) floating-point operations. This cost is less than the O(mn(2)) required by the classical schemes based on QR-decompositions or bidiagonalization. We present several numerical examples illustrating the performance of the algorithm.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据