Fast Mixed Integer Quadratic Programming for Sparse Signal Estimation
It has been recently shown that the <inline-formula> <tex-math notation="LaTeX">$l_{0}$ </tex-math></inline-formula>-norm problem can be reformulated into a mixed integer quadratic programming (MIQP) problem. CPLEX, a commercial optimization software package that ca...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2018-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/8493156/ |
| _version_ | 1818874835158171648 |
|---|---|
| author | Sangjun Park Heung-No Lee |
| author_facet | Sangjun Park Heung-No Lee |
| author_sort | Sangjun Park |
| collection | DOAJ |
| description | It has been recently shown that the <inline-formula> <tex-math notation="LaTeX">$l_{0}$ </tex-math></inline-formula>-norm problem can be reformulated into a mixed integer quadratic programming (MIQP) problem. CPLEX, a commercial optimization software package that can solve integer programming problems, is used to find the global solution to this MIQP problem for sparse signal estimation. However, CPLEX uses an exhaustive approach to search a feasible space to this MIQP problem. Thus, its running time grows exponentially as the problem dimension grows. This means that CPLEX quickly becomes computationally intractable for higher dimension problems. In this paper, we aim to propose a fast first-order-type method for solving this MIQP problem based on the alternating direction method. We conduct extensive simulations to demonstrate that: 1) our method is used to estimate a sparse signal by solving this problem and 2) our method is computationally tractable for problem dimensions up to the order of 1 million. |
| first_indexed | 2024-12-19T13:16:55Z |
| format | Article |
| id | doaj.art-56b181c6e6894c6a93e7a5624c6e18df |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-12-19T13:16:55Z |
| publishDate | 2018-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-56b181c6e6894c6a93e7a5624c6e18df2022-12-21T20:19:49ZengIEEEIEEE Access2169-35362018-01-016584395844910.1109/ACCESS.2018.28750228493156Fast Mixed Integer Quadratic Programming for Sparse Signal EstimationSangjun Park0https://orcid.org/0000-0003-4975-042XHeung-No Lee1https://orcid.org/0000-0001-8528-5778School of Electrical Engineering and Computer Science, Gwangju Institute of Science and Technology, Gwangju, South KoreaSchool of Electrical Engineering and Computer Science, Gwangju Institute of Science and Technology, Gwangju, South KoreaIt has been recently shown that the <inline-formula> <tex-math notation="LaTeX">$l_{0}$ </tex-math></inline-formula>-norm problem can be reformulated into a mixed integer quadratic programming (MIQP) problem. CPLEX, a commercial optimization software package that can solve integer programming problems, is used to find the global solution to this MIQP problem for sparse signal estimation. However, CPLEX uses an exhaustive approach to search a feasible space to this MIQP problem. Thus, its running time grows exponentially as the problem dimension grows. This means that CPLEX quickly becomes computationally intractable for higher dimension problems. In this paper, we aim to propose a fast first-order-type method for solving this MIQP problem based on the alternating direction method. We conduct extensive simulations to demonstrate that: 1) our method is used to estimate a sparse signal by solving this problem and 2) our method is computationally tractable for problem dimensions up to the order of 1 million.https://ieeexplore.ieee.org/document/8493156/Alternating direction methodcompressed sensingmixed integer quadratic program |
| spellingShingle | Sangjun Park Heung-No Lee Fast Mixed Integer Quadratic Programming for Sparse Signal Estimation IEEE Access Alternating direction method compressed sensing mixed integer quadratic program |
| title | Fast Mixed Integer Quadratic Programming for Sparse Signal Estimation |
| title_full | Fast Mixed Integer Quadratic Programming for Sparse Signal Estimation |
| title_fullStr | Fast Mixed Integer Quadratic Programming for Sparse Signal Estimation |
| title_full_unstemmed | Fast Mixed Integer Quadratic Programming for Sparse Signal Estimation |
| title_short | Fast Mixed Integer Quadratic Programming for Sparse Signal Estimation |
| title_sort | fast mixed integer quadratic programming for sparse signal estimation |
| topic | Alternating direction method compressed sensing mixed integer quadratic program |
| url | https://ieeexplore.ieee.org/document/8493156/ |
| work_keys_str_mv | AT sangjunpark fastmixedintegerquadraticprogrammingforsparsesignalestimation AT heungnolee fastmixedintegerquadraticprogrammingforsparsesignalestimation |