Necessary and Sufficient Conditions for Sparsity Pattern Recovery

摘要: The paper considers the problem of detecting sparsity pattern a k -sparse vector in \BBR n from m random noisy measurements. A new necessary condition on number measurements for asymptotically reliable detection with maximum-likelihood (ML) estimation and Gaussian measurement matrices is derived. This ML compared against sufficient simple maximum correlation (MC) or thresholding algorithms. analysis shows that gap between can be described by expression terms total signal-to-noise ratio (SNR), growing increasing SNR. Thresholding also more sophisticated Lasso orthogonal matching pursuit (OMP) methods. At high SNRs, it shown OMP over range powers nonzero component values unknown signals. Specifically, key benefit ability to detect signals relatively small components.