The Noise Collector for sparse recovery in high dimensions
The Noise Collector for sparse recovery in high dimensions
复制标题
DOI：
10.1073/pnas.1913995117
复制
发表时间：
2019-08
影响因子：
11.1
通讯作者：
M. Moscoso;A. Novikov;G. Papanicolaou;C. Tsogka
中科院分区：
文献类型：
--
作者：
M. Moscoso;A. Novikov;G. Papanicolaou;C. Tsogka
从噪声、高维数据中检测稀疏信号的能力是现代科学和工程的重中之重。为了获得最佳结果，目前的方法需要调整依赖于噪声水平的参数，而噪声通常很难估计。我们开发了一种无参数、计算效率高、1-范数最小化方法，该方法对任何水平的噪声都具有高概率的零错误发现率（无假阳性），同时在噪声不太大的情况下检测稀疏信号的确切位置。从嘈杂的高维数据中检测稀疏信号的能力是现代科学和工程的重中之重。众所周知，如果数据是无噪声的，用1-范数最小化方法可以有效地找到线性系统a =b0的稀疏解。然而，从被噪声破坏的数据中检测信号仍然是一个具有挑战性的问题，因为解决方案通常依赖于具有最优值的正则化参数，而正则化参数不易选择。我们提出了一种不需要任何参数估计的有效方法。我们引入无虚影权值τ和噪声收集器矩阵C，求解增广系统ρ+Cη=b0+e，其中e为噪声。我们证明了该系统的1-范数最小解对于任何噪声水平都具有零错误发现率，并且随着b0的维数增加到无穷大，其概率趋于1。我们在噪声不太大的情况下获得了精确的支撑恢复，并开发了一种快速的噪声收集器算法，使求解增强系统的计算成本与原系统相当。我们证明了该方法在被动阵列成像中的有效性。
Significance The ability to detect sparse signals from noisy, high-dimensional data is a top priority in modern science and engineering. For optimal results, current approaches need to tune parameters that depend on the level of noise, which is often difficult to estimate. We develop a parameter-free, computationally efficient, ℓ1-norm minimization approach that has a zero false discovery rate (no false positives) with high probability for any level of noise while it detects the exact location of sparse signals when the noise is not too large. 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 ℓ1-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 τ and the Noise Collector matrix C and solve an augmented system Aρ+Cη=b0+e, where e is the noise. We show that the ℓ1-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.