Novel convex decomposition of piecewise affine functions
In this paper, we present a novel approach to decompose a given piecewise affine (PWA) function into two convex PWA functions. Convex decompositions are useful to speed up or distribute evaluations of PWA functions. Different approaches to construct a convex decomposition have already been published. However, either the two resulting convex functions have very high or very different complexities, which is often undesirable, or the decomposition procedure is inapplicable even for simple cases. Our novel methodology significantly reduces these drawbacks in order to extend the applicability of convex decompositions.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Linear-Size Neural Network Representation of Piecewise Affine Functions in $\mathbb{R}^2$
It is shown that any continuous piecewise affine (CPA) function $\mathbb{R}^2\to\mathbb{R}$ with $p$ pieces can be represented by a ReLU neural network with two hidden layers and $O(p)$ neurons. Unlike prior work, which …
Representing Piecewise Linear Functions by Functions with Small Arity
A piecewise linear function can be described in different forms: as an arbitrarily nested expression of $\min$- and $\max$-functions, as a difference of two convex piecewise linear functions, or as a linear combination o…
On Coordinate Minimization of Convex Piecewise-Affine Functions
A popular class of algorithms to optimize the dual LP relaxation of the discrete energy minimization problem (a.k.a.\ MAP inference in graphical models or valued constraint satisfaction) are convergent message-passing al…
Locally Linear Attributes of ReLU Neural Networks
A ReLU neural network determines/is a continuous piecewise linear map from an input space to an output space. The weights in the neural network determine a decomposition of the input space into convex polytopes and on ea…
Piecewise Linear Regression via a Difference of Convex Functions
We present a new piecewise linear regression methodology that utilizes fitting a difference of convex functions (DC functions) to the data. These are functions $f$ that may be represented as the difference $\phi_1 - \phi…
regression