研究高低质量数据混合下的稀疏恢复,给出可恢复的样本量条件。
Price of Quality: Sufficient Conditions for Sparse Recovery using Mixed-Quality Data
- 提出高低质量数据混合时的稀疏恢复方法,区分知情与无知解码器。
- 低质样本最多需两倍数量即可替代一个高质样本,信息论上具界限。
- 算法层面证明LASSO对数据异质性鲁棒,仅依赖平均噪声水平。
我们研究观测来自混合质量源时的稀疏恢复问题:少量高精度测量(低方差)与大量低精度测量(高方差)并存。针对这种异质噪声情形,我们建立了信息论与算法层面的样本量恢复条件。信息论方面,提出了‘质量代价’(Price of Quality)的线性权衡关系:替换一个高质样本所需的低质样本数。在解码器对数据质量完全未知的设定下,该代价均匀有界,且一个高质样本最多不超过两个低质样本的价值;而在解码器知晓每样本方差的设定下,代价可无限增大。算法层面分析了在无知设定下的LASSO,发现其恢复阈值与同质噪声情形一致,仅取决于平均噪声水平,表现出对数据异质性的显著鲁棒性。这些结果首次给出了混合质量数据下稀疏恢复的充分条件,并揭示了信息论与算法阈值对数据质量变化的不同适应机制。
原文摘要 · Abstract (English)
We study sparse recovery when observations come from mixed-quality sources: a small collection of high-quality measurements with small noise variance and a larger collection of lower-quality measurements with higher variance. For this heterogeneous-noise setting, we establish sample-size conditions for information-theoretic and algorithmic recovery. On the information-theoretic side, we show that it is sufficient for $(n_1, n_2)$ to satisfy a linear trade-off defining the Price of Quality: the number of low-quality samples needed to replace one high-quality sample. In the agnostic setting, where the decoder is completely agnostic to the quality of the data, it is uniformly bounded, and in particular one high-quality sample is never worth more than two low-quality samples for this sufficient condition to hold. In the informed setting, where the decoder is informed of per-sample variances, the price of quality can grow arbitrarily large. On the algorithmic side, we analyze the LASSO in the agnostic setting and show that the recovery threshold matches the homogeneous-noise case and only depends on the average noise level, revealing a striking robustness of computational recovery to data heterogeneity. Together, these results give the first conditions for sparse recovery with mixed-quality data and expose a fundamental difference between how the information-theoretic and algorithmic thresholds adapt to changes in data quality.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。