Reproduce “Price of Quality: Sufficient Conditions for Sparse Recovery using Mixed-Quality Data” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Youssef Chaabouni, David Gamarnik
The paper compares sparse recovery from measurements with different noise variances. For an agnostic decoder, its information-theoretic sufficient condition values one high-quality sample at less than two low-quality samples, while variance-aware weighting can make that replacement value arbitrarily large. For LASSO, the sample-size threshold matches the homogeneous-noise threshold, but regularization depends on average variance. These are sufficient bounds, not necessary thresholds.
Key insights
- The "Price of Quality" (γ) metric, quantifying the number of low-quality samples needed to compensate for one high-quality sample, varies significantly between informed and agnostic settings.
- Knowing and leveraging per-sample noise variances (informed decoder) dramatically increases the effective value of high-quality data for information-theoretic recovery, with γ potentially being arbitrarily large.
- The LASSO algorithm's sample size threshold for recovery in the agnostic setting is robust to individual noise level heterogeneity, depending only on the total sample size and average noise level.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.