Sparsity maximization under a quadratic constraint with applications in filter design

Dennis Wei, Alan V. Oppenheim

Abstract

This paper considers two problems in sparse filter design, the first involving a least-squares constraint on the frequency response, and the second a constraint on signal-to-noise ratio relevant to signal detection. It is shown that both problems can be recast as the minimization of the number of non-zero elements in a vector subject to a quadratic constraint. A solution is obtained for the case in which the matrix in the quadratic constraint is diagonal. For the more difficult non-diagonal case, a relaxation based on the substitution of a diagonal matrix is developed. Numerical simulations show that this diagonal relaxation is tighter than a linear relaxation under a wide range of conditions. The diagonal relaxation is therefore a promising candidate for inclusion in branch-and-bound algorithms.
BibTeX
@inproceedings{wei2010sparsity,
  author = {Dennis Wei and Alan V. Oppenheim},
  title = {{Sparsity maximization under a quadratic constraint with applications in filter design}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2010},
  doi = {10.1109/icassp.2010.5495892},
}

Loading related content...

Figure