Fast Minimization of Polynomial Decomposition using Fixed-Polarity Pascal Transforms

Polynomials can be represented as a weighted sum of various powers of binomials where the weights are spectral coefficients and the associated powers of binomials are basis functions. The minimization problem is concerned with finding a set of basis functions that result in a maximum number of zero-valued spectral coefficients, or alternatively, wherein the spectral vector has a norm that is as close to zero as possible. One application of this minimization problem includes compression of signals that are represented with fitted polynomials. This problem can be considered to be a higher-radix generalization of the fixed-polarity Reed-Muller minimization problem since polynomial decomposition can be efficiently accomplished using the properties of the fixed-polarity family of Pascal transforms. We devise an efficient decomposition technique based on properties of the Pascal transform and we formulate a heuristic minimization algorithm to search for the minimal decomposition. Experimental results are provided that compare the quality and performance of the heuristic search to an exhaustive search for the minimal decomposition. The experimental results indicate that finding such a minimal decomposition can be achieved in a practical amount of runtime.