IEEE Transactions on Information Theory · 2013 · 82 citations · 57 references
Natural SciencesMathematicsInformation TheoryMachine LearningOptimizationData CompressionDigital Signal ProcessingDimensionality ReductionSignal ProcessingCompressed SensingCompressive SensingError BoundsLower BoundsSignal-to-noise RatioSparse Signal ProcessingSparse Signal RepresentationSparsity Problem
Recovery of the sparsity pattern (or support) of an unknown sparse vector from a small number of noisy linear measurements is an important problem in compressed sensing. In this paper, the high-dimensional setting is considered. It is shown that if the measurement rate and per-sample signal-to-noise ratio (SNR) are finite constants independent of the length of the vector, then the optimal sparsity pattern estimate will have a constant fraction of errors. Lower bounds on the measurement rate needed to attain a desired fraction of errors are given in terms of the SNR and various key parameters of the unknown vector. The tightness of the bounds in a scaling sense, as a function of the SNR and the fraction of errors, is established by comparison with existing achievable bounds. Near optimality is shown for a wide variety of practically motivated signal models.
57
David L. Donoho · IEEE Transactions on Information Theory · 2006 · 23.1K citations
Ideal spatial adaptation by wavelet shrinkage
David L. Donoho, Iain M. Johnstone · Biometrika · 1994 · 7.8K citations