Document Type

Technical Report

Publication Date

2010

Subjects

Least squares -- Data processing, Least squares -- Algorithms, Computational complexity

Abstract

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.

Description

Portland State University Computer Science Department Technical Report #10-01, 2010.

Persistent Identifier

https://archives.pdx.edu/ds/psu/30750

Download

Share

COinS