|
|
|
Professor:
Prof. Martin H. Gutknecht
Date: 20.10.2007
Project Title:
Efficient Algorithms for Large Linear Additive Models
Summary:
We consider the penalized least squares solution
of an overdetermined linear system of size N x m whose matrix is
structured into d block columns (of roughly the same width),
which may be imposed by the underlying application or by the need to
distribute the system on a parallel computer.
We are interested in applications in data mining where the system is huge
and where data access and communication time limit the choice of
algorithms in the necessarily parallel environment.
In data mining and statistical applications one is particularly interested
in the predicted values y := A x = b - r .
It is easy to derive a structured linear system for these predicted values.
Statisticians often solve this system with the block Gauss-Seidel algorithm
and call this backfitting.
We compare backfitting with a number of other options that offer themselves
for the solution of the problem.