We show exactly how much extra data you need when your data is sparse instead of dense, and how sparsifying an already-dense data matrix affects ground truth recovery. In this newer completed version of the paper, we resolve an open conjecture from the older NeurIPS 2025 version.</p>\n","updatedAt":"2026-09-10T15:25:09.267Z","author":{"_id":"6a9000e09b21fe3dfb5eb29d","avatarUrl":"https://cdn-avatars.huggingface.co/v1/production/uploads/6a9000e09b21fe3dfb5eb29d/6zphaIhwcMMV0NlPZAXBL.jpeg","fullname":"Youssef Chaabouni","name":"youssefchaabouni","type":"user","isPro":false,"isHf":false,"isHfAdmin":false,"isMod":false,"isUserFollowing":false}},"numEdits":0,"identifiedLanguage":{"language":"en","probability":0.8856626749038696},"editors":["youssefchaabouni"],"editorAvatarUrls":["https://cdn-avatars.huggingface.co/v1/production/uploads/6a9000e09b21fe3dfb5eb29d/6zphaIhwcMMV0NlPZAXBL.jpeg"],"reactions":[],"isReport":false}}],"primaryEmailConfirmed":false,"paper":{"id":"2509.01809","authors":[{"_id":"6aa1c83ba2aeb74440b1dccd","user":{"_id":"6a9000e09b21fe3dfb5eb29d","avatarUrl":"https://cdn-avatars.huggingface.co/v1/production/uploads/6a9000e09b21fe3dfb5eb29d/6zphaIhwcMMV0NlPZAXBL.jpeg","isPro":false,"fullname":"Youssef Chaabouni","user":"youssefchaabouni","type":"user","name":"youssefchaabouni"},"name":"Youssef Chaabouni","status":"claimed_verified","statusLastChangedAt":"2026-09-10T00:45:05.051Z","hidden":false},{"_id":"6aa1c83ba2aeb74440b1dcce","name":"David Gamarnik","hidden":false}],"publishedAt":"2026-09-08T00:00:00.000Z","submittedOnDailyAt":"2026-09-10T00:00:00.000Z","title":"The Price of Sparsity: Sufficient Conditions for Sparse Recovery using Sparse and Sparsified Measurements","submittedOnDailyBy":{"_id":"6a9000e09b21fe3dfb5eb29d","avatarUrl":"https://cdn-avatars.huggingface.co/v1/production/uploads/6a9000e09b21fe3dfb5eb29d/6zphaIhwcMMV0NlPZAXBL.jpeg","isPro":false,"fullname":"Youssef Chaabouni","user":"youssefchaabouni","type":"user","name":"youssefchaabouni"},"summary":"We consider the problem of support recovery for sparse binary signals from noisy linear measurements. For sparse Gaussian measurement matrices we identify sufficient conditions on the minimal sample size for maximum-likelihood recovery in the high-SNR regime ds/p to infty, where p denotes the signal dimension, s the number of non-zero components of the signal, and d the expected number of non-zero components per row of measurement. Combined with known lower bounds, this yields an information-theoretic threshold of order slog(p/s) / log(ds/p), making explicit the price of measurement sparsity. In particular, we highlight a regime where the sample-complexity loss from measurement sparsity is logarithmic while the computational gain is nearly linear.\n Second, we study recovery after sparsifying an originally dense Gaussian design: the observations are generated from the dense design, while estimation uses an independently sparsified design and a rescaled response. In the proportional regime s=αp, d=ψp, we prove that, for every fixed target error level δ and every slack varepsilon>0, a sample size of order p/ψ^2 is sufficient for support recovery for arbitrarily small ψ.","upvotes":0,"discussionId":"6aa1c83ba2aeb74440b1dccf","ai_summary":"For sparse binary signals, sufficient sample sizes for maximum-likelihood support recovery are identified in high-SNR regimes, revealing an information-theoretic threshold and trade-offs between measurement sparsity and computational cost, with analysis also covering sparsified dense designs.","ai_keywords":["support recovery","sparse binary signals","noisy linear measurements","sparse Gaussian measurement matrices","maximum-likelihood recovery","high-SNR regime","information-theoretic threshold","measurement sparsity","dense Gaussian design","proportional regime"],"ai_summary_model":"thinkingmachines/Inkling-Small","organization":{"_id":"62cf234c216602c3f3123382","name":"Massachusetts-Institute-of-Technology","fullname":"Massachusetts Institute of Technology","avatar":"https://cdn-avatars.huggingface.co/v1/production/uploads/1657742064194-62cf1fdb2822f319618d82a8.png"}},"canReadDatabase":false,"canManagePapers":false,"canSubmit":false,"hasHfLevelAccess":false,"upvoted":false,"upvoters":[],"acceptLanguages":["en"],"organization":{"_id":"62cf234c216602c3f3123382","name":"Massachusetts-Institute-of-Technology","fullname":"Massachusetts Institute of Technology","avatar":"https://cdn-avatars.huggingface.co/v1/production/uploads/1657742064194-62cf1fdb2822f319618d82a8.png"},"markdownContentUrl":"https://huggingface.co/buckets/huggingchat/papers-content/resolve/2509/2509.01809.md","query":{}}">
The Price of Sparsity: Sufficient Conditions for Sparse Recovery using Sparse and Sparsified Measurements
Abstract
For sparse binary signals, sufficient sample sizes for maximum-likelihood support recovery are identified in high-SNR regimes, revealing an information-theoretic threshold and trade-offs between measurement sparsity and computational cost, with analysis also covering sparsified dense designs.
We consider the problem of support recovery for sparse binary signals from noisy linear measurements. For sparse Gaussian measurement matrices we identify sufficient conditions on the minimal sample size for maximum-likelihood recovery in the high-SNR regime ds/p to infty, where p denotes the signal dimension, s the number of non-zero components of the signal, and d the expected number of non-zero components per row of measurement. Combined with known lower bounds, this yields an information-theoretic threshold of order slog(p/s) / log(ds/p), making explicit the price of measurement sparsity. In particular, we highlight a regime where the sample-complexity loss from measurement sparsity is logarithmic while the computational gain is nearly linear.
Second, we study recovery after sparsifying an originally dense Gaussian design: the observations are generated from the dense design, while estimation uses an independently sparsified design and a rescaled response. In the proportional regime s=αp, d=ψp, we prove that, for every fixed target error level δ and every slack varepsilon>0, a sample size of order p/ψ^2 is sufficient for support recovery for arbitrarily small ψ.
Community
We show exactly how much extra data you need when your data is sparse instead of dense, and how sparsifying an already-dense data matrix affects ground truth recovery. In this newer completed version of the paper, we resolve an open conjecture from the older NeurIPS 2025 version.
Upload images, audio, and videos by dragging in the text input, pasting, or clicking here.
Tap or paste here to upload images
Cite arxiv.org/abs/2509.01809 in a model README.md to link it from this page.
Cite arxiv.org/abs/2509.01809 in a dataset README.md to link it from this page.
Cite arxiv.org/abs/2509.01809 in a Space README.md to link it from this page.
Discussion (0)
Sign in to join the discussion. Free account, 30 seconds — email code or GitHub.
Sign in →No comments yet. Sign in and be the first to say something.