Sublinear-time algorithms for compressive phase retrieval
In the problem of compressed phase retrieval, the goal is to reconstruct a sparse or approximately k-sparse vector x in C n given access to y= |φ x|, where |v| denotes the vector obtained from taking the absolute value of v inCn coordinate-wise. In this paper we present sublinear-time algorithms for...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2022
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/161218 |
| _version_ | 1824456495470739456 |
|---|---|
| author | Li, Yi Nakos, Vasileios |
| author2 | School of Physical and Mathematical Sciences |
| author_facet | School of Physical and Mathematical Sciences Li, Yi Nakos, Vasileios |
| author_sort | Li, Yi |
| collection | NTU |
| description | In the problem of compressed phase retrieval, the goal is to reconstruct a sparse or approximately k-sparse vector x in C n given access to y= |φ x|, where |v| denotes the vector obtained from taking the absolute value of v inCn coordinate-wise. In this paper we present sublinear-time algorithms for a few for-each variants of the compressive phase retrieval problem which are akin to the variants considered for the classical compressive sensing problem in theoretical computer science. Our algorithms use pure combinatorial techniques and near-optimal number of measurements. |
| first_indexed | 2025-02-19T03:55:01Z |
| format | Journal Article |
| id | ntu-10356/161218 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2025-02-19T03:55:01Z |
| publishDate | 2022 |
| record_format | dspace |
| spelling | ntu-10356/1612182022-08-19T07:50:36Z Sublinear-time algorithms for compressive phase retrieval Li, Yi Nakos, Vasileios School of Physical and Mathematical Sciences Engineering::Computer science and engineering Signal Processing Algorithms Phase Measurement In the problem of compressed phase retrieval, the goal is to reconstruct a sparse or approximately k-sparse vector x in C n given access to y= |φ x|, where |v| denotes the vector obtained from taking the absolute value of v inCn coordinate-wise. In this paper we present sublinear-time algorithms for a few for-each variants of the compressive phase retrieval problem which are akin to the variants considered for the classical compressive sensing problem in theoretical computer science. Our algorithms use pure combinatorial techniques and near-optimal number of measurements. The work of Vasileios Nakos was supported in part by ONR under Grant N00014-15-1-2388. 2022-08-19T07:50:36Z 2022-08-19T07:50:36Z 2020 Journal Article Li, Y. & Nakos, V. (2020). Sublinear-time algorithms for compressive phase retrieval. IEEE Transactions On Information Theory, 66(11), 7302-7310. https://dx.doi.org/10.1109/TIT.2020.3020701 0018-9448 https://hdl.handle.net/10356/161218 10.1109/TIT.2020.3020701 2-s2.0-85094631070 11 66 7302 7310 en IEEE Transactions on Information Theory © 2020 IEEE. All rights reserved. |
| spellingShingle | Engineering::Computer science and engineering Signal Processing Algorithms Phase Measurement Li, Yi Nakos, Vasileios Sublinear-time algorithms for compressive phase retrieval |
| title | Sublinear-time algorithms for compressive phase retrieval |
| title_full | Sublinear-time algorithms for compressive phase retrieval |
| title_fullStr | Sublinear-time algorithms for compressive phase retrieval |
| title_full_unstemmed | Sublinear-time algorithms for compressive phase retrieval |
| title_short | Sublinear-time algorithms for compressive phase retrieval |
| title_sort | sublinear time algorithms for compressive phase retrieval |
| topic | Engineering::Computer science and engineering Signal Processing Algorithms Phase Measurement |
| url | https://hdl.handle.net/10356/161218 |
| work_keys_str_mv | AT liyi sublineartimealgorithmsforcompressivephaseretrieval AT nakosvasileios sublineartimealgorithmsforcompressivephaseretrieval |