![MathJax Logo](/templates/jsp/_style2/_tandf/pb2/images/math-jax.gif)
Abstract
The inverse of a Vandermonde matrix has been used for signal processing, polynomial interpolation, curve fitting, wireless communication, and system identification. In this paper, we propose a novel fast recursive algorithm to compute the inverse of a Vandermonde matrix. The algorithm computes the inverse of a higher order Vandermonde matrix using the available lower order inverse matrix with a computational cost of . The proposed algorithm is given in a matrix form, which makes it appropriate for hardware implementation. The running time of the proposed algorithm to find the inverse of a Vandermonde matrix using a lower order Vandermonde matrix is compared with the running time of the matrix inversion function implemented in MATLAB.
Public Interest Statement
The Vandermonde matrix and its inverse have been widely used in many applications, such as polynomial interpolation and signal processing. In this paper, a fast recursive algorithm is proposed to find the inverse of a Vandermonde matrix. We show that the inverse of a Vandermonde matrix can be computed recursively using the inverse of a reduced size
Vandermonde matrix. The size of
Vandermonde matrix can be further reduced until we reach to a size small enough that the inverse can be computed easily.
Furthermore, the proposed algorithm can be used for finding the inverse Vandermonde matrix when the entries are observed sequentially. The proposed algorithm in each iteration uses the new entry and the previous inverse matrix to compute the inverse of the increased size Vandermonde matrix.
1. Introduction
The Vandermonde matrix and its inverse have been widely used in many applications, such as polynomial interpolation (Phillips, Citation2003), curve fitting (Wilf, Citation1958), system identification (Barker, Tan, & Godfrey, Citation2004), signal reconstruction (Olkkonen & Olkkonen, Citation2010), wireless communication (Wang, Scaglione, Giannakis, & Barbarossa, Citation1999), and signal processing (Ryan & Debbah, Citation2009). Computing the inverse of a Vandermonde matrix has been extensively studied over the last four decades. Tou (Citation1964) and Wertz (Citation1965) used the Lagrange interpolation formula and expressed the elements of the inverse of a Vandermonde matrix as the coefficients of a polynomial. Explicit formulas for finding the inverse of the Vandermonde matrix are given in Kaufman (Citation1969), Neagoe (Citation1996), El-Mikkawya (Citation2003), Respondek (Citation2016). Authors in Gautschi and Inglese (Citation1988) found lower bounds for the condition number of the Vandermonde matrices and showed that the bounds grow exponentially as the size of the matrix increases. Therefore, the Vandermonde matrices are usually ill conditioned and the methods proposed in Kaufman (Citation1969), Neagoe (Citation1996), El-Mikkawya (Citation2003) may fail to accurately compute the elements of the inverse matrix. In later works, fast algorithms are derived in and
to compute the elements of the inverse of the Vandermonde matrix (Eisinberg & Fedele, Citation2006; Gohberg & Olshevsky, Citation1997).
In this paper, we propose a novel recursive algorithm for computing the inverse of the Vandermonde matrix. We show that the inverse of a Vandermonde matrix can be computed recursively using the inverse of a reduced size
Vandermonde matrix. The size of
Vandermonde matrix can be further reduced until we reach to a size small enough that the inverse can be computed easily. One of the advantages of the proposed recursive algorithm is its capability to update the inverse matrix when the size of the matrix increases due to observing new incoming entries. The entries of the Vandermonde matrix can be considered as a sequence such that by observing each new entry, the size of the matrix increases by one. In the real-world applications, we may confront situations where a complete set of the entries is not available in advance and the matrix entries are observed sequentially (Aliyari Ghassabeh & Abrishami Moghaddam, Citation2013; Aliyari Ghassabeh, Rudzicz, & Abrishami Moghaddam, Citation2015). The proposed techniques in Kaufman (Citation1969), Neagoe (Citation1996), El-Mikkawya (Citation2003), Gohberg and Olshevsky (Citation1997), Eisinberg and Fedele (Citation2006) require to have access to the whole entries in advance to find the inverse matrix. In contrast to the previously mentioned methods, the proposed recursive algorithm has the ability to observe the entries sequentially and update the new (increased size) inverse matrix simultaneously. The computational cost for computing the inverse of
Vandermonde matrix using
dimensional inverse matrix after observing the new entry is
, which is considerably less than the usual matrix inversion techniques. Furthermore, the proposed recursive algorithm is presented in a matrix form that makes it suitable for hardware implementation and reduces the computational time and complexity.
The paper is organized as follows: Section 2 introduces the new recursive algorithm for computing the inverse of a Vandermonde matrix. The simulation results are given in Section 3, where the running time of the proposed algorithm for computing the inverse of a Vandermonde matrix is compared with the running time of the inverse function implemented in MATLAB. The concluding remarks are given in Section 4.
2. Proposed recursive algorithm
Let denote an
Vandermonde matrix defined over the set of all complex numbers
,
The determinant of
Footnote
1
is given by
(Mirsky, Citation2011). Therefore, the Vandermonde matrix is nonsingular if and only if the parameters
are distinct.
Definition 1
Let be an
matrix defined by
Then we have the following proposition
Proposition 1
(Horn & Johnson, Citation1990) Suppose that and
are defined as above. Let
denote the determinant of the Vandermonde matrix
, i.e.
. Assume
, then
and
is given by
where denotes the ijth cofactor of the matrix
.
Therefore, if is available then
can be computed with complexity
using Proposition 1.Footnote
2
Now we are in a position to prove the following lemma that introduces a recursive algorithm for finding the inverse of a Vandermonde matrix
Lemma 1
Let denote an
Vandermonde matrix such that
. Let
be an
matrix according to Definition 1. Let
denote the identity matrix of order n. Furthermore, let
denote the ijth element of
. Then the inverse of the Vandermonde matrix
is given by the following recursive formula
where
where is computed using Proposition 1,
is a constant matrix, and
are given by
(1)
(1)
Remark 1
(a) | The last two equations in 1 can be rewritten in matrix form as follows | ||||
(b) | For a two dimensional Vandermonde matrix | ||||
(c) | To compute |
Lemma 2
The coefficient defined in (1) is always a non-zero number.
Expressing the equations in a matrix form reduces the running time and makes the hardware implementation easier. Note that the coefficients are needed to construct
and using (2) they can be computed in
. The complexity of computing the matrix product
is
and the complexity of multiplying the result by
is O(n), therefore the inverse of a
Vandermonde matrix
can be found using
in
. The required steps for finding
from
is given as follows
(a) | Compute | ||||
(b) | Construct | ||||
(C) | The inverse matrix is the product of the matrices in step (b), i.e. |
The recursive algorithm for finding the inverse of an Vandermonde matrix,
, can be summarized as follows
Note that we also can start with a Vandermonde matrix
, increase the dimension of the Vandermonde matrix by one in each iteration and compute its inverse using Lemma 1. The iterations stop until the Vandermonde matrix has the desired size. In the next section, we compare the running time of the proposed algorithm with the running time of the matrix inversion function implemented in MATLAB.
3. Simulation results
In the following simulations we compute the running time of the proposed algorithm to find the inverse of a Vandermonde matrix in an adaptive manner for polynomial interpolation. The running time is compared with the inverse function implemented in MATLAB. The algorithm is implemented in MATLAB and the simulations run on a PC with Intel Pentium 4, 2.6 GHZ CPU, and 2048 Mb RAM.
Given a set of n observations , where
s are distinct and
, we can find a unique polynomial p of degree
such that
(Phillips, Citation2003). Suppose that the interpolation polynomial p is given by
. Then the problem can be written in the following matrix form
(4)
(4)
It is a system of n linear equations and the unknown coefficients are given by
(5)
(5)
where is an
Vandermonde matrix. It is clear from (5) that finding the unknown coefficients involves computing the inverse of the associated Vandermonde matrix and multiplying it by
.
In the following simulations we assume that the observations are made sequentially and the observed data are used to find the polynomial p that passes through the given points. We assume that the input data are observed in an increasing order, i.e. . As the number of observed data increases the degree of the polynomial p also linearly increases. For example, if we have k pairs of input data, the degree of the polynomial p is
and by observing the next pair of the data the degree of the polynomial increases to k. In other words, upon arrival of each observation the size of the associated Vandermonde matrix increases by one and we are required to compute the inverse of the new increased size Vandermonde matrix. After each observation, the current matrix inversion algorithms need the whole data set to compute the inverse of the Vandermonde matrix (e.g. the matrix inverse function in MATLAB requires the whole observations to find the inverse matrix). But the proposed algorithm uses only the current observation and the previous inverse matrix to update the inverse of the higher order Vandermonde matrix. As mentioned before, the computational cost for updating the Vandermonde matrix using the proposed algorithm is
, which is much less than most regular matrix inversion techniques.
Figure 1. Comparison between the running times of the proposed algorithm and the matrix inversion function in MATLAB. The size of the Vandermonde matrix increases from 10 to 80, and in each iteration the time required to find the inverse function is computed
![Figure 1. Comparison between the running times of the proposed algorithm and the matrix inversion function in MATLAB. The size of the Vandermonde matrix increases from 10 to 80, and in each iteration the time required to find the inverse function is computed](/cms/asset/531464ec-92c3-4f6e-b9a2-405a9f0cc33a/oaen_a_1175061_f0001_oc.jpg)
We compute the required time for updating the Vandermonde matrix using the proposed algorithm as a function of the size of the matrix. The results are compared with the running time of the function implemented in MATLAB for computing the inverse matrix. For each matrix size, we repeated the experiment 100 times and the average running time was found. The initial size of the Vandermonde matrix is 10 and by adding new entries (observing new data) it gradually increases to 80. For the sake of simplicity, the input elements of a Vandermonde matrix are assumed to be
, i.e.,
. As mentioned before, for finding the polynomial p with degree
we need n pairs of observations
. Since our goal here is to test the performance of the proposed algorithm for finding the inverse of the Vandermonde matrix, we just need the first element of each observation. Figure compares the running times of the proposed algorithm with the MATLAB inverse function for finding the inverse of a Vandermonde matrix as a function of the matrix size. The x-axis in Figure is the size of the Vandermonde matrix, and y-axis is the requires time (second) to find the inverse matrix. It can be observed from Figure that the proposed algorithm is faster than the matrix inversion function in MATLAB.Footnote
4
4. Conclusion
Computing the inverse of a Vandermonde matrix arises in many applications such as polynomial interpolation, curve fitting, and signal processing. In this paper, we proposed a fast recursive algorithm to find the inverse of a Vandermonde matrix. The proposed algorithm in each iteration uses the new entry and the previous inverse matrix to compute the inverse of the increased size Vandermonde matrix. The proposed algorithm can be implemented as a recursive function to find the inverse of a Vandermonde matrix recursively. The running times of the proposed algorithm to find the inverse of a Vandermonde matrix are compared with the inverse function implemented in MATLAB and the simulation results showed that for a sequential data the proposed algorithm is faster than the inverse function in MATLAB.
Additional information
Funding
Notes on contributors
Youness Aliyari Ghassabeh
Youness Aliyari Ghassabeh received the BS degree in electrical engineering from the University of Tehran, Tehran, Iran, in 2004, the MS degree from K.N. Toosi University of Technology, Tehran, in 2006, and the PhD degree in mathematics and engineering from Queen’s University, Kingston, ON, Canada, in 2013. He was a postdoctoral fellow at the Toronto Rehabilitation Institute, University Health Network, Toronto, ON between 2013 to 2014. He is currently a manager in Operational Risk Methodology group at Bank of Montreal, Toronto, ON, Canada. His main research interests include machine learning, statistical pattern recognition, probability theory and stochastic processes, image/signal processing, source coding and information theory.
Notes
1 For the sake of simplicity, hereafter we use to refer to an
Vandermonde matrix
.
2 Note that is jith element of
(Horn & Johnson, Citation1990).
3 We assume that the new entries are added from the left to the Vandermonde matrix. So, for a Vandermonde matrix
, we have
and
. For the general
case, see the Proof of Lemma 1 in Appendix.
4 Note that for the proposed algorithm, the required time for finding the inverse matrix using the previous inverse matrix and the new entry is reported.
5 Otherwise, the determinant of the Vandermonde matrix is zero and the inverse does not exist
References
- Aliyari Ghassabeh, Y. , & Abrishami Moghaddam, H. (2013). Adaptive linear discriminant analysis for online feature extraction. Machine Vision Applications , 24 , 777–794.
- Aliyari Ghassabeh, Y. , Rudzicz, F. , & Abrishami Moghaddam, H. (2015). Fast incremental LDA feature extraction. Pattern Recognition , 31 , 1999–2012.
- Barker, H. A. , Tan, A. H. , & Godfrey, K. R. (2004). Optimal levels of perturbation signals for nonlinear system identification. IEEE Transactions on Automatic Conrol , 49 , 1404–1407.
- El-Mikkawya, M. E. A. (2003). Inversion of a generalized Vandermonde matrix. International Journal of Computer Mathematics , 80 , 759–765.
- Eisinberg, A. , & Fedele, G. (2006). On the inversion of the Vandermonde matrix. Applied Mathematics and Computation , 174 , 1384–1397.
- Gautschi, W. , & Inglese, G. (1988). Lower bounds for the condition number of Vandermonde matrix. Numerische Mathematik , 52 , 241–250.
- Gohberg, I. , & Olshevsky, V. (1997). The fast generalized Parker--Traub algorithm for inversion of Vandermonde and related matrices. Journal of Complexity , 13 , 208–234.
- Horn, R. A. , & Johnson, C. R. (1990). Matrix analysis . Cambridge: Cambridge University Press.
- Kaufman, I. (1969). The inversion of the Vandermonde matrix and transformation to the Jordan canonical form. IEEE Transactions on Automatic Control , 14 , 774–777.
- Mirsky, L. (2011). An introduction to linear algebra . New York, NY: Dover Publications.
- Neagoe, V. (1996). Inversion of the Van der Monde matrix. IEEE Signal Processing Letters , 3 , 119–120.
- Olkkonen, H. , & Olkkonen, J. T. (2010). Sampling and reconstruction of transient signals by parallel exponential filters. IEEE Transactions on Circuits and Systems - Part II: Express Briefs , 57 , 426–429.
- Phillips, G. M. (2003). Interpolation and approximation by polynomials . New York, NY: Springer Verlag.
- Ryan, O. , & Debbah, M. (2009). Asymptotic behaviour of random Vandermonde matrices with entries on the unit circle. IEEE Transaction on Information Theory , 55 , 3115–3147.
- Respondek, J. S. (2016). Incremental numerical recipes for the high efficient inversion of the confluent Vandermonde matrices. Computers & Mathematics with Applications , 71 , 489–502.
- Wertz, H. (1965). On the numerical inversion of a recurrent problem: The Vandermonde matrix. IEEE Transactions on Automatic Control , 10 , 492.
- Wang, Z. , Scaglione, A. , Giannakis, G. , & Barbarossa, S. (1999). Vandermonde--Lagrange mutually orthogonal flexible transceivers for blind CDMA in unknown multipath. In Proceedings of 2nd IEEE Workshop on Signal Processing Advances in Wireless Communications (pp. 42–45). Minneapolis, MN.
- Wilf, H. S. (1958). Curve-fitting matrices. The American Mathematical Monthly , 65 , 272–274.
- Tou, J. (1964). Determination of the inverse Vandermonde matrix. IEEE Transactions on Automatic Control , 9 , 314.
Appendix 1
Proof of Lemma 1
Proof
We show that , where
is a
identity matrix. To achieve this goal, we start by computing the product of
and
,
It is straightforward to show that
where(A1)
(A1)
The above equations can be written in the following compact matrix form(A2)
(A2)
Now, we evaluate ,
It is simple to show that(A3)
(A3)
where(A4)
(A4)
(A5)
(A5)
The above equalities can be written in the following matrix(A6)
(A6)
It remains to show that . Using Equation (8), we obtain
(A7)
(A7)
Therefore,
Appendix 2
Proof of Lemma 2
Proof
We use contradiction to show . Assume the coefficient
is zero, i.e.
. Then using Equations (1) and (2), we have
(B1)
(B1)
(B2)
(B2)
By combining Equations (9) and (10), we obtain(B3)
(B3)
The first matrix in (15) is a Vandermonde matrix
. Since
are distinct,Footnote
5
therefore
is a nonsingular matrix and its inverse exists. By multiplying both sides of Equation (15) by
, we obtain
(B4)
(B4)
The above equality implies that our assumption, , is not correct. Therefore,
.