Hadamard wirtinger flow for sparse phase retrieval
We consider the problem of reconstructing an n-dimensional k-sparse signal from a set of noiseless magnitude-only measurements. Formulating the problem as an unregularized empirical risk minimization task, we study the sample complexity performance of gradient descent with Hadamard parametrization,...
| 主要な著者: | , |
|---|---|
| フォーマット: | Conference item |
| 言語: | English |
| 出版事項: |
Journal of Machine Learning Research
2021
|
| _version_ | 1826281788145664000 |
|---|---|
| author | Wu, F Rebeschini, P |
| author_facet | Wu, F Rebeschini, P |
| author_sort | Wu, F |
| collection | OXFORD |
| description | We consider the problem of reconstructing an
n-dimensional k-sparse signal from a set of
noiseless magnitude-only measurements. Formulating the problem as an unregularized empirical risk minimization task, we study the
sample complexity performance of gradient descent with Hadamard parametrization, which
we call Hadamard Wirtinger flow (HWF). Provided knowledge of the signal sparsity k, we
prove that a single step of HWF is able to
recover the support from k(x
∗
max)
−2
(modulo
logarithmic term) samples, where x
∗
max is the
largest component of the signal in magnitude.
This support recovery procedure can be used
to initialize existing reconstruction methods
and yields algorithms with total runtime proportional to the cost of reading the data and
improved sample complexity, which is linear
in k when the signal contains at least one large
component. We numerically investigate the
performance of HWF at convergence and show
that, while not requiring any explicit form
of regularization nor knowledge of k, HWF
adapts to the signal sparsity and reconstructs
sparse signals with fewer measurements than
existing gradient based methods. |
| first_indexed | 2024-03-07T00:34:05Z |
| format | Conference item |
| id | oxford-uuid:80cba428-6e3f-4f81-82bc-b22b9af9f7aa |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T00:34:05Z |
| publishDate | 2021 |
| publisher | Journal of Machine Learning Research |
| record_format | dspace |
| spelling | oxford-uuid:80cba428-6e3f-4f81-82bc-b22b9af9f7aa2022-03-26T21:25:49ZHadamard wirtinger flow for sparse phase retrievalConference itemhttp://purl.org/coar/resource_type/c_5794uuid:80cba428-6e3f-4f81-82bc-b22b9af9f7aaEnglishSymplectic ElementsJournal of Machine Learning Research2021Wu, FRebeschini, PWe consider the problem of reconstructing an n-dimensional k-sparse signal from a set of noiseless magnitude-only measurements. Formulating the problem as an unregularized empirical risk minimization task, we study the sample complexity performance of gradient descent with Hadamard parametrization, which we call Hadamard Wirtinger flow (HWF). Provided knowledge of the signal sparsity k, we prove that a single step of HWF is able to recover the support from k(x ∗ max) −2 (modulo logarithmic term) samples, where x ∗ max is the largest component of the signal in magnitude. This support recovery procedure can be used to initialize existing reconstruction methods and yields algorithms with total runtime proportional to the cost of reading the data and improved sample complexity, which is linear in k when the signal contains at least one large component. We numerically investigate the performance of HWF at convergence and show that, while not requiring any explicit form of regularization nor knowledge of k, HWF adapts to the signal sparsity and reconstructs sparse signals with fewer measurements than existing gradient based methods. |
| spellingShingle | Wu, F Rebeschini, P Hadamard wirtinger flow for sparse phase retrieval |
| title | Hadamard wirtinger flow for sparse phase retrieval |
| title_full | Hadamard wirtinger flow for sparse phase retrieval |
| title_fullStr | Hadamard wirtinger flow for sparse phase retrieval |
| title_full_unstemmed | Hadamard wirtinger flow for sparse phase retrieval |
| title_short | Hadamard wirtinger flow for sparse phase retrieval |
| title_sort | hadamard wirtinger flow for sparse phase retrieval |
| work_keys_str_mv | AT wuf hadamardwirtingerflowforsparsephaseretrieval AT rebeschinip hadamardwirtingerflowforsparsephaseretrieval |