We propose a method for solving the speech direction estimation problem by computer algebra. The method is based on the function approximation using the minimax polynomial. The minimax polynomial is obtained by an iterative method called the Remez exchange algorithm, in which Gröbner bases computation is employed. We present an efective way to compute the minimax polynomial using Gröbner bases. Estimation problem, Function approximation, Minimax polynomial, Remez exchange algorithm, Gröbner basis, Speech direction estimation problem ∗Corresponding author.
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 [
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 [
CEUR Workshop Proceedings
ceur-ws.org
ISSN1613-0073
approximation together with Gröbner bases [
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 [
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.
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 . 2.1. Minimax Approximation In the following, let [, ] be a closed interval and be a continuous function on [, ] . Definition 2.1 (Minimax polynomial). For the function in above, a polynomial ∈ [] which minimizes of degree ‖ − ‖ ∞ = max | () − () ≤≤ | , is called the -th minimax polynomial of .
Definition 2.1 says that, if ∈ []
is the -th minimax polynomial of , the inequality max | () − ()| ≤ ≤≤ max | () − ()|, ≤≤ follows for any ∈ [] with deg = . In other words, the -th minimax polynomial is the best polynomial in terms of error. Thus, one should use the minimax polynomial if one wants to approximate the given function by polynomials with minimizing errors.
The following theorem [
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 [
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 1Solving a system of linear equations is performed by Risa/Asir itself and the function”os_md.fmmx()” in the os_muldif library is used for computing extremum points with the extrema. 5: 6: Require: a continuous function , a closed interval [, ] , a degree of a polynomial Ensure: a minimax polynomial ∈ []
with degree 1: max ≔ ∞, min ≔ 0 2: ≔ [ 0, 1, … , , +1 ] : + 2 initial interpolate points 3: while max >> min do [ 0, 1, … , , ] : the solution of ∑
=0 ( ) + (−1 ) = ( ) ( = 0, 1, … , , + 1) ≔ [ 0, 1, … , , +1 ] : the + 2 extremum points of () ≔ () − () max ≔ max{|( 0)|, |( 1)|, … , |( +1 )|}, min ≔ min{|( 0)|, |( 1)|, … , |( +1 )|} polynomial becomes larger and the interval [, ] more restricted. The method in this paper can be used if functions are continuous, their range is bounded and the variable to solve is in a bounded interval. If the variable to solve is in a bounded interval that is not closed, we can construct the minimax polynomial over a closed one containing it.
Note that the minimax polynomial of has the following property: the error function − has deg + 2 maximum value with alternate change of singers in [, ] . The value of | () − () | rapidly becomes larger as the value separates from [, ] .
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
(1)
(2)
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
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 [
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.
( , ) + ∑ ( )ℎ ( ) = 0, () +
∑ ( ) = 0, ,,
Speech direction estimation problem [
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 [
Distance attenuation is the efect 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 efect 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 [
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 = ( − sin cos sin cos
) ( − ). the theoretical sound pressure level ̂ recorded by mic is described as The parameters and stand for the coordinate of mic and the user in Σ , respectively. Then, ̂ = − 10 log10 ‖ ‖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 = ( − sin cos sin cos ) ( − ) the theoritical sound pressure level ̂ recorded by mic is described as The parameters and stands for the coordinate of mic and the user in Σ respectively. Then, ̂ = − 10 log10 ‖ ‖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 , Thus, the term (1 − , and are measurable parameters, one can substitute measured values into these.
1 + cos( )) can be alternated by a measured parameter and ̂ can be substituted by a measured value. Thus, the equation above can be transformed into the form of ̂ − + 10 log10 ‖ ‖2 + = 0.
Since the term log10 ‖ ‖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 ̂ − + 10 () + = 0.
The equation above is a multivariate polynomial in , , for any number . To find (− < ≤ ), we need to measure parameters ,
, , ̂ for given ≥ 3 , thus we compute the Gröbner bases and make the system of equations a triangular form.
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 [
Furthermore, there exist the minimax rational functions and algorithms for computing ones. The minimax rational function of is a rational function , which minimizes ≤≤ max | () − , ()| = ≤≤ max | () −
∑
≥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 [
To solve estimation problems independent of the values of measured parameters, we need to
approximate multivariate functions with multivariate polynomials or rational functions. Cody [
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 eficacy or efectiveness of this method, we should seek estimation problems that can be solved by this method.