A NEW COMPLEXITY BOUND FOR THE LEAST-SQUARES PROBLEM

概要

論文の詳細を見る
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.
1996-03-06