WEKO3
アイテム
A NEW COMPLEXITY BOUND FOR THE LEAST-SQUARES PROBLEM
https://ipsj.ixsq.nii.ac.jp/records/129006
https://ipsj.ixsq.nii.ac.jp/records/129006eac5cb79-c4e9-47f3-9492-c6f40db2da67
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
KJ00001329213.pdf (104.1 kB)
|
|
| Item type | National Convention(1) | |||||
|---|---|---|---|---|---|---|
| 公開日 | 1996-03-06 | |||||
| タイトル | ||||||
| 言語 | en | |||||
| タイトル | A NEW COMPLEXITY BOUND FOR THE LEAST-SQUARES PROBLEM | |||||
| 言語 | ||||||
| 言語 | eng | |||||
| 資源タイプ | ||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_5794 | |||||
| 資源タイプ | conference paper | |||||
| 著者所属(英) | ||||||
| en | ||||||
| Department of lnformation Systems Engineering, Aomori University | ||||||
| 論文抄録(英) | ||||||
| 内容記述タイプ | Other | |||||
| 内容記述 | Let(x_i, y_i), i=1～n, be measured data of n pairs, where x_i≠x_j, if i≠j. We consider the following least-squares problem with the polynomial regression of degree m, ∥y-f(x)∥_2=min(1)where y=(y_1, y_2, …, y_n)^T, f(x)=(f(x_1), f(x_2), …, f(x_n))^T, f(x_i)=a_0+a_1x_i+…+a_mx^m_i, i=1～n, m+1≤ n. Solving (1) by using some traditional methods, such as Householder transformation or QR decomposition etc., requires O(n^2m) arithmetic operations. In [7], we have showed a fast algorithm which needs only O(nm) arithmetic operations. This paper further proves that the arithmetic complexity of the least-squares problem (1) does not exceed O(nlog^2_2m) ; this result generalizes the complexity results showed by H. T. Kung for the fast polynomial interpolation [5], D. Bini and V. Pan [2], J. F. Canny, E. Kaltofen and Y. Lakshman [4] for the solution of the Vander-monde linear system. | |||||
| 書誌レコードID | ||||||
| 収録物識別子タイプ | NCID | |||||
| 収録物識別子 | AN00349328 | |||||
| 書誌情報 |
全国大会講演論文集 巻 第52回, 号 基礎理論と基礎技術, p. 1-2, 発行日 1996-03-06 |
|||||
| 出版者 | ||||||
| 言語 | ja | |||||
| 出版者 | 情報処理学会 | |||||
