Sublinear-time algorithms for compressive phase retrieval
In the compressive phase retrieval problem, the goal is to reconstruct a sparse or approximately k-sparse vector x ∈ R n given access to y = |Φ x |, where |v| denotes the vector obtained from taking the absolute value of v ∈ R n coordinatewise. In this paper we present sublinear-time algorithms for...
Saved in:
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Conference or Workshop Item |
| Language: | English |
| Published: |
2020
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/142571 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Nanyang Technological University |
| Language: | English |
| Summary: | In the compressive phase retrieval problem, the goal is to reconstruct a sparse or approximately k-sparse vector x ∈ R n given access to y = |Φ x |, where |v| denotes the vector obtained from taking the absolute value of v ∈ R n coordinatewise. In this paper we present sublinear-time algorithms for different variants of the compressive phase retrieval problem which are akin to the variants of the classical compressive sensing problem considered in theoretical computer science. Our algorithms use pure combinatorial techniques and achieve almost optimal number of measurements. |
|---|