**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Concept# Linear interpolation

Summary

In mathematics, linear interpolation is a method of curve fitting using linear polynomials to construct new data points within the range of a discrete set of known data points.
Linear interpolation between two known points
If the two known points are given by the coordinates (x_0,y_0) and (x_1,y_1), the linear interpolant is the straight line between these points. For a value x in the interval (x_0, x_1), the value y along the straight line is given from the equation of slopes
\frac{y - y_0}{x - x_0} = \frac{y_1 - y_0}{x_1 - x_0},
which can be derived geometrically from the figure on the right. It is a special case of polynomial interpolation with n=1.
Solving this equation for y, which is the unknown value at x, gives
\begin{align}
y &= y_0 + (x-x_0)\frac{y_1 - y_0}{x_1 - x_0} \
&= \frac{y_0(x_1-x_0)}{x_1-x_0} + \fra

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications

Loading

Related people

Loading

Related units

Loading

Related concepts

Loading

Related courses

Loading

Related lectures

Loading

Related publications (26)

Loading

Loading

Loading

Related units

Related people

No results

No results

Related concepts (7)

Interpolation

In the mathematical field of numerical analysis, interpolation is a type of estimation, a method of constructing (finding) new data points based on the range of a discrete set of known data points.

Computer graphics

Computer graphics deals with generating s and art with the aid of computers. Today, computer graphics is a core technology in digital photography, film, video games, digital art, cell phone and comp

Spline interpolation

In the mathematical field of numerical analysis, spline interpolation is a form of interpolation where the interpolant is a special type of piecewise polynomial called a spline. That is, instead of f

Related courses (26)

MATH-251(a): Numerical analysis

This course presents numerical methods for the solution of mathematical problems such as systems of linear and non-linear equations, functions approximation, integration and differentiation and differential equations.

CIVIL-321: Numerical modelling of solids and structures

La modélisation numérique des solides est abordée à travers la méthode des éléments finis. Les aspects purement analytiques sont d'abord présentés, puis les moyens d'interpolation, d'intégration et de résolution de la mécanique sont étudiés.

MATH-351: Advanced numerical analysis

The student will learn state-of-the-art algorithms for solving differential equations. The analysis and implementation of these algorithms will be discussed in some detail.

Related lectures (60)

Quentin Christian Becker, Mike Yan Michelis

The underlying geometrical structure of the latent space in deep generative models is in most cases not Euclidean, which may lead to biases when comparing interpolation capabilities of two models. Smoothness and plausibility of linear interpolations in latent space are associated with the quality of the underlying generative model. In this paper, we show that not all such interpolations are comparable as they can deviate arbitrarily from the shortest interpolation curve given by the geodesic. This deviation is revealed by computing curve lengths with the pull-back metric of the generative model, finding shorter curves than the straight line between endpoints, and measuring a non-zero relative length improvement on this straight line. This leads to a strategy to compare linear interpolations across two generative models. We also show the effect and importance of choosing an appropriate output space for computing shorter curves. For this computation we derive an extension of the pull-back metric.

2021Options are some of the most traded financial instruments and computing their price is a central task in financial mathematics and in practice. Consequently, the development of numerical algorithms for pricing options is an active field of research. In general, evaluating the price of a specific option relies on the properties of the stochastic model used for the underlying asset price. In this thesis we develop efficient and accurate numerical methods for option pricing in a specific class of models: polynomial models. They are a versatile tool for financial modeling and have useful properties that can be exploited for option pricing.
Significant challenges arise when developing option pricing techniques. For instance, the underlying model might have a high-dimensional parameter space. Furthermore, treating multi-asset options yields high-dimensional pricing problems. Therefore, the pricing method should be able to handle high dimensionality. Another important aspect is the efficiency of the algorithm: in real-world applications, option prices need to be delivered within short periods of time, making the algorithmic complexity a potential bottleneck. In this thesis, we address these challenges by developing option pricing techniques that are able to handle low and high-dimensional problems, and we propose complexity reduction techniques.
The thesis consists of four parts:
First, we present a methodology for European and American option pricing. The method uses the moments of the underlying price process to produce monotone sequences of lower and upper bounds of the option price. The bounds are obtained by solving a sequence of polynomial optimization problems. As the order of the moments increases, the bounds become sharper and eventually converge to the exact price under appropriate assumptions.
Second, we develop a fast algorithm for the incremental computation of nested block triangular matrix exponentials. This algorithm allows for an efficient incremental computation of the moment sequence of polynomial jump-diffusions. In other words, moments of order 0, 1, 2, 3... are computed sequentially until a dynamically evaluated criterion tells us to stop. The algorithm is based on the scaling and squaring technique and reduces the complexity of the pricing algorithms that require such an incremental moment computation.
Third, we develop a complexity reduction technique for high-dimensional option pricing. To this end, we first consider the option price as a function of model and payoff parameters. Then, the tensorized Chebyshev interpolation is used on the parameter space to increase the efficiency in computing option prices, while maintaining the required accuracy. The high dimensionality of the problem is treated by expressing the tensorized interpolation in the tensor train format and by deriving an efficient way, which is based on tensor completion, to approximate the interpolation coefficients.
Lastly, we propose a methodology for pricing single and multi-asset European options. The approach is a combination of Monte Carlo simulation and function approximation. We address the memory limitations that arise when treating very high-dimensional applications by combining the method with optimal sampling strategies and using a randomized algorithm to reduce the storage complexity of the approach.
The obtained numerical results show the effectiveness of the algorithms developed in this thesis.

Ahlswede et al. in the seminal paper [1] have shown that in data transfer over networks, processing the data at the nodes can significantly improve the throughput. As proved by Li et al. in [2], even with a simple type of operation, namely linear operation, the throughput can still be vastly improved. In [3], it is shown that the multicasting problem over networks can be translated to an algebraic question about a polynomial associated to the network called network polynomial. In this thesis, we start from the algorithm of [3] and extend it in several directions. First, we generalize the framework of [3] to include the case where the messages can also be vectors over some fixed finite field. We also show that in contrast to the original algorithm, ours can be used to reduce the field size for the case of sending finite field elements. In both vector network code algorithm and finite field minimization, we translate the network code design problems into an algebraic problem about network polynomials. Because of the importance of the network polynomials, we investigate more properties of them and we study the relationship between these objects and the topological properties of the network. Then, we extend the result of [3] to the deterministic models for wireless relay networks, a very important class of networks that has been introduced in [4] by Avestimehr, Diggavi and Tse. Finally, for another class of networks, called broadcast networks, we introduce the transfer matrix and using its properties, we show that in the absence of public messages, processing the information at the nodes will not improve the throughput.