TY - JOUR

T1 - The noise collector for sparse recovery in high dimensions

AU - Moscoso, Miguel

AU - Novikov, Alexei

AU - Papanicolaou, George

AU - Tsogka, Chrysoula

N1 - Funding Information:
ACKNOWLEDGMENTS. The work of M.M. was partially supported by Spanish Ministerio de Ciencia e Innovación Grant FIS2016-77892-R. The work of A.N. was partially supported by NSF Grants DMS-1515187 and DMS-1813943. The work of G.P. was partially supported by Air Force Office of Scientific Research (AFOSR) Grant FA9550-18-1-0519. The work of C.T. was partially supported by AFOSR Grants FA9550-17-1-0238 and FA9550-18-1-0519. We thank Marguerite Novikov for drawing Fig. 1, Left.
Publisher Copyright:
© 2020 National Academy of Sciences. All rights reserved.

PY - 2020/5/26

Y1 - 2020/5/26

N2 - 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 Aρ = b0 can be found efficiently with an l1-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 τ and the Noise Collector matrix C and solve an augmented system Aρ + Cn = b0 + e, where e is the noise. We show that the l1-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 b0 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.

AB - 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 Aρ = b0 can be found efficiently with an l1-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 τ and the Noise Collector matrix C and solve an augmented system Aρ + Cn = b0 + e, where e is the noise. We show that the l1-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 b0 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.

UR - http://www.scopus.com/inward/record.url?scp=85085532004&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85085532004&partnerID=8YFLogxK

U2 - 10.1073/pnas.1913995117

DO - 10.1073/pnas.1913995117

M3 - Article

C2 - 32393628

AN - SCOPUS:85085532004

SN - 0027-8424

VL - 117

JO - Proceedings of the National Academy of Sciences of the United States of America

JF - Proceedings of the National Academy of Sciences of the United States of America

IS - 21

M1 - 11226

ER -