A Column Generation Approach for ...

A Column Generation Approach for Piecewise Affine Model Fitting

Luigi Malag˛
DEI PhD Student

DEI - Aula 2A
16 novembre 2011
Ore 11.30


In this work we consider the general problem of Piecewise Affine Model Fitting (PAMF). Given a set points in (R^{n},R) and a positive integer k, PAMF consists in partitioning the domain R^{n} into at most k linearly separable regions and in determining for each region an affine hyperplane f_i(x) : R^{n} \to R, i \in 1, ..., k, so as to best approximate the given points. The classical approach to PAMF proceeds in two steps: first the domain is partitioned and then the hyperplanes are estimated by minimizing the distances of the points in each region from the corresponding hyperplane. In this work, we propose a novel approach to PAMF based on column generation, where both partitioning of the domain and model fitting are solved at the same time. Preliminary results are encouraging, both in terms of total computing time and solution quality.

Area di ricerca:
Intelligenza artificiale, robotica e computer vision