The MIN PFS problem and piecewise linear model estimation.

*(English)*Zbl 0995.90076Summary: We consider a new combinatorial optimization problem related to linear systems (MIN PFS) that consists, given an infeasible system, in finding a partition into a minimum number of feasible subsystems. MIN PFS allows formalization of the fundamental problem of piecewise linear model estimation, which is an attractive alternative when modeling a wide range of nonlinear phenomena. Since MIN PFS turns out to be NP-hard to approximate within every factor strictly smaller than 3/2 and we are mainly interested in real-time applications, we propose a greedy strategy based on randomized and thermal variants of the classical Agmon-Motzkin-Schoenberg relaxation method for solving systems of linear inequalities. Our method provides good approximate solutions in a short amount of time. The potential of our approach and the performance of our algorithm are demonstrated on two challenging problems from image and signal processing. The first one is that of detecting line segments in digital images and the second one that of modeling time-series using piecewise linear autoregressive models. In both cases the MIN PFS-based approach presents various advantages with respect to conventional alternatives, including wider range of applicability, lower computational requirements and no need for a priori assumptions regarding the underlying structure of the data.

##### MSC:

90C27 | Combinatorial optimization |

##### Keywords:

infeasible linear systems; feasible subsystems; minimum partition; relaxation methods; piecewise linear model estimation; combinatorial optimization##### Software:

Houghtool##### References:

[1] | Aarts, E.; Korst, J., Simulated annealing and boltzmannn machines, (1989), Wiley and Sons New York |

[2] | Agmon, S., The relaxation method for linear inequalities, Canadian J. math., 6, 382-392, (1954) · Zbl 0055.35001 |

[3] | E. Amaldi, From finding maximum feasible subsystems of linear systems to feedforward neural network design, Ph.D. Thesis No. 1272, Department of Mathematics, Swiss Federal Institute of Technology, Lausanne, 1994. |

[4] | E. Amaldi, R. Hauser, Randomized relaxation methods for the maximum feasible subsystem problem, Technical Report, N. 2001-90, DEI, Politecnico di Milano, Italy, 2001. · Zbl 1119.65327 |

[5] | Amaldi, E.; Kann, V., The complexity and approximability of finding maximum feasible subsystems of linear relations, Theoret. comput. sci., 147, 1-2, 181-210, (1995) · Zbl 0884.68093 |

[6] | E. Amaldi, M. Mattavelli, A combinatorial optimization approach to extract piecewise linear structure from non-linear data and an application to optical flow segmentation, Technical Report 97-12, Cornell Computational Optimization project, Cornell University, Ithaca NY, 1997. |

[7] | Amaldi, E.; Pfetsch, M.; Trotter, L., Some structural and algorithmic properties of the maximum feasible subsystem problem, (), 45-59 · Zbl 0978.90067 |

[8] | Argyris, J.; Faust, G.; Haase, M., An exploration of chaos, (1994), North-Holland Amsterdam |

[9] | Blumer, A.; Ehrenfeucht, A.; Haussler, D.; Warmuth, M.K., Occam’s razor, Inform. process. lett., 24, 377-380, (1987) · Zbl 0653.68084 |

[10] | Bradley, P.S.; Mangasarian, O.L., K-plane clustering, J. global optim., 16, 23-32, (2000) · Zbl 0990.90135 |

[11] | Censor, Y.; Zenios, S.A., Parallel optimization: theory, algorithms and applications, (1997), Oxford University Press Oxford · Zbl 0945.90064 |

[12] | Chinneck, J., Fast heuristics for the maximum feasible subsystem problem, INFORMS J. comput., 13, 210-213, (2001) · Zbl 1238.90093 |

[13] | Frean, M., A “thermalâ€ť perceptron learning rule, Neural comput., 4, 6, 946-957, (1992) |

[14] | Garey, M.R.; Johnson, D.S., Computers and intractability: A guide to the theory of NP-completeness, (1979), W.H. Freeman and Company San Francisco · Zbl 0411.68039 |

[15] | Goffin, J.L., The relaxation method for solving systems of linear inequalities, Math. oper. res., 5, 388-414, (1980) · Zbl 0442.90051 |

[16] | Greer, R., Trees and hills: methodology for maximizing functions of systems of linear relations, Annals of discrete mathematics, Vol. 22, (1984), Elsevier science publishers B.V Amsterdam |

[17] | Hansen, P.; Jaumard, B., Clustering analysis and mathematical programming, Math. programming B, 79, 191-216, (1997) |

[18] | Illingworth, J.; Kittler, J., The adaptive Hough transform, IEEE trans. pattern anal. Mach. intell., PAMI-9, 5, 690-698, (1987) |

[19] | Illingworth, J.; Kittler, J., A survey of the Hough transform, Comput. vision graphics image process., 44, 87-116, (1988) |

[20] | Kohonen, T., The self organizing map, Proc. IEEE, 78, 1464-1480, (1990) |

[21] | Kultaken, P.; Xu, L.; Oja, E., A new curve detection method: randomized Hough transform, Pattern recognition lett., 11, 331-338, (1995) · Zbl 0942.68696 |

[22] | Leavers, V.F., Which Hough transform?, CVGIP: image understanding, 58, 2, 250-264, (1993) |

[23] | Lee, E.K.; Gallagher, R.J.; Zaider, M., Planning implants of radionuclides for the treatment of prostate cancer: an application of mixed integer programming, Optima, 61, 1-7, (1999) |

[24] | Mangasarian, O.L., Misclassification minimization, J. global optim., 5, 309-323, (1994) · Zbl 0814.90081 |

[25] | M. Mattavelli, Motion analysis and estimation: from ill-posed discrete inverse linear problems to MPEG-2 coding, Ph.D. Thesis No. 1597, Communication Systems Division, Swiss Federal Institute of Technology, Lausanne, 1997. |

[26] | M. Mattavelli, V. Noel, E. Amaldi, A new efficient line detection algorithm based on combinatorial optimization techniques, Proceedings of the 1998 International Conference on Image Processing (ICIP98), Chicago, Illinois, October 4-7 1998, IEEE Signal Processing Society. · Zbl 0986.68538 |

[27] | M. Mattavelli, V. Noel, E. Amaldi, A new approach for fast line detection based on combinatorial optimization, Proceedings of ICIAP99, International Conference on Image Analysis and Processing, Venice, Italy, September 27-29, 1999, pp. 168-173. |

[28] | M. Mattavelli, V. Noel, E. Amaldi, Fast line detection algorithms based on combinatorial optimization, Proceedings of the 4th International Workshop on Visual Form (IWVF4), Capri, Italy, Lecture Notes in Computer Science, eds. C. Arcelli and L.P. Cordella and G. Sanniti di Baja, Springer, Berlin, 2001, pp. 410-419. · Zbl 0986.68538 |

[29] | Minsky, M.L.; Papert, S., Perceptrons: an introduction to computational geometry, (1988), MIT Press Cambridge, MA · Zbl 0197.43702 |

[30] | Motzkin, T.S.; Schoenberg, I.J., The relaxation method for linear inequalities, Canadian J. math., 6, 393-404, (1954) · Zbl 0055.35002 |

[31] | E. Oja, H. Kalviainen, P. Hirvonen, Houghtool a software package for Hough transform calculation, Ninth Scandinavian Conference on Image Analysis, Uppsala, Sweden, 1995, pp. 841-848, http://www.lut.fi/dep/tite/XHoughtool/xhoughtool.html. |

[32] | P. Palmer, M. Petrou, J. Kittler, A Hough transform algorithm with a 2-D hypothesis testing kernel, CVGIP 58(2)(Image Understanding) (1993) 221-234. |

[33] | M. Parker, A set covering approach to infeasibility analysis of linear programming problems and related issues, Ph.D. Thesis, Dep. of Mathematics, University of Colorado at Denver, 1995. |

[34] | Polyak, B.T., Random algorithms for solving convex inequalities, () · Zbl 0997.90053 |

[35] | Rousseeuw, P.J.; Kaufman, L., Finding groups in data, (1990), Wiley New York · Zbl 1345.62009 |

[36] | Rousseeuw, P.J.; Leroy, A.M., Robust regression and outlier detection, (1987), Wiley New York |

[37] | Ryan, J., Transversals of IIS-hypergraphs, Congr. numer., 81, 17-22, (1991) · Zbl 0765.05075 |

[38] | Telgen, J., On relaxation methods for systems of linear inequalities, European J. oper. res., 9, 184-189, (1982) · Zbl 0476.65041 |

[39] | Tong, H., Threshold models in nonlinear time series analysis, (1983), Springer New York |

[40] | Tong, H., Nonlinear time series, (1990), Oxford University Press Oxford |

[41] | J.-M. Vesin, A common generalization framework for two classical nonlinear models, Proceedings of International Workshop on Nonlinear Digital Signal Processing, Tampere, Finland, 1993, pp. 6-2.3. |

[42] | J.-M. Vesin, M. Mattavelli, E. Amaldi, A new approach to piecewise linear modeling based on a combinatorial optimization formulation, Physica D, under revision. |

[43] | Xu, L.; Oja, E.; Kultanen, P., A new curve detection method: randomized Hough transform, Pattern recognition lett., 11, 5, 334-344, (1990) |

[44] | Zapata, E.; Guil, N.; Villalba, J., A fast Hough transform for segment detection, IEEE trans. image process., 4-11, 1541-1548, (1995) |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.