3.3.1 Interpolating Polynomials

Given the set , consider the three functions , , and , defined as follows:

is a d-degree polynomial with . Consider the function , along with a representative G, . We may deduce that G is a function, and that:

It follows that the functions , , and are well defined, for our choice of G. Since , the function ,

interpolates G. is the quadratic Lagrange interpolating polynomial of G.  

may be expressed in standard polynomial form:

with

is the coefficient of in , a d-degree polynomial. The leading coefficient,   , is of special interest, and may be denoted simply by :

The set G, and the associated polynomial , are:      

• concave down if ,
• linear if , and
• concave up if ;

where:

Consider , a richer representation of g; . The representation has one of the preceding properties if all three-member subsets of have the same property:

All three properties are considered to be satisfied by sparse representations of g since

where . For G = g, the usual definitions of linearity and concavity are equivalent to those given here. Let state that has one of the above properties:  

For all representations ,

Using the linear and quadratic interpolating polynomials we will construct linear bounds for many common functions.

Jeff Tupper

March 1996