Testing noisy linear functions for sparsity

We consider the following basic inference problem: there is an unknown high-dimensional vector w ∈ ℝ n , and an algorithm is given access to labeled pairs ( x , y ) where x ∈ ℝ n is a measurement and y = w · x + noise . What is the complexity of deciding whether the target vector w is (approximately) k -sparse? The recovery analogue of this problem — given the promise that w is sparse, find or approximate the vector w — is the famous sparse recovery problem, with a rich body of work in signal processing, statistics, and computer science.

Authors

• Xue Chen 0001
• Anindya De
• Rocco A. Servedio

Keywords

• Property testing
• cumulants
• sparse recovery