Cargando…
The Noise Collector for sparse recovery in high dimensions
The ability to detect sparse signals from noisy, high-dimensional data is a top priority in modern science and engineering. It is well known that a sparse solution of the linear system [Formula: see text] can be found efficiently with an [Formula: see text]-norm minimization approach if the data are...
Autores principales: | , , , |
---|---|
Formato: | Online Artículo Texto |
Lenguaje: | English |
Publicado: |
National Academy of Sciences
2020
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7260980/ https://www.ncbi.nlm.nih.gov/pubmed/32393628 http://dx.doi.org/10.1073/pnas.1913995117 |
_version_ | 1783540424557723648 |
---|---|
author | Moscoso, Miguel Novikov, Alexei Papanicolaou, George Tsogka, Chrysoula |
author_facet | Moscoso, Miguel Novikov, Alexei Papanicolaou, George Tsogka, Chrysoula |
author_sort | Moscoso, Miguel |
collection | PubMed |
description | The ability to detect sparse signals from noisy, high-dimensional data is a top priority in modern science and engineering. It is well known that a sparse solution of the linear system [Formula: see text] can be found efficiently with an [Formula: see text]-norm minimization approach if the data are noiseless. However, detection of the signal from data corrupted by noise is still a challenging problem as the solution depends, in general, on a regularization parameter with optimal value that is not easy to choose. We propose an efficient approach that does not require any parameter estimation. We introduce a no-phantom weight [Formula: see text] and the Noise Collector matrix [Formula: see text] and solve an augmented system [Formula: see text] , where [Formula: see text] is the noise. We show that the [Formula: see text]-norm minimal solution of this system has zero false discovery rate for any level of noise, with probability that tends to one as the dimension of [Formula: see text] increases to infinity. We obtain exact support recovery if the noise is not too large and develop a fast Noise Collector algorithm, which makes the computational cost of solving the augmented system comparable with that of the original one. We demonstrate the effectiveness of the method in applications to passive array imaging. |
format | Online Article Text |
id | pubmed-7260980 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2020 |
publisher | National Academy of Sciences |
record_format | MEDLINE/PubMed |
spelling | pubmed-72609802020-06-08 The Noise Collector for sparse recovery in high dimensions Moscoso, Miguel Novikov, Alexei Papanicolaou, George Tsogka, Chrysoula Proc Natl Acad Sci U S A Physical Sciences The ability to detect sparse signals from noisy, high-dimensional data is a top priority in modern science and engineering. It is well known that a sparse solution of the linear system [Formula: see text] can be found efficiently with an [Formula: see text]-norm minimization approach if the data are noiseless. However, detection of the signal from data corrupted by noise is still a challenging problem as the solution depends, in general, on a regularization parameter with optimal value that is not easy to choose. We propose an efficient approach that does not require any parameter estimation. We introduce a no-phantom weight [Formula: see text] and the Noise Collector matrix [Formula: see text] and solve an augmented system [Formula: see text] , where [Formula: see text] is the noise. We show that the [Formula: see text]-norm minimal solution of this system has zero false discovery rate for any level of noise, with probability that tends to one as the dimension of [Formula: see text] increases to infinity. We obtain exact support recovery if the noise is not too large and develop a fast Noise Collector algorithm, which makes the computational cost of solving the augmented system comparable with that of the original one. We demonstrate the effectiveness of the method in applications to passive array imaging. National Academy of Sciences 2020-05-26 2020-05-11 /pmc/articles/PMC7260980/ /pubmed/32393628 http://dx.doi.org/10.1073/pnas.1913995117 Text en Copyright © 2020 the Author(s). Published by PNAS. https://creativecommons.org/licenses/by-nc-nd/4.0/ https://creativecommons.org/licenses/by-nc-nd/4.0/This open access article is distributed under Creative Commons Attribution-NonCommercial-NoDerivatives License 4.0 (CC BY-NC-ND) (https://creativecommons.org/licenses/by-nc-nd/4.0/) . |
spellingShingle | Physical Sciences Moscoso, Miguel Novikov, Alexei Papanicolaou, George Tsogka, Chrysoula The Noise Collector for sparse recovery in high dimensions |
title | The Noise Collector for sparse recovery in high dimensions |
title_full | The Noise Collector for sparse recovery in high dimensions |
title_fullStr | The Noise Collector for sparse recovery in high dimensions |
title_full_unstemmed | The Noise Collector for sparse recovery in high dimensions |
title_short | The Noise Collector for sparse recovery in high dimensions |
title_sort | noise collector for sparse recovery in high dimensions |
topic | Physical Sciences |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7260980/ https://www.ncbi.nlm.nih.gov/pubmed/32393628 http://dx.doi.org/10.1073/pnas.1913995117 |
work_keys_str_mv | AT moscosomiguel thenoisecollectorforsparserecoveryinhighdimensions AT novikovalexei thenoisecollectorforsparserecoveryinhighdimensions AT papanicolaougeorge thenoisecollectorforsparserecoveryinhighdimensions AT tsogkachrysoula thenoisecollectorforsparserecoveryinhighdimensions AT moscosomiguel noisecollectorforsparserecoveryinhighdimensions AT novikovalexei noisecollectorforsparserecoveryinhighdimensions AT papanicolaougeorge noisecollectorforsparserecoveryinhighdimensions AT tsogkachrysoula noisecollectorforsparserecoveryinhighdimensions |