Research‎ > ‎

Function approximation

A topic that I find interesting is how to approximate functions in an optimal way for a particular application, either from the point of view of improving the performance of algorithms running on accelerated hardware such as GPUs or from a more theoretical point of view on classification problems using confidence regions.


Optimal piecewise linear function approximation for GPU-based applications
Summary of the proposed knot placement technique to define a continuous piecewise linear approximation of a function f. Knots (in red) are distributed according to the amount of local convexity of f given by the local knot density (lkd, top plot). Hence, fewer knots are placed around the zeros of the lkd, which correspond to the less steep regions of F.

Many computer vision and human-computer interaction applications developed in recent years need evaluating complex and continuous mathematical functions as an essential step toward proper operation. However, rigorous evaluation of these kind of functions often implies a very high computational cost, unacceptable in real-time applications. To alleviate this problem, functions are commonly approximated by simpler piecewise-polynomial representations. Following this idea, we propose a novel, efficient, and practical technique to evaluate complex and continuous functions using a nearly optimal design of two types of piecewise linear approximations in the case of a large budget of evaluation subintervals. To this end, we develop a thorough error analysis that yields asymptotically tight bounds to accurately quantify the approximation performance of both representations. It provides an improvement upon previous error estimates and allows the user to control the tradeoff between the approximation error and the number of evaluation subintervals. To guarantee real-time operation, the method is suitable for, but not limited to, an efficient implementation in modern graphics processing units, where it outperforms previous alternative approaches by exploiting the fixed-function interpolation routines present in their texture units. The proposed technique is a perfect match for any application requiring the evaluation of continuous functions; we have measured in detail its quality and efficiency on several functions, and, in particular, the Gaussian function because it is extensively used in many areas of computer vision and cybernetics, and it is expensive to evaluate.

References:
D. Berjón, G. Gallego, C. Cuevas, F. Morán, N. García
Optimal piecewise linear function approximation for GPU-based applications
IEEE Transactions on Cybernetics, vol. 46, no. 11, pp. 2584-2595, Nov. 2016.
doi,  PDF (arXiv) PDF (OA-UPM).


Optimal polygonal L1 linearization and fast interpolation of nonlinear systems
Suboptimal partition for the linear chirp function f(x) = sin(10πx2) in the interval x∈[0,1] . Top: local knot density (lkd) corresponding to f. Bottom: polygonal interpolant with N=127 (128 knots) overlaid on function f.

The analysis of complex nonlinear systems is often carried out using simpler piecewise linear representations of them. A principled and practical technique is proposed to linearize and evaluate arbitrary continuous nonlinear functions using polygonal (continuous piecewise linear) models under the L1 norm. A thorough error analysis is developed to guide an optimal design of two kinds of polygonal approximations in the asymptotic case of a large budget of evaluation subintervals N. The method allows the user to obtain the level of linearization (N) for a target approximation error and vice versa. It is suitable for, but not limited to, an efficient implementation in modern Graphics Processing Units (GPUs), allowing real-time performance of computationally demanding applications. The quality and efficiency of the technique has been measured in detail on two nonlinear functions that are widely used in many areas of scientific computing and are expensive to evaluate.

References:
G. Gallego, D. Berjón, N. García
Optimal polygonal L1 linearization and fast interpolation of nonlinear systems
IEEE Transactions on Circuits and Systems I: Regular Papers, vol. 61, no. 11, pp. 3225-3234, Nov. 2014.
doi,  PDF (arXiv),  PDF (OA-UPM).


Optimal confidence regions in multi-dimensional Gaussian distributions


Results obtained from the application of the classical GMM method to detect moving objects in two different outdoor sequences. Color notation: correct detections (green), misdetections (red), and false detections (black).

Many existing engineering works model the statistical characteristics of the entities under study as normal distributions. These models are eventually used for decision making, requiring in practice the definition of the classification region corresponding to the desired confidence level. Surprisingly enough, however, a great amount of computer vision works using multidimensional normal models leave unspecified or fail to establish correct confidence regions due to misconceptions on the features of Gaussian functions or to wrong analogies with the unidimensional case. The resulting regions incur in deviations that can be unacceptable in high-dimensional models. Here we provide a comprehensive derivation of the optimal confidence regions for multivariate normal distributions of arbitrary dimensionality. To this end, firstly we derive the condition for region optimality of general continuous multidimensional distributions, and then we apply it to the widespread case of the normal probability density function. The obtained results are used to analyze the confidence error incurred by previous works related to vision research, showing that deviations caused by wrong regions may turn into unacceptable as dimensionality increases. To support the theoretical analysis, a quantitative example in the context of moving object detection by means of background modeling is given.

References:
G. Gallego, C. Cuevas, R. Mohedano, N. García
On the Mahalanobis distance classification criterion for multidimensional normal distributions
IEEE Transactions on Signal Processing, vol. 61, no. 17, pp. 4387-4396, Sep. 2013.
doi,  PDF (OA-UPM).