Optimization Online


Approximate spectral factorization for design of efficient sub-filter sequences

Björn Norell (bjosv***at***imt.liu.se)
Oleg Burdakov (Oleg.Burdakov***at***liu.se)
Mats Andersson (matsa***at***imt.liu.se)
Hans Knutsson (knutte***at***imt.liu.se)

Abstract: 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.

Keywords: multilinear least squares; global optimization; filter networks

Category 1: Global Optimization (Applications )

Category 2: Nonlinear Optimization (Nonlinear Systems and Least-Squares )

Category 3: Nonlinear Optimization (Constrained Nonlinear Optimization )

Citation: Technical Report LiTH-MAT-R-2011/14-SE, Department of Mathematics, Linkoeping University, 2011.

Download: [PDF]

Entry Submitted: 10/08/2011
Entry Accepted: 10/09/2011
Entry Last Modified: 10/09/2011

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society