Portland State University. Department of Computer Science
Least squares -- Data processing, Least squares -- Algorithms, Computational complexity
I present a new divide-and-conquer algorithm for solving continuous linear least-squares problems. The method is applicable when the column space of the linear system relating data to model parameters is “translation invariant”. The central operation is a matrix- vector product, which makes the method very easy to implement. Secondly, the structure of the computation suggests a straightforward parallel implementation.
A complexity analysis for sequential implementation shows that the method has the same asymptotic complexity as well-known algorithms for discrete linear least-squares. For illustration we work out the details for the problem of fitting quadratic bivariate polyno- mials to a piecewise constant function.
Juengling, Ralf, "Solving Continuous Linear Least-Squares Problems by Iterated Projection" (2010). Computer Science Faculty Publications and Presentations. 216.