Publication: The noise collector for sparse recovery in high dimensions
Loading...
Identifiers
Publication date
2020-05-26
Defense date
Advisors
Tutors
Journal Title
Journal ISSN
Volume Title
Publisher
National Academy of Sciences
Impact
Export
Abstract
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 Alpharho=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 weight tau and the Noise Collector matrix C and solve an augmented system Alpharho+Ceta=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.
Description
Keywords
High-dimensional probability, Convex geometry, Noisy data, Sparsity-promoting algorithms
Bibliographic citation
Proceedings of the National Academy of Sciences of th United States of America, 117(21), May 2020, Pp. 11226-11232