A well-known approach to the design of computationally efficient filters is to use spectral factorization, i.e. a decomposition of a filter into a sequence of sub-filters. Due to the sparsity of the sub-filters, the typical processing speedup factor is within the range 1-10 in 2D, and for 3D it achieves 10-100. The design of such decompositions consists in choosing the proper number of sub-filters, their individual types and sparsity. We focus here on finding optimal values of coefficients for given sequences of sparse sub-filters. It is a non-convex large scale optimization problem, namely, multilinear least squares. The existing approaches are characterized by a lack of robustness – a very slow convergence with no guarantee of success. They are typically based on generating random initial points for further refinement with the use of local search methods. To deal with the multi-extremal nature of the original problem, we introduce a new constrained optimization problem. Its solution is then used as an initial point in the original problem for further refinement. Our approach is applicable to designing multi-dimensional filters. Its efficiency and robustness is illustrated by designing sub-filter sequences for 2D low-pass, band-pass and high-pass filters of approximately the same quality as with the use of a standard approach, but with the overall design speedup factor of several hundred.
Citation
Technical Report LiTH-MAT-R-2011/14-SE, Department of Mathematics, Linkoeping University, 2011.