Linear Programming Algorithms for Sparse Filter Design
In designing discrete-time filters, the length of the impulse response is often used as an indication of computational cost. In systems where the complexity is dominated by arithmetic operations, the number of nonzero coefficients in the impulse response may be a more appropriate metric to consider...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2012
|
| Online Access: | http://hdl.handle.net/1721.1/69889 https://orcid.org/0000-0003-0647-236X |
| _version_ | 1826210165700952064 |
|---|---|
| author | Baran, Thomas A. Wei, Dennis Oppenheim, Alan V. |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Baran, Thomas A. Wei, Dennis Oppenheim, Alan V. |
| author_sort | Baran, Thomas A. |
| collection | MIT |
| description | In designing discrete-time filters, the length of the impulse response is often used as an indication of computational cost. In systems where the complexity is dominated by arithmetic operations, the number of nonzero coefficients in the impulse response may be a more appropriate metric to consider instead, and computational savings are realized by omitting arithmetic operations associated with zero-valued coefficients. This metric is particularly relevant to the design of sensor arrays, where a set of array weights with many zero-valued entries allows for the elimination of physical array elements, resulting in a reduction of data acquisition and communication costs. However, designing a filter with the fewest number of nonzero coefficients subject to a set of frequency-domain constraints is a computationally difficult optimization problem. This paper describes several approximate polynomial-time algorithms that use linear programming to design filters having a small number of nonzero coefficients, i.e., filters that are sparse. Specifically, we present two approaches that have different computational complexities in terms of the number of required linear programs. The first technique iteratively thins the impulse response of a non-sparse filter until frequency-domain constraints are violated. The second minimizes the 1-norm of the impulse response of the filter, using the resulting design to determine the coefficients that are constrained to zero in a subsequent re-optimization stage. The algorithms are evaluated within the contexts of array design and acoustic equalization. |
| first_indexed | 2024-09-23T14:44:56Z |
| format | Article |
| id | mit-1721.1/69889 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T14:44:56Z |
| publishDate | 2012 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/698892022-10-01T22:14:16Z Linear Programming Algorithms for Sparse Filter Design Baran, Thomas A. Wei, Dennis Oppenheim, Alan V. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Oppenheim, Alan V. Baran, Thomas A. Wei, Dennis Oppenheim, Alan V. In designing discrete-time filters, the length of the impulse response is often used as an indication of computational cost. In systems where the complexity is dominated by arithmetic operations, the number of nonzero coefficients in the impulse response may be a more appropriate metric to consider instead, and computational savings are realized by omitting arithmetic operations associated with zero-valued coefficients. This metric is particularly relevant to the design of sensor arrays, where a set of array weights with many zero-valued entries allows for the elimination of physical array elements, resulting in a reduction of data acquisition and communication costs. However, designing a filter with the fewest number of nonzero coefficients subject to a set of frequency-domain constraints is a computationally difficult optimization problem. This paper describes several approximate polynomial-time algorithms that use linear programming to design filters having a small number of nonzero coefficients, i.e., filters that are sparse. Specifically, we present two approaches that have different computational complexities in terms of the number of required linear programs. The first technique iteratively thins the impulse response of a non-sparse filter until frequency-domain constraints are violated. The second minimizes the 1-norm of the impulse response of the filter, using the resulting design to determine the coefficients that are constrained to zero in a subsequent re-optimization stage. The algorithms are evaluated within the contexts of array design and acoustic equalization. Texas Instruments Leadership University Consortium Program BAE Systems (PO 112991) Lincoln Laboratory (PO 3077828) Massachusetts Institute of Technology. William Asbjornsen Albert Memorial Fellowship 2012-03-30T15:48:07Z 2012-03-30T15:48:07Z 2010-03 2009-05 Article http://purl.org/eprint/type/JournalArticle 1053-587X 1941-0476 INSPEC Accession Number: 11105850 http://hdl.handle.net/1721.1/69889 Baran, T., D. Wei, and A.V. Oppenheim. “Linear Programming Algorithms for Sparse Filter Design.” IEEE Transactions on Signal Processing 58.3 (2010): 1605–1617. Web. 30 Mar. 2012. © 2010 Institute of Electrical and Electronics Engineers https://orcid.org/0000-0003-0647-236X en_US http://dx.doi.org/10.1109/tsp.2009.2036471 IEEE Transactions on Signal Processing Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Institute of Electrical and Electronics Engineers (IEEE) IEEE |
| spellingShingle | Baran, Thomas A. Wei, Dennis Oppenheim, Alan V. Linear Programming Algorithms for Sparse Filter Design |
| title | Linear Programming Algorithms for Sparse Filter Design |
| title_full | Linear Programming Algorithms for Sparse Filter Design |
| title_fullStr | Linear Programming Algorithms for Sparse Filter Design |
| title_full_unstemmed | Linear Programming Algorithms for Sparse Filter Design |
| title_short | Linear Programming Algorithms for Sparse Filter Design |
| title_sort | linear programming algorithms for sparse filter design |
| url | http://hdl.handle.net/1721.1/69889 https://orcid.org/0000-0003-0647-236X |
| work_keys_str_mv | AT baranthomasa linearprogrammingalgorithmsforsparsefilterdesign AT weidennis linearprogrammingalgorithmsforsparsefilterdesign AT oppenheimalanv linearprogrammingalgorithmsforsparsefilterdesign |