Revisiting compressed sensing: exploiting the efficiency of simplex and sparsification methods
We propose two approaches to solve large-scale compressed sensing problems. The first approach uses the parametric simplex method to recover very sparse signals by taking a small number of simplex pivots, while the second approach reformulates the problem using Kronecker products to achieve faster c...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer Berlin Heidelberg
2017
|
| Online Access: | http://hdl.handle.net/1721.1/107484 https://orcid.org/0000-0003-3582-8898 |
| _version_ | 1826197818492059648 |
|---|---|
| author | Vanderbei, Robert Lin, Kevin Liu, Han Wang, Lie |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Vanderbei, Robert Lin, Kevin Liu, Han Wang, Lie |
| author_sort | Vanderbei, Robert |
| collection | MIT |
| description | We propose two approaches to solve large-scale compressed sensing problems. The first approach uses the parametric simplex method to recover very sparse signals by taking a small number of simplex pivots, while the second approach reformulates the problem using Kronecker products to achieve faster computation via a sparser problem formulation. In particular, we focus on the computational aspects of these methods in compressed sensing. For the first approach, if the true signal is very sparse and we initialize our solution to be the zero vector, then a customized parametric simplex method usually takes a small number of iterations to converge. Our numerical studies show that this approach is 10 times faster than state-of-the-art methods for recovering very sparse signals. The second approach can be used when the sensing matrix is the Kronecker product of two smaller matrices. We show that the best-known sufficient condition for the Kronecker compressed sensing (KCS) strategy to obtain a perfect recovery is more restrictive than the corresponding condition if using the first approach. However, KCS can be formulated as a linear program with a very sparse constraint matrix, whereas the first approach involves a completely dense constraint matrix. Hence, algorithms that benefit from sparse problem representation, such as interior point methods (IPMs), are expected to have computational advantages for the KCS problem. We numerically demonstrate that KCS combined with IPMs is up to 10 times faster than vanilla IPMs and state-of-the-art methods such as ℓ[subscript 1]_ℓ[subscript s] and Mirror Prox regardless of the sparsity level or problem size. |
| first_indexed | 2024-09-23T10:53:37Z |
| format | Article |
| id | mit-1721.1/107484 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T10:53:37Z |
| publishDate | 2017 |
| publisher | Springer Berlin Heidelberg |
| record_format | dspace |
| spelling | mit-1721.1/1074842022-09-30T23:48:29Z Revisiting compressed sensing: exploiting the efficiency of simplex and sparsification methods Vanderbei, Robert Lin, Kevin Liu, Han Wang, Lie Massachusetts Institute of Technology. Department of Mathematics Wang, Lie We propose two approaches to solve large-scale compressed sensing problems. The first approach uses the parametric simplex method to recover very sparse signals by taking a small number of simplex pivots, while the second approach reformulates the problem using Kronecker products to achieve faster computation via a sparser problem formulation. In particular, we focus on the computational aspects of these methods in compressed sensing. For the first approach, if the true signal is very sparse and we initialize our solution to be the zero vector, then a customized parametric simplex method usually takes a small number of iterations to converge. Our numerical studies show that this approach is 10 times faster than state-of-the-art methods for recovering very sparse signals. The second approach can be used when the sensing matrix is the Kronecker product of two smaller matrices. We show that the best-known sufficient condition for the Kronecker compressed sensing (KCS) strategy to obtain a perfect recovery is more restrictive than the corresponding condition if using the first approach. However, KCS can be formulated as a linear program with a very sparse constraint matrix, whereas the first approach involves a completely dense constraint matrix. Hence, algorithms that benefit from sparse problem representation, such as interior point methods (IPMs), are expected to have computational advantages for the KCS problem. We numerically demonstrate that KCS combined with IPMs is up to 10 times faster than vanilla IPMs and state-of-the-art methods such as ℓ[subscript 1]_ℓ[subscript s] and Mirror Prox regardless of the sparsity level or problem size. National Science Foundation (U.S.) (Grant DMS-1005539) 2017-03-17T22:54:33Z 2017-03-17T22:54:33Z 2016-05 2013-12 2017-02-02T15:20:50Z Article http://purl.org/eprint/type/JournalArticle 1867-2949 1867-2957 http://hdl.handle.net/1721.1/107484 Vanderbei, Robert, Kevin Lin, Han Liu, and Lie Wang. “Revisiting Compressed Sensing: Exploiting the Efficiency of Simplex and Sparsification Methods.” Mathematical Programming Computation 8, no. 3 (May 9, 2016): 253–269. https://orcid.org/0000-0003-3582-8898 en http://dx.doi.org/10.1007/s12532-016-0105-y Mathematical Programming Computation Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ Springer-Verlag Berlin Heidelberg and The Mathematical Programming Society application/pdf Springer Berlin Heidelberg Springer Berlin Heidelberg |
| spellingShingle | Vanderbei, Robert Lin, Kevin Liu, Han Wang, Lie Revisiting compressed sensing: exploiting the efficiency of simplex and sparsification methods |
| title | Revisiting compressed sensing: exploiting the efficiency of simplex and sparsification methods |
| title_full | Revisiting compressed sensing: exploiting the efficiency of simplex and sparsification methods |
| title_fullStr | Revisiting compressed sensing: exploiting the efficiency of simplex and sparsification methods |
| title_full_unstemmed | Revisiting compressed sensing: exploiting the efficiency of simplex and sparsification methods |
| title_short | Revisiting compressed sensing: exploiting the efficiency of simplex and sparsification methods |
| title_sort | revisiting compressed sensing exploiting the efficiency of simplex and sparsification methods |
| url | http://hdl.handle.net/1721.1/107484 https://orcid.org/0000-0003-3582-8898 |
| work_keys_str_mv | AT vanderbeirobert revisitingcompressedsensingexploitingtheefficiencyofsimplexandsparsificationmethods AT linkevin revisitingcompressedsensingexploitingtheefficiencyofsimplexandsparsificationmethods AT liuhan revisitingcompressedsensingexploitingtheefficiencyofsimplexandsparsificationmethods AT wanglie revisitingcompressedsensingexploitingtheefficiencyofsimplexandsparsificationmethods |