A linear algebra approach to systems of polynomial equations with application to digital communications

We introduce in this paper a new algebraic approach to some problems arising in signal processing and communications that can be described as or reduced to systems of multivariate quadratic polynomial equations. Based on methods from computational algebraic geometry, the approach achieves a full description of the solution space and thus avoids the local minima issue of adaptive algorithms. Furthermore, unlike most symbolic methods, the computational cost is kept low by a split of the problem into two stages. First, a symbolic pre-computation is done offline once for all, to get a more convenient parametric trace-matrix representation of the problem using normal forms. The solutions of the problem are then easily obtained from this representation by solving a single univariate polynomial equation. This approach is quite general and can be applied to a wide variety of problems: SISO channel identification of PSK modulations but also filter design and possibly MIMO blind source separation by deflation.