Intorduction

In this paper, we discuss solving estimation problems with a function approximation method using the minimax polynomial and computer algebra.

Function approximation is the technique to approximate functions. It is used to make a sequence of polynomials for proving the density of function space [1] or to regard a function as a polynomial for evaluation [2]. Various methods for function approximation have been proposed, such as the Maclaulin expansion or the least squares method [2]. Here, as one of them, we present the minimax approximation and Remez exchange algorithm. The minimax approximation is the approximation using the polynomial which meets the property that the maximum value of the difference between the given function and the derived polynomial is the smallest of all polynomials in a given domain. The polynomial satisfying such a property is called the minimax polynomial. Since minimax polynomials are polynomials, one can use algebraic computation. On the other hand, the interpolation method [2], which is frequently used in computer algebra, estimates the polynomial based on discrete points and values on the original function. Compared with the interpolation method, the minimax approximation is better for errors, that is, the maximum value of errors of the minimax polynomial is less than that of the polynomial obtained by the interpolation method in many cases. In computing the minimax polynomial, an iteration method called the Remez exchange algorithm is used.

Estimation problems are the problems of estimating unknown information using already known information. Solving estimation problems is important in developing devices since objects that are measurable are limited. To solve estimation problems, one uses numerical methods such as the gradient method [3] or the genetic Algorithms [4]. However, the gradient method may return a local solution depending on initial values since it uses local convergence properties, and the genetic algorithm has some disadvantages in that it sometimes solves the estimation problem not properly due to the phenomena called initial convergence and hitchhiking. On the other hand, the estimation method using minimax approximation together with Gröbner bases [5] computation may avoid these phenomena, for this method evaluates values globally.

In this paper, we propose a method for solving estimation problems using the minimax polynomial and Gröbner bases, as follows. First, for a given mathematical model (function) of the estimation problem, we calculate the minimax polynomial which approximates the given function. Then, we make a system of polynomial equations and solve it with Gröbner bases computation for obtaining the solution of the estimation problem. Furthermore, we apply the proposed method to the speech direction estimation problem, which is an estimation of the direction of a speaker using a microphone array. For the speech direction estimation problem, a method using the Genetic Algorithm has been proposed [6]. We show that we can effectively use the minimax approximation and Gröbner bases for finding global solutions to the speech direction estimation problem.

The paper is organized as follows. In Section 2, we review the definition of the minimax polynomial and the Remez exchange algorithm. In Section 3, after defining the estimation problem more minutely, we propose a solution for this using the minimax approximation and Gröbner bases. In Section 4, we introduce the speech direction estimation problem, which is the task we are working on, and explain the reason why the method in this paper can be used. In Section 5, we conclude and pick up some challenges we are facing and tasks to improve our tasks.

Preliminaries

Let 𝐾 be a field. The notation 𝐾 [𝑥] or 𝐾 [𝑥 1 , … , 𝑥 𝑛 ] stands for the ring of polynomials over 𝐾 in 𝑥 1 , … , 𝑥 𝑛 . For a function 𝑓, ‖𝑓 ‖ ∞ denotes the infinity norm of 𝑓.

Minimax Approximation

In the following, let [𝑎, 𝑏] be a closed interval and 𝑓 be a continuous function on [𝑎, 𝑏]. The following theorem [2] tells us that that that value has a minimum value.

Theorem 2.1. If the function 𝑓 is continuous, the 𝑓 has a unique 𝑘-th minimax polynomial for any 𝑘 ∈ ℤ ≥0 . Furthermore, we can construct the 𝑘-th degree minimax polynomial by Algorithm 1.

For details of Algorithm 1 such as uniqueness and termination, see [7]. Note that Algorithm 1 needs to compute the solution of a system of linear equations and the extremum points of continuous functions. (We have implemented Algorithm 1 using a computer algebra system Risa/Asir [8] with the library os_muldif [9] 1 .)

The method to approximate functions using the Remez exchange algorithm is called minimax approximation. Note that the maximum error of 𝑓 − 𝑃 becomes smaller as the degree of minimax

The estimation problem

In this section, we introduce the method to solve estimation problems using minimax approximation and computer algebra.

Let 𝑢 = (𝑢 1 , … , 𝑢 𝑛 ) be measurable parameters and 𝑣 = (𝑣 1 , … , 𝑣 𝑡 ) be immeasurable parameters, and 𝑥 be the parameter to be estimated. Assume that a mathematical model describing phenomena is given as

𝑓 (𝑢, 𝑥) + ∑ 𝑖,𝑗,𝑘 𝑔 𝑖 (𝑢)ℎ 𝑗 (𝑣 𝑘 ) = 0,(1)

where 𝑓 is a continuous function and 𝑥 is bounded. Since 𝑢 are measurable, one can consider 𝑓 (𝑢, 𝑥) as a function only in 𝑥, 𝑔 𝑖 (𝑢) as a constant by substituting 𝑢 and ℎ 𝑖 (𝑣 𝑗 ) as a new immeasurable parameter by replacing it with a new variable properly if necessary. Thus, 𝑓 can be approximated by the minimax polynomial and the equation is transformed into the form of

𝑃(𝑥) + ∑ 𝑖 𝑄 𝑖 (𝑣) = 0,(2)

where 𝑃 and 𝑄 𝑖 represents the polynomials in 𝑥 and 𝑣, respectively. As eq. ( 2) is a multivariate polynomial equation, a system of polynomial equations can be generated by substituting measured values into measurable parameters. Thus, Gröbner bases and the Elimination Theorem [5] can be used to solve the system. Note that the minimax approximation is the best way to approximate a function by polynomials in terms of errors. However, under some conditions, the minimax approximation cannot be performed. To be able to apply the approximation, the mathematical model with the estimated parameter must be continuous, have no other immeasurable parameters, and the estimated parameter must be in a bounded interval. The more restricted the interval is, the better the accuracies of the minimax approximations are. Thus this method is suitable for estimation problems in that the range of the solution of the estimated parameters is bounded.

An example by speech direction estimation problem

Speech direction estimation problem [6] is the problem of estimating the orientation of the speaker's face. This problem derives from robotics. Nowadays robots have been playing important roles in various fields and some research on robots cooperating with each other is underway [10,11]. For such tasks, how to select one robot from more than one is one of the themes when humans select and command one to do some tasks. Thus, we are trying to select one robot by calling like humans saying "excuse me" or "hey. " We assume a situation in a room like we are calling one robot waiter from many in a restaurant. Thus naming each robot is difficult.

We suppose that we know the coordinates of a user and robots, for the microphone arrays we are assuming have a function to compute the locations of themselves and the directions of arrival (DoA) and we can compute the user's location using DoA. For details, see [6]. To estimate the direction of the speaker's face orientation, we use a mathematical model called the voice spread model. The voice spread model is a formula to compute logical sound pressure levels recorded by a particular microphone array. We consider the situation in which there is a speaker and microphone array mic 𝑖. To construct a voice spread model, we need to consider two attenuation effects, distance attenuation and angle attenuation.

Distance attenuation is the effect that the longer the distance between a sound source and a sound receiving point is, the smaller the sound pressure level of the receiving point is. Supposing a sound source to be a point, the sound pressure level is in inverse proportion to the square of the distance.

Angle attenuation is the effect that the sound pressure level is the strongest in the front direction of a mouth and it gets weaker when separate from the direction. There are various kinds of research on angle attenuations [12,13,14] and we adopt Monson's [15].

Let Σ 𝑊 be the world coordinate system, Σ 𝑆 be the local coordinate system whose center is the user and the 𝑥-axis is the front direction of the user's face. Furthermore, let 𝜃 be the angle formed by the 𝑥-axis of Σ 𝑊 and Σ 𝑆 . Note that 𝜃 is the very estimated parameter. Then, the coordinate of mic 𝑖 is expressed as

𝑆 𝑝 𝑖 = ( cos 𝜃 sin 𝜃 − sin 𝜃 cos 𝜃 ) ( 𝑊 𝑝 𝑖 − 𝑊 𝑝 𝑆 ).

The parameters 𝑊 𝑝 𝑖 and 𝑊 𝑝 𝑆 stand for the coordinate of mic 𝑖 and the user in Σ 𝑊 , respectively. Then, the theoretical sound pressure level L 𝑖 recorded by mic 𝑖 is described as

L 𝑖 = 𝐿 − 10 log 10 ‖ 𝑆 𝑝 𝑖 ‖ 2 − 𝑎 (1 − 1 + cos(𝜑 𝑖 ) 2 ) .

Note that parameter 𝐿 is the sound pressure level of the point that is 1 [m] away from the speaker and in the direction of the speaker's mouth. A parameter 𝑎 is the size of angle attenuation and 𝜙 𝑖 represents the azimuth angle to mic 𝑖 in Σ 𝑆 . Note that the parameters 𝐿 and 𝑎 are immeasurable and 𝜙 𝑖 is measurable. Let Σ 𝑊 be the world coordinate system, Σ 𝑆 be the local coordinate system whose center is the user and 𝑥-axis is the front direction of the user's face. Also let 𝜃 be the angle formed by 𝑥-axises of Σ 𝑊 and Σ 𝑆 . Note that 𝜃 is the very estimated parameter. The coordinate of mic 𝑖's microphone array is expressed as

𝑆 𝑝 𝑖 = ( cos 𝜃 sin 𝜃 − sin 𝜃 cos 𝜃 ) ( 𝑊 𝑝 𝑖 − 𝑊 𝑝 𝑆 )

The parameters 𝑊 𝑝 𝑖 and 𝑊 𝑝 𝑆 stands for the coordinate of mic 𝑖 and the user in Σ 𝑊 respectively. Then, the theoritical sound pressure level L 𝑖 recorded by mic 𝑖 is described as

L 𝑖 = 𝐿 − 10 log 10 ‖ 𝑆 𝑝 𝑖 ‖ 2 − 𝑎 (1 − 1 + cos(𝜑 𝑖 ) 2 )

Note that parameter 𝐿 is the sound pressure level of the point that is 1 [m] away from the speaker and in the direction of the speaker's mouse. A parameter 𝑎 is the size of angle attenuation and 𝜙 𝑖 represents the azimuth angle to mic 𝑖 in Σ 𝑆 . Make sure that the parameters 𝐿 and 𝑎 are immeasurable and 𝜙 𝑖 is measurable.

Since 𝑊 𝑝 𝑖 , 𝑊 𝑝 𝑆 , and 𝜑 𝑖 are measurable parameters, one can substitute measured values into these.

Thus, the term (1 − 1 + cos(𝜑 𝑖 ) 2 ) can be alternated by a measured parameter 𝑚 𝑖 and L 𝑖 can be substituted by a measured value. Thus, the equation above can be transformed into the form of L 𝑖 − 𝐿 + 10 log 10 ‖ 𝑆 𝑝 𝑖 ‖ 2 + 𝑎𝑚 𝑖 = 0.

Since the term log 10 ‖ 𝑆 𝑝 𝑖 ‖ 2 can be regarded as a function with the variable 𝜃 only and 𝜃 is in a bounded interval (−𝜋, 𝜋], we can approximate that term by the minimax polynomial 𝑃 𝑖 (𝜃). As a result, we have

L 𝑖 − 𝐿 + 10𝑃 𝑖 (𝜃) + 𝑎𝑚 𝑖 = 0.

The equation above is a multivariate polynomial in 𝐿, 𝜃, 𝑎 for any number 𝑖. To find 𝜃 (−𝜋 < 𝜃 ≤ 𝜋), we need to measure parameters 𝑊 𝑝 𝑖 , 𝑊 𝑝 𝑆 , 𝜑 𝑖 , L 𝑖 for given 𝑖 ≥ 3, thus we compute the Gröbner bases and make the system of equations a triangular form.

Concluding remarks

In this paper, we have proposed a method for estimation problems using the minimax approximation and Gröbner bases computation. As an application, we have shown that the method can be used for the speech direction estimation problem.

To check the accuracy of the proposed method, experiments should be carried out in simulations and actual environments. For simulations of speech direction estimation problems, Python language has a library called Pyroomacoustics [16]. It is a software library to develop and test algorithms for voice processing, and can simulate an environment in a room and one can adjust the properties of the environment such as the location and the directivity of a sound source and a microphone, temperature, humidity, dimension, size and shape of a room and so on.

Furthermore, there exist the minimax rational functions and algorithms for computing ones. The minimax rational function of 𝑓 is a rational function 𝑅 𝑚,𝑘 which minimizes for given 𝑚, 𝑘 ∈ ℤ ≥1 . Compared with the minimax polynomials, the minimax rational functions tend to have less errors. However, we failed to compute one properly due to errors in the calculation of improper integrals. We need to compute Chebyshev expansion [2] of 𝑓 to construct a minimax rational function and to compute improper integrals. In our experiment, we failed to compute improper integrals properly due to divergence of integrands. Thus, the method to compute improper integrals with fewer errors should be investigated.

To solve estimation problems independent of the values of measured parameters, we need to approximate multivariate functions with multivariate polynomials or rational functions. Cody [17] says almost no algorithm for approximating those with minimax polynomials (or rational functions) exists. However, Luke [18] has made approximations of a variety of functions in mathematical physics using hypergeometric functions. Loeb [19] reports a linear algorithm to create rational approximations over a discrete point set. Fox, Goldstein and Lastman [20] also have proposed an algorithm for rational approximation on finite point sets.

The problem with which this method can be used is very limited since mathematical models that satisfy equation (1) and estimated parameters to be bounded are very restrictive. However, direction estimation problems are good because parameters of direction are usually bounded on (−𝜋, 𝜋] or [0, 2𝜋). To see the efficacy or effectiveness of this method, we should seek estimation problems that can be solved by this method.